Теорема Кантора — Бернштейна

Теорема Кантора — Бернштейна

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

| A | = | B | .

Неформально говоря, теорема утверждает следующее:

Из $\alpha \leqslant \beta$ и $\beta\leqslant\alpha$, следует, что α = β.

Утверждение теоремы является очевидным, если под α и β подразумеваются действительные числа, однако теорема ведёт речь о кардинальных числах.

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

Пусть

$C_0=A\setminus g[B],\!$

и

$C_{n+1}=g[f[C_n]]\quad \mbox{ for }n\geqslant 0$

и

$C=\bigcup_{n=0}^\infty C_n.$

Тогда, для любого $x\in A$ положим

$h(x)=\left\{ \begin{matrix} f(x) & \,\,\mbox{if }x\in C \\ g^{-1}(x) & \mbox{if }x\not\in C \end{matrix} \right.$

Если x не лежит в C, тогда x должен быть в g[B] (образе множества B под действием отображения g). И тогда существует g ^{− 1}(x), и h корректно определённое взаимооднозначное отображение (биекция).

Можно проверить, что $h:A\to B$ и есть искомое взаимооднозначное отображение.

Заметим, что это определение отображения h неконструктивно в том смысле, что не существует общего алгоритма определения за конечное число шагов для любых заданных множеств A, B и инъекций f, g, лежит ли некоторый элемент x множества A в множестве C или нет. Хотя для некоторых частных случаев, такой алгоритм существует.

История

Теорема названа в честь Георга Кантора, Феликса Бернштейна и Эрнста Шрёдера

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

Эрнст Шрёдер первым сформулировал теорему, но опубликовал неправильное доказательство. Независимо эта теорема была сформулирована Кантором. Ученик Кантора Феликс Бернштейн опубликовал диссертацию, содержащую полностью корректное доказательство.

См. также

• Эрнст Шрёдер
• Георг Кантор
• Феликс Бернштейн
• Теория множеств
• Кардинальное число

Литература

• Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств.

• Ершов Ю. Л., Палютин Е. А. Математическая логика: Учебное пособие. — 3-е, стереотип. изд. — СПб.: «Лань», 2004. — 336 с.