Теорема Кантора о мощности множества: P(A) больше A

Интуиция подсказывает, что бесконечность одна на всех: раз множество натуральных чисел бесконечно, то и любое другое бесконечное множество «такое же большое». Георг Кантор показал, что это не так. Его теорема о мощности множества утверждает простую и при этом разрушительную для наивной интуиции вещь: множество всех подмножеств всегда строго больше исходного множества, даже если оно бесконечно. Значит, бесконечностей не одна, а целая бесконечная башня. Ниже разберём точную формулировку, классическое доказательство диагональным методом и следствия, из-за которых не существует «множества всех множеств».

Что утверждает теорема Кантора

Для любого множества $A$ его булеан (множество всех подмножеств) обозначают $\mathcal{P}(A)$ или $2^A$. Теорема Кантора звучит так:

$$|A| < |\mathcal{P}(A)|$$

То есть мощность булеана строго больше мощности самого множества, и это верно для любого $A$ - конечного, счётного или несчётного.

Для конечного множества это очевидно: если в $A$ ровно $n$ элементов, то подмножеств у него $2^n$, а $2^n > n$ при любом натуральном $n$. Сила теоремы в том, что неравенство сохраняется и для бесконечных множеств, где наивный подсчёт «по элементам» не работает. Именно здесь обычная интуиция отказывает: кажется, что бесконечность нельзя «превзойти», но Кантор показывает, как именно.

Напомним, что равенство мощностей $|A| = |B|$ означает существование биекции между $A$ и $B$, а $|A| \le |B|$ - существование инъекции из $A$ в $B$. Строгое неравенство $|A| < |\mathcal{P}(A)|$ означает: инъекция $A \to \mathcal{P}(A)$ есть, а вот биекции - нет ни одной.

Половина простая: инъекция всегда существует

Чтобы доказать $|A| \le |\mathcal{P}(A)|$, достаточно предъявить инъекцию. Она очевидна: каждому элементу $a \in A$ сопоставим одноэлементное подмножество $\{a\} \in \mathcal{P}(A)$.

$$f\colon A \to \mathcal{P}(A), \qquad f(a) = \{a\}$$

Разным элементам соответствуют разные одноэлементные множества, так что $f$ инъективна. Эта половина не вызывает споров и работает для любого множества. Вся трудность - во второй половине: нужно показать, что никакая функция из $A$ в $\mathcal{P}(A)$ не может быть сюръективной, а значит, и биективной.

Рассчитать для своей задачи

Диагональный аргумент: ядро доказательства

Допустим противное: пусть существует сюръекция $g\colon A \to \mathcal{P}(A)$, то есть каждое подмножество $A$ есть образ какого-то элемента. Построим «диагональное» подмножество, которое не может быть ничьим образом, и придём к противоречию.

Определим множество тех элементов, которые не входят в сопоставленное им подмножество:

$$D = \{\, a \in A \mid a \notin g(a) \,\}$$

Это корректное подмножество $A$, значит $D \in \mathcal{P}(A)$. Раз $g$ - сюръекция, найдётся элемент $d \in A$ такой, что $g(d) = D$. Зададим вопрос: принадлежит ли $d$ множеству $D$?

$$d \in D \iff d \notin g(d) = D$$

Получаем $d \in D \iff d \notin D$ - прямое противоречие. Элемент одновременно и принадлежит, и не принадлежит $D$. Значит, исходное допущение о существовании сюръекции ложно. Сюръекции $A \to \mathcal{P}(A)$ не существует, тем более не существует биекции, поэтому $|A| < |\mathcal{P}(A)|$. Теорема доказана.

Этот приём называют диагональным методом: он же лежит в основе доказательства несчётности отрезка $[0,1]$, где Кантор «портит» $n$-й знак $n$-го числа в гипотетическом списке. Тот же механизм самоприменения работает и здесь - множество $D$ описывает «парадоксальный» элемент, который ускользает от любого назначения.

Рассчитать для своей задачи

Связь с двоичными последовательностями

Почему булеан обозначают именно $2^A$? Каждое подмножество $S \subseteq A$ однозначно задаётся своей характеристической функцией:

$$\chi_S\colon A \to \{0,1\}, \qquad \chi_S(a) = \begin{cases} 1, & a \in S \\ 0, & a \notin S \end{cases}$$

Подмножества $A$ и функции из $A$ в двухэлементное множество $\{0,1\}$ - это одно и то же, поэтому $|\mathcal{P}(A)| = 2^{|A|}$. Для счётного $A = \mathbb{N}$ подмножество - это бесконечная двоичная строка из нулей и единиц, а таких строк, как показывает та же диагональ, несчётно много. Так теорема Кантора напрямую даёт несчётность множества всех двоичных последовательностей и, через двоичную запись, несчётность отрезка вещественных чисел.

Следствия: башня бесконечностей и парадокс Кантора

Главное следствие - не существует наибольшей мощности. Применяя теорему к самому булеану, получаем строго возрастающую цепочку:

$$|A| < |\mathcal{P}(A)| < |\mathcal{P}(\mathcal{P}(A))| < \cdots$$

Стартовав с $\mathbb{N}$, мы строим бесконечную иерархию всё более «крупных» бесконечностей: счётная $\aleph_0$, мощность континуума $2^{\aleph_0}$, затем $2^{2^{\aleph_0}}$ и так далее. Кантор обозначил бесконечные мощности кардиналами $\aleph_0, \aleph_1, \dots$; вопрос о том, совпадает ли $2^{\aleph_0}$ с $\aleph_1$, - это знаменитая континуум-гипотеза, не разрешимая средствами стандартной аксиоматики.

Второе следствие - парадокс Кантора: не существует «множества всех множеств». Если бы такое универсальное множество $U$ существовало, то его булеан $\mathcal{P}(U)$ был бы строго мощнее $U$. Но всякое подмножество $U$ само является множеством, то есть элементом $U$, значит $\mathcal{P}(U) \subseteq U$ и $|\mathcal{P}(U)| \le |U|$ - противоречие с теоремой. Именно эта трудность подтолкнула к аксиоматической теории множеств (Цермело - Френкеля), где «множество всех множеств» просто запрещено схемой выделения. Теорема Кантора тесно связана с теоремой Кантора-Бернштейна, которая, наоборот, даёт критерий равенства мощностей.

Как это выглядит на конкретных примерах

Чтобы теорема перестала быть абстрактной, полезно прогнать её на знакомых множествах. Это помогает увидеть, где именно ломается наивное «бесконечность одна».

Возьмём множество из трёх элементов $A = \{1, 2, 3\}$. Его подмножества: пустое, три одноэлементных, три двухэлементных и само $A$ - итого $2^3 = 8$ штук. Восемь больше трёх, неравенство $|A| < |\mathcal{P}(A)|$ налицо. Никакая функция из трёх элементов не «накроет» все восемь подмножеств просто потому, что их больше.

Теперь счётный случай $A = \mathbb{N} = \{0, 1, 2, \dots\}$. Здесь $\mathcal{P}(\mathbb{N})$ - множество всех подмножеств натурального ряда, равномощное множеству бесконечных двоичных строк и, как следствие, всему отрезку $[0,1]$. По теореме оно строго мощнее $\mathbb{N}$: перенумеровать все подмножества натуральных чисел невозможно, как ни старайся. Это и есть знаменитый переход от счётного к континууму - наглядно работающий на множестве операций над множествами, но дающий принципиально новую, большую бесконечность.

Полезно проследить, что именно делает диагональное множество $D$ в счётном случае. Если бы кто-то предъявил «список» всех подмножеств $\mathbb{N}$, занумерованный самими натуральными числами, то $D$ собрало бы ровно те номера $a$, которые не лежат в $a$-м подмножестве списка. Тогда $D$ отличается от каждого подмножества списка хотя бы в одной позиции - по диагонали. Значит, $D$ в списке нет, и список неполон. Любая попытка нумерации проваливается по той же причине.

Частые ошибки

• Путают $\mathcal{P}(A)$ с самим $A$. Булеан - это множество подмножеств, а не множество элементов. Даже для пустого множества $\mathcal{P}(\varnothing) = \{\varnothing\}$ содержит один элемент.
• Считают, что для бесконечных множеств теорема «очевидна по $2^n$». Формула $2^n > n$ работает только в конечном случае; для бесконечных множеств нужен именно диагональный аргумент, а не подсчёт.
• Думают, что все бесконечности равны. Это и есть главное заблуждение, которое теорема опровергает: $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| = |\mathbb{R}|$.
• Забывают про строгость неравенства. Инъекция $A \to \mathcal{P}(A)$ есть всегда, но обратной инъекции (а тем более биекции) нет - без этого «строго» теорема теряет смысл.
• Смешивают $D$ с конкретным множеством. $D$ зависит от гипотетической функции $g$; это не фиксированное множество, а инструмент для получения противоречия.

FAQ

Работает ли теорема Кантора для конечных множеств? Да. Для множества из $n$ элементов булеан содержит $2^n$ подмножеств, и $2^n > n$ при любом $n \ge 0$. Просто в конечном случае это видно прямым подсчётом, а вся ценность теоремы - в распространении неравенства на бесконечные множества.

Чем теорема Кантора отличается от диагонального доказательства несчётности $\mathbb{R}$? Это одна и та же идея в разных обёртках. Несчётность $[0,1]$ - частный случай: множество двоичных последовательностей равномощно $\mathcal{P}(\mathbb{N})$, а оно строго мощнее $\mathbb{N}$. Общая теорема о мощности множества формулирует диагональный приём для произвольного $A$.

Почему из теоремы следует, что нет множества всех множеств? Если бы универсальное множество $U$ существовало, его подмножества были бы его же элементами, откуда $|\mathcal{P}(U)| \le |U|$. Но теорема даёт $|U| < |\mathcal{P}(U)|$ - противоречие. Поэтому в аксиоматике ZF такого множества нет.

Коротко

Теорема Кантора утверждает, что мощность булеана $\mathcal{P}(A)$ строго больше мощности самого $A$ для любого множества: инъекция $a \mapsto \{a\}$ существует, а сюръекция - нет, что показывает диагональное множество $D = \{a \mid a \notin g(a)\}$. Отсюда - бесконечная башня всё больших бесконечностей и отсутствие наибольшей мощности, а заодно парадокс Кантора, запрещающий «множество всех множеств».