Теорема Кантора-Бернштейна: доказательство и смысл

Теорема Кантора-Бернштейна - рабочий инструмент теории множеств, который позволяет доказывать равномощность двух множеств, не строя между ними явную биекцию. Достаточно предъявить две инъекции - по одной в каждую сторону, - и теорема гарантирует, что нужное взаимно однозначное соответствие существует. Это резко упрощает доказательства: построить вложение почти всегда легче, чем сразу выписать биекцию. Ниже разберём точную формулировку, идею доказательства через цепочки элементов, классические примеры и места, где студенты чаще всего ошибаются. Если нужно разобрать конкретную задачу про мощности, соберите её в инструменте ниже.

Что утверждает теорема Кантора-Бернштейна

Теорема Кантора-Бернштейна (полное историческое название - теорема Кантора-Шрёдера-Бернштейна) формулируется так: если существует инъекция $f : A \to B$ и инъекция $g : B \to A$, то существует биекция $h : A \to B$. На языке мощностей это записывается компактно:

$|A| \le |B| \;\text{и}\; |B| \le |A| \;\Rightarrow\; |A| = |B|.$

Здесь запись $|A| \le |B|$ по определению означает «существует инъекция из $A$ в $B$», то есть $A$ можно вложить в $B$ без склеек. Теорема говорит, что отношение $\le$ на мощностях антисимметрично - ровно как обычное неравенство для чисел. Это и делает мощности множеств похожими на числа: их можно сравнивать, и из двух нестрогих неравенств в разные стороны следует равенство.

Принципиально важно, что доказательство теоремы Кантора-Бернштейна не использует аксиому выбора. Это отличает её от теоремы о трихотомии (любые две мощности сравнимы), которая без аксиомы выбора неверна. Поэтому теорема Кантора-Бернштейна - надёжный, конструктивный кирпич, на который можно опираться даже в осторожных основаниях математики.

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

Идея доказательства: разбиение на цепочки

Самое наглядное доказательство теоремы Кантора-Бернштейна разбивает оба множества на непересекающиеся цепочки и строит биекцию отдельно на каждой. Возьмём произвольный элемент и начнём его «раскручивать» назад: для $a \in A$ ищем его прообраз $g^{-1}(a)$ в $B$ (если он есть), затем прообраз того по $f$ в $A$, и так далее. Чередуя $f^{-1}$ и $g^{-1}$, мы движемся по элементам, пока на каком-то шаге прообраза не окажется - или пока цепочка не уйдёт в бесконечность.

По тому, чем заканчивается такая обратная цепочка, все элементы делятся на три типа:

$$\text{цепочки: }\; \begin{cases} \text{обрывается в } A, \\ \text{обрывается в } B, \\ \text{бесконечна (или циклична)}. \end{cases}$$

Для цепочек, которые обрываются в $A$, биекцию задаём через $f$; для обрывающихся в $B$ - через $g^{-1}$; для бесконечных и циклических подойдёт любая из стрелок, например снова $f$. Поскольку инъективность $f$ и $g$ гарантирует, что цепочки не пересекаются и покрывают всё множество, склейка кусочных биекций даёт единое взаимно однозначное соответствие $h : A \to B$. Это и есть искомая биекция.

Альтернативное доказательство через теорему Кнастера-Тарского

Есть второе, более короткое доказательство, использующее теорему о неподвижной точке. Рассмотрим отображение множеств $\varphi(S) = A \setminus g(B \setminus f(S))$, действующее на подмножествах $A$. Оно монотонно по включению: если $S_1 \subseteq S_2$, то $\varphi(S_1) \subseteq \varphi(S_2)$. По теореме Кнастера-Тарского у любого монотонного отображения на решётке подмножеств есть неподвижная точка $C$, то есть $\varphi(C) = C$.

Эта неподвижная точка задаёт нужное разбиение: на множестве $C$ биекцию строим как $f$, а на дополнении $A \setminus C$ - как $g^{-1}$. Аккуратная проверка показывает, что обе части согласуются на границе и вместе дают биекцию $h$. Это доказательство компактнее, но менее наглядно, чем разбиение на цепочки. Идея неподвижной точки роднит теорему Кантора-Бернштейна с другими результатами анализа - например, со схожими по духу рассуждениями вокруг теоремы Кантора о равномерной непрерывности, где компактность тоже «склеивает» локальное в глобальное.

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

Классические примеры применения

Главная ценность теоремы Кантора-Бернштейна - в задачах, где прямая биекция громоздка. Несколько канонических случаев.

Отрезок и интервал. Чтобы доказать $|[0, 1]| = |(0, 1)|$, явная биекция требует ухищрений со счётной перестановкой точек. С теоремой всё просто: тождественное вложение $(0,1) \hookrightarrow [0,1]$ даёт одну инъекцию, а $x \mapsto \tfrac{1}{4} + \tfrac{x}{2}$ вкладывает $[0,1]$ внутрь $(0,1)$ - вторую. Двух инъекций достаточно.

Отрезок и квадрат. Знаменитый результат $|[0,1]| = |[0,1]^2|$ (отрезок равномощен квадрату) удобно получать именно так. Инъекция $[0,1] \to [0,1]^2$ очевидна: $x \mapsto (x, 0)$. Обратная инъекция $[0,1]^2 \to [0,1]$ строится перемешиванием десятичных разрядов двух координат - это вложение, и оно инъективно. Биекцию напрямую выписывать мучительно из-за неоднозначности десятичных записей вида $0{,}4999\ldots = 0{,}5000\ldots$, а теорема Кантора-Бернштейна обходит проблему.

Степени континуума. Равенства вроде $|\mathbb{R}| = |\mathbb{R}^n|$ или $|\mathbb{R}| = |2^{\mathbb{N}}|$ доказываются по той же схеме: строим два простых вложения и ссылаемся на теорему. Это стандартный приём при работе с мощностью континуума.

Почему нужны именно инъекции

Распространённое заблуждение - будто для равномощности годятся любые отображения «в обе стороны». Нет: теорема требует именно инъекций. Сюръекции тоже дают информацию о мощностях, но в обратную сторону: если есть сюръекция $A \to B$, то $|B| \le |A|$ (при наличии аксиомы выбора). Двойная сюръекция $A \twoheadrightarrow B$ и $B \twoheadrightarrow A$ влечёт равномощность лишь как следствие, опираясь на аксиому выбора, тогда как вариант с инъекциями работает без неё.

Связь с обратными функциями стоит проговорить. Инъекция $f : A \to B$ - это вложение: разные элементы $A$ переходят в разные элементы $B$, и на образе $f(A)$ корректно определена обратная $f^{-1}$. Именно поэтому в доказательстве через цепочки мы свободно пользуемся $f^{-1}$ и $g^{-1}$ - на образах они однозначны. Если бы $f$ склеивала точки, обратной не было бы, и вся конструкция рассыпалась.

Полезно держать в голове геометрическую картинку. Инъекция $g : B \to A$ переносит копию всего $B$ внутрь $A$, занимая там лишь часть - образ $g(B)$. Аналогично $f$ укладывает копию $A$ внутрь $B$. Получаются вложенные «матрёшки» убывающих образов, и именно вдоль них раскручиваются цепочки из доказательства. Когда цепочка обрывается, она упирается в элемент, у которого нет прообраза, - то есть в точку, не попавшую в очередной вложенный образ. Этот образ-в-образе и есть скелет всей конструкции: он показывает, что хотя каждое вложение «не дотягивает» до целого множества, вместе две стрелки точно покрывают обе стороны без потерь и пересечений.

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

• Путают теорему Кантора-Бернштейна с теоремой Кантора. Это разные результаты: теорема Кантора утверждает $|A| < |2^A|$ (множество строго меньше своего булеана), а теорема Кантора-Бернштейна - про антисимметрию $\le$. Названия похожи, смысл разный.
• Берут сюръекции вместо инъекций. Формулировка завязана именно на вложения. Подмена ломает доказательство и тянет за собой аксиому выбора.
• Пытаются предъявить явную биекцию. Это лишняя работа: теорема существование биекции гарантирует, строить её руками не нужно - достаточно двух инъекций.
• Считают, что нужна аксиома выбора. Доказательство теоремы Кантора-Бернштейна полностью конструктивно и от аксиомы выбора не зависит.
• Забывают проверить инъективность одного из вложений. Если хотя бы одно отображение склеивает точки, оно не инъекция, и теорема неприменима - равномощность из таких отображений не следует.

FAQ

Нужна ли для теоремы Кантора-Бернштейна аксиома выбора? Нет. Оба классических доказательства - через разбиение на цепочки и через теорему Кнастера-Тарского о неподвижной точке - полностью конструктивны и аксиому выбора не используют. Именно поэтому теорема считается «безопасной» и применимой в любых основаниях.

Чем теорема Кантора-Бернштейна отличается от теоремы Кантора? Теорема Кантора показывает, что мощность множества строго меньше мощности его множества подмножеств: $|A| < |2^A|$. Теорема Кантора-Бернштейна - про сравнение двух мощностей: из $|A| \le |B|$ и $|B| \le |A|$ следует $|A| = |B|$. Общее у них только имя Кантора.

Можно ли так доказать, что отрезок равномощен всей плоскости? Да. Инъекция отрезка в плоскость очевидна ($x \mapsto (x,0)$), а инъекция плоскости в отрезок строится перемешиванием цифр координат. Две инъекции по теореме Кантора-Бернштейна дают биекцию, то есть $|[0,1]| = |\mathbb{R}^2|$.

Коротко

Теорема Кантора-Бернштейна сводит доказательство равномощности к построению двух инъекций: если $A$ вкладывается в $B$ и $B$ вкладывается в $A$, то между ними существует биекция, и $|A| = |B|$. Доказывается разбиением на цепочки или через неподвижную точку, не требует аксиомы выбора и служит главным рабочим приёмом при сравнении бесконечных мощностей - от отрезка и квадрата до степеней континуума.