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

Материал из Википедии — свободной энциклопедии

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

|A| = |B|

[править] Доказательство

Пусть

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

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

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

Тогда, для любого x∈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 → B и есть искомое взаимооднозначное отображение.

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

[править] История

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

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