Понятие мощности множества. Сравнение мощностей. Теорема Кантора-Берштейна. Операции над кардинальными числами

Множества А и В называются эквивалентными (А~В), если существует биекция f: А↔В.

Свойства отношения эквивалентности:

1) А~А (поскольку id_A: А↔А);

2) если А~В, то В~А (т.к. из f: А↔В следует f^-1: В↔А);

3) если А~В и В~С, то А~С (т.к. из f: А↔В, g: В↔С следует f•g: А↔С).

Мощностью множества А называется класс всех множеств, эквивалентных множеству А (|А|).

Эквивалентные множества А и В называются равномощными: |A|=|B|.

Если А~n для некоторого , т.е. А имеет ровно n элементов, то множество А называется конечным (|A|=n).

Множество, не являющееся конечным, называется бесконечным. Если А~ω, то множество А называется счетным: |A|=ω. Если А~2^ω, то множество А называется континуальным или континуумом: |A|=2^ω.

Мощности множеств также иногда называют кардинальными числами.

Сравнение мощностей:

Говорят, что мощность множества А не превосходит мощности множества В: |A|≤|B|, если А эквивалентно некоторому подмножеству множества В

Теорема Кантора-Бернштейна:

Если |A|≤|B| и |B|≤|A|, то |A|=|B|.

Доказательство: Пусть f: A→B, g: B→A – разнозначные отображения, А₀=А, А₁=g(B) и А_n+2=(f•g)(A_n). Индукцией по n легко показать, что , . Пусть и . Очевидно, что и при i≠j. Т.к. f•g разнозначно отображает M_i на М_i+2 для любого , то отображение h: А→А, определенное следующим образом:

является разнозначным отображением А на . Т.к. |B|=|A₁|, |B|=|A|.

Следствие: Для любых множеств А и В выполняется только одно из соотношений: |A|=|A|, |A|<|B|, |B|<|A|.

Операции над кардинальными числами:

Пусть |A|=α, |B|=β. Тогда

1) ;

2) ;

3) .

Для конечных кардинальных чисел справедливы следующие три правила, используемые в комбинаторике:

Правило суммы: Если |A|=m, |B|=n, то .

Правило произведения: Если |A|=m, |B|=n, то .

Правило степени: Если |A|=m, |B|=n, то |A^B|=mⁿ.

Некоторые свойства бесконечных кардиналов:

ω²~ω; ω~ ; |Q|=ω; |P(U)|=2^|U|; |U|<2^|U|; если |A|>ω и |B|≤ω, то |A\B|=|A|; 2^ω~10^ω~ω^ω;