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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Cantor-Bernstein.jpg

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

|A|=|B|.

Другими словами, теорема утверждает следующее:

Из \mathfrak{a} \leqslant \mathfrak{b} и \mathfrak{b} \leqslant \mathfrak{a} следует, что \mathfrak{a} = \mathfrak{b}, где \mathfrak{a}, \mathfrak{b}кардинальные числа.

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

Пусть

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

и

C_{n+1}=g[f[C_n]]\quad при 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 - сюрьекция.

Нужно доказать, что \forall y \in B \exists x \in A h(x)=y
\forall y \in B

\mathrm{I} \ \ \ Если y \in f(C), то \exists x \in C f(x) = y . Тогда h(x)=f(x)=y

\mathrm{II}\; y \notin f(C)
Пусть x=g(y). Предположим, x \in C. Тогда x \in C_n, при n>0, значит x \in g(f(C_{n-1})),
\Rightarrow \exists c \in C_{n-1}
\begin{matrix}
x=g(f(c))\\
x=g(y)
\end{matrix} \Bigg\} \Rightarrow , т. к. g - инъекция, то y=f(c) \in f(C), что противоречит предположению.
Значит x \notin  C. Тогда h(x)=g^{-1}(x)=g^{-1}(g(y))=y

Проверим, что h - инъекция.

Нужно доказать, что  h(x_1) = h(x_2) \Rightarrow x_1 = x_2

\mathrm{I}\; x_1,x_2 \in C
 f(x_1)=f(x_2) \Rightarrow x_1=x_2 ( f - инъекция)

\mathrm{II}\; x_1,x_2 \notin C
 g^{-1}(x_1)=g^{-1}(x_2) \Rightarrow x_1=g(g^{-1}(x_1))=g(g^{-1}(x_2))=x_2

\mathrm{III}\; x_1 \in C,x_2 \notin C
 h(x_1)=f(x_1), h(x_2)=g^{-1}(x_2)
h(x_1)=h(x_2)
x_2=g(h(x_2))=g(h(x_1))=g(f(x_1))\in C Значит этот случай невозможен.

Замечание[править | править вики-текст]

Определение отображения h выше неконструктивно, то есть не существует алгоритма определения за конечное число шагов, лежит ли некоторый элемент x множества A в множестве C или нет. Хотя для некоторых частных случаев такой алгоритм существует.

История[править | править вики-текст]

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

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

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

См. также[править | править вики-текст]

Литература[править | править вики-текст]

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