Сравнение мощностей множеств: теорема Кантора—Бернштейна и теоремы Кантора о мощности множества подмножеств

Для сравнения мощностей говорят \(\lvert A\rvert\le\lvert B\rvert\), если существует инъекция \(A\to B\). Теорема Кантора—Бернштейна утверждает: если \(\lvert A\rvert\le\lvert B\rvert\) и \(\lvert B\rvert\le\lvert A\rvert\), то \(A\) и \(B\) равномощны.¹

Через \(2^A\), или \(\mathcal P(A)\), обозначают булеан множества \(A\), то есть множество всех его подмножеств. Теорема Кантора утверждает, что \(A\) не равномощно \(\mathcal P(A)\). Отображение \(a\mapsto\{a\}\) задаёт инъекцию \(A\to\mathcal P(A)\), поэтому \(\lvert A\rvert<\lvert\mathcal P(A)\rvert\). Невозможность сюръекции \(A\to\mathcal P(A)\) доказывается диагональным построением \(M=\{a\in A\mid a\notin f(a)\}\).¹

Что важно запомнить

\(\lvert A\rvert\le\lvert B\rvert\) означает существование инъекции \(A\to B\).
Инъекции в обе стороны дают равномощность по теореме Кантора—Бернштейна.
\(2^A\), или \(\mathcal P(A)\), — булеан множества \(A\).
Отображение \(a\mapsto\{a\}\) является инъекцией \(A\to\mathcal P(A)\).
Диагональный аргумент исключает даже сюръекцию \(A\to\mathcal P(A)\).
Следовательно, \(\lvert A\rvert<\lvert\mathcal P(A)\rvert\).

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

Мощность \(A\) считают не большей мощности \(B\), если существует инъекция \(A\to B\). Это записывают как \(\lvert A\rvert\le\lvert B\rvert\). Теорема Кантора—Бернштейна, которую также называют теоремой Кантора—Шрёдера—Бернштейна, утверждает, что из инъекций \(f:A\to B\) и \(g:B\to A\) следует существование биекции \(A\to B\). Значит, \(\lvert A\rvert=\lvert B\rvert\).¹

Идея доказательства Кантора—Бернштейна

Пусть даны инъекции \(f:A\to B\) и \(g:B\to A\). Положим \(A_0=A\), \(A_1=g(B)\), \(A_2=g(f(A))\). Тогда \(A_2\subseteq A_1\subseteq A_0\). Отображение \(h=g\circ f\) является биекцией \(A_0\) на \(A_2\). Достаточно построить биекцию \(A_0\to A_1\). Если рассматривать \(g\) как биекцию \(B\to A_1=g(B)\), у неё есть обратная функция \(g^{-1}:A_1\to B\). Поэтому композиция построенной биекции \(A_0\to A_1\) с \(g^{-1}\) даст биекцию \(A\to B\).¹

Определим \(A_{n+2}=h(A_n)\) и слои \(C_n=A_n\setminus A_{n+1}\). Пусть \(D\) является пересечением всех \(A_n\). Отображение \(h\) переводит каждый чётный слой \(C_{2n}\) биективно в \(C_{2n+2}\). На нечётных слоях и на \(D\) оставим элементы на месте. Полученное отображение является биекцией \(A_0\to A_1\), что завершает доказательство.¹

Теорема Кантора о множестве подмножеств

Через \(2^A\), или \(\mathcal P(A)\), обозначают булеан множества \(A\), то есть множество всех его подмножеств. Теорема Кантора утверждает, что сюръекции \(A\to\mathcal P(A)\) не существует, а значит, не существует и биекции. Предположим обратное и пусть \(f:A\to\mathcal P(A)\) сюръективно. Рассмотрим

\[M=\{a\in A\mid a\notin f(a)\}.\]

Так как \(M\subseteq A\), существует \(b\in A\) с \(f(b)=M\). Если \(b\in M\), то по определению \(M\) получаем \(b\notin f(b)=M\). Если \(b\notin M\), то по тому же определению \(b\in f(b)=M\). Оба варианта приводят к противоречию. С другой стороны, отображение \(a\mapsto\{a\}\) инъективно. Следовательно, \(A\) по мощности строго меньше \(\mathcal P(A)\): \(\lvert A\rvert\lt\lvert\mathcal P(A)\rvert\).¹

Пример простыми словами

Для \(A=\{1,2\}\) множество \(\mathcal P(A)\) состоит из \(\varnothing\), \(\{1\}\), \(\{2\}\), \(\{1,2\}\). Уже в конечном случае видно увеличение числа элементов. Теорема Кантора утверждает такое строгое увеличение мощности для любого множества.¹

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

Считать две исходные инъекции в теореме Кантора—Бернштейна взаимно обратными.
Путать \(\mathcal P(A)\) с декартовым квадратом \(A\times A\).
В диагональном доказательстве забывать, что \(M\subseteq A\).
Делать вывод \(\lvert A\rvert<\lvert\mathcal P(A)\rvert\) только из отсутствия биекции, не предъявив инъекцию \(A\to\mathcal P(A)\).

Другие вопросы

Источники

1 Бегунц А. В., Шапошников С. В. Примерный конспект курса математического анализа Первый семестр. Механико-математический факультет МГУ имени М. В. Ломоносова, 2018 г. С. 10–11.