Мощность множества

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Мощность множества, кардинальное число множества (лат. cardinaliscardo — главное обстоятельство, стержень, сердцевина) — характеристика множеств (в том числе бесконечных), обобщающая понятие количества (числа) элементов конечного множества.

В основе этого понятия лежат естественные представления о сравнении множеств:

  1. Любые два множества, между элементами которых может быть установлено взаимно-однозначное соответствие (биекция), содержат одинаковое количество элементов (имеют одинаковую мощность).
  2. Обратно: множества, равные по мощности, должны допускать такое взаимно-однозначное соответствие.
  3. Часть множества не превосходит полного множества по мощности (то есть по количеству элементов).

До построения теории мощности множеств, множества различались по признакам: пустое/непустое и конечное/бесконечное, также конечные множества различались по количеству элементов. Бесконечные же множества нельзя было сравнить.

Мощность множеств позволяет сравнивать бесконечные множества. Например, счётные множества являются самыми «маленькими» бесконечными множествами.

Мощность множества A обозначается через |A|. Сам Кантор использовал обозначение \overline{\overline{A}}. Иногда встречаются обозначения \# A и \mathrm{card}(A).

Определение[править | править исходный текст]

Два множества называются равномощными, если между ними существует биекция. Существование биекции между множествами есть отношение эквивалентности, а мощность множества — это соответствующий ему класс эквивалентности.

Комментарий[править | править исходный текст]

Класс множеств, биективно эквивалентных данному, не является множеством.

Связанные определения[править | править исходный текст]

  • Мощность множества натуральных чисел {\mathbb N} обозначается символом \aleph_0алеф-нуль»). Множество называется бесконечным, если его мощность \geqslant\aleph_0 (не меньше мощности множества натуральных чисел), таким образом, счётные множества — это «самые маленькие» из бесконечных множеств. Следующие кардинальные числа в порядке возрастания обозначаются \aleph_1, \aleph_2,\dots\aleph_\omega,\aleph_{\omega+1},\dots\aleph_{\omega_1},\dots (где индекс пробегает все порядковые числа). Среди кардинальных чисел нет наибольшего: для любого множества кардинальных чисел существует кардинальное число, большее всех элементов этого множества.
  • Для мощностей, как и в случае конечных множеств, имеются понятия: «равенство», «больше», «меньше». То есть для любых множеств A и B возможно только одно из трёх:
    1. |A|=|B|, или A и B равномощны;
    2. |A|>|B|, или A мощнее B, т. е. A содержит подмножество, равномощное B, но A и B не равномощны;
    3. |A|<|B|, или B мощнее A — в этом случае B содержит подмножество, равномощное A, но A и B не равномощны.
    • Ситуация, в которой A и B не равномощны и ни в одном из них нет части, равномощной другому, невозможна. Это следует из теоремы Цермело. Иначе это означало бы существование несравнимых между собой мощностей (что в принципе возможно, если не принимать аксиому выбора).
    • Ситуация, в которой |A|>|B| и |A|<|B|, невозможна по теореме Кантора — Бернштейна.

Примеры[править | править исходный текст]

  • Множество называется конечным, если оно равномощно отрезку натурального ряда I_n = \{1,2,...,n\} при некотором неотрицательном целом n. Число n выражает количество элементов конечного множества. При n=0 множество не содержит элементов (пустое множество). Если n<m, то не существует инъективного отображения из I_m в I_n (принцип Дирихле), а значит, не существует и биекции между ними. Поэтому множества I_m и I_n имеют различную мощность.
  • Множество называется счётным, если оно равномощно множеству всех натуральных чисел \mathbb{N}. Счётными множествами являются:
    • Множество \mathbb{N}\setminus I_k при любом натуральном k. Соответствие: n\rightarrow n+k.
    • Множество \mathbb{N}\cup \{0\}. Соответствие: n\rightarrow n-1.
    • Множество целых чисел \mathbb{Z}. Соответствие получается при сопоставлении членов ряда 0 + 1 - 2 + 3 - 4 + 5 - 6 + ... его частичным суммам (члены ряда берутся без учёта знака).
    • Множество пар натуральных чисел \mathbb{N}\times\mathbb{N}.
    • Множество рациональных чисел \mathbb{Q} инъективно отображается во множество \mathbb{Z}\times\mathbb{N} (несократимой дроби вида p/q соответствует пара чисел (p,q)\in\mathbb{Z}\times\mathbb{N}). Поэтому множество рациональных чисел не более, чем счётно. Но так как оно содержит множество натуральных чисел, то оно и не менее, чем счётно. По теореме Кантора-Бернштейна оно счётно.
  • Бесконечные множества, неравномощные множеству \mathbb{N}, называются несчётными. По теореме Кантора несчётным является множество бесконечных последовательностей, составленных из цифр 0 и 1. Мощность этого множества называется континуум.

Свойства[править | править исходный текст]

  • Два конечных множества равномощны тогда и только тогда, когда они состоят из одинакового числа элементов. То есть для конечного множества понятие мощности совпадает с привычным понятием количества.
  • Для бесконечных множеств мощность множества может совпадать с мощностью своего собственного подмножества, например |{\mathbb N}|=|\mathbb Z|.
    • Более того, множество бесконечно тогда и только тогда, когда оно содержит равномощное собственное (то есть не совпадающее с основным множеством) подмножество.
  • Теорема Кантора гарантирует существование более мощного множества для любого данного: Множество всех подмножеств множества A имеет большую мощность, чем A, или |2^A| > |A|.
  • С помощью канторова квадрата можно также доказать следующее полезное утверждение: Декартово произведение бесконечного множества A с самим собой равномощно A.
  • Мощность декартова произведения:
    |A\times B|=|A|\cdot |B|
  • Формула включения-исключения в простейшем виде:
    |A\cup B|=|A| + |B| - |A\cap B|


См. также[править | править исходный текст]

Литература[править | править исходный текст]