§ 4. Сравнение мощностей

Обозначим А = a, B = b . Как ввести отношение порядка во множестве кардинальных чисел?

С точки зрения логики возможны четыре случая:

1. А~Ц с B a B~A₁~A.

В этом случае по теореме Кантора-Шредера-Бернштейна A~B,

т. е. a = b .

2. А з A₁~B, но $ B с B: B₁~A. Естественно считать, что А > B, т. е. a > b.

3. B з B₁~A, но $ А₁~А : Д ~B. Аналогично считаем b > a .

4. $ Дс А : A₁~B a$ Д с B: Д~А.

В этом случае надо считать a и b несравнимыми между собой. Однако в современной математике во избежание парадоксов все же ограничивают доступ множеств в математику некоторой системой аксиом. При принятии наиболее распространенной аксиоматики Цермело - Френкеля доказывается, что случай 4 невозможен, и далее мы его не рассматриваем. За подробностями отсылаем к [1].

Итак, вследствие наших определений любые два кардинальных числа сравнимы. Выясним свойства введенного нами отношения порядка для мощностей.

Ясно, что случай a = b исключает a > b и b > a . Как обычно, a < b означает, что b > a. Одновременно a > b и a < b не могут иметь место. Действительно, в противном случае имеем: $Д : A~B и ЗД : B₁~A. Тогда по теореме Кантора-Шредера-Берштейна: a = b .

Несовместимы также a = b и a > b , поскольку a = b требует B с B: B₁~A₁, а a>b запрещает это. Аналогично a = Р и a < Р не могут иметь место одновременно. Значит, верна.

Теорема 1

При сравнении кардинальных чисел выполняется одно и только одно из трех условий:

1. a = p;

2. a > р;

3. a < b. (свойство трихотомии).

В частности, a > a никогда не выполняется. Для того чтобы утверждать, что сравнение кардинальных чисел, введенное нами, действительно есть отношение порядка, надо еще установить, что оно транзитивно.

Теорема 2

Если a < Р и Р < g, то a < g. Доказательство

По условию A~B е B, B-Q е C, отсюда A~C₂ е C, C₂ = j( B_l), здесь j : B « C_x. Остается показать, что A~C. В противном случае C₂ ~C ^ Q ~C ^ B~C ^ Р = g, что невозможно. И тогда a < g. Теорема доказана.

Как обычно, a < Р означает a < Р v a = Р . Таким образом, отношение a > Р есть отношение порядка на множестве кардинальных чисел.

Наименьшая мощность есть 0 = 0. Есть ли наибольшая мощность? Ответ укажет следующая теорема.

Теорема 3

Мощность булеана непустого множества больше мощности данного множества.

Доказательство

fi ( A) имеет подмножество {{a_i)) одноэлементного

множеств, эквивалентное А, поэтому b ( А) > А. Покажем, что А неэквивалентно b( А). Допустим противное: a е А « j( a) = C с А.

Возможны 2 и только 2 случая:

1. a ej( a); a - назовем элементом 1 -го типа.

2. ae j( a); тогда a - элемент 2-го типа.

Обозначим S -множество всех элементов 2-го типа; S « a₀ е А.

Какой же a₀ ? Если a₀ е S, то он 1 -го типа, но S из 2-го типа. Если a₀ e S, то тоже не получится, т. к. он будет 2-го типа и

должен войти в S. Противоречие, тогда А~ B ( А) и B ( А )> А. Теорема доказана.

Отсюда, очевидно, вытекает исключительно важный и интересный результат.

Следствие

Не существует наибольшей мощности.

Если А = n, то b ( А) имеет 2ⁿ элементов:

C0 = 1,0;

C_n¹ - одноэлементных; C_n² - 2 элементных;

Cnⁿ - все A.

Всего их C0 + C1 +... + Cⁿ_n = 2ⁿ.

Поэтому по аналогии, если A = a, то мощность булеана обозначают 2^a. Теорема 3 дает 2^a > a.

В связи с этим понятными становятся обозначения самого булеана: 2 ^A ,exp A.

Далее мы перейдем к рассмотрению бесконечных мощностей.

Начнем с мощности множества N натуральных чисел.