Множества мощности континуум

Рассмотрим одну из возможных процедур, позволяющую получать множества с мощностью, превышающей некоторую исходную.

Определение. Множеством всех подмножеств или булеаном множества М называют множество, состоящее из всех подмножеств М. Обозначают его через [M].

Пример 1. М = {a, b}. [М] = {Æ, a, b, (a, b)}.

Пример 2. М = {1, 2, 3}. [М] = {Æ, 1, 2, 3, (1, 2), (1, 3), (2, 3), (1, 2, 3)}.

У конечных множеств М мощность [М] равна 2^½М½. Поэтому для множества всех подмножеств (булеана) также применяют обозначение 2^М.

Пример 3. М = N = {1, 2, 3, ...}. В [М] войдут:

а) нулевой элемент Æ;

б) все натуральные числа поодиночке;

в) все возможные их сочетания по 2, 3, 4 и т. д. (конечной длины);

г) все возможные сочетания натуральных чисел счетной длины.

Теорема 2.4 (Г.Кантор). При М ¹ Æсправедливо: ½M½<½[М]½, т.е. мощность любого непустого множества М меньше мощности множества его подмножеств.

Доказательство. Для конечных множеств утверждение очевидно, т.к. при n ³1 выполняется условие n <2ⁿ.

Рассмотрим бесконечные множества. Так как М Ì [М], то всегда½M½£½[М]½. Докажем утверждение теоремы от противного. Допустим,½M½=½[М]½. По определению эквивалентности множеств это означает, что существует взаимно однозначное отображение f:M®[М], которое каждому элементу а Î М ставит в соответствие некоторое подмножество А Í [М].

Анализируя все элементы а Î М и их образы f(а) = А Í [М], строим вспомогательное множество Х следующим образом: если а не входит в свой образ, а Ï f(а), то а включается в Х.

Множество Х Î [М], поскольку [М] содержит все возможные подмножества М. Так как f — взаимно однозначное отображение, то для Х должен существовать элемент х Î М, такой, что f ^–1 : Х® х, f(х) = Х.

Для элемента х есть только две возможности: a) хÎX, б) хÏ Х. Допустим, верно а). Так как х содержится в своем образе, то он не должен входить в X, хÏХ. В случае б) также получаем противоречие, поскольку х по алгоритму должен быть включён в Х. Полученное противоречие показывает, что f ^-1 на множестве Х не определено, следовательно, взаимно однозначное отображение f: M ® [М] не существует и ½M½¹½[М]½. Следовательно, ½M½<½[М]½.