Стрелки показывают отображения. Теоре́ма Ка́нтора — Бернште́йна (в англ. литературе теоре́ма Ка́нтора — Бернште́йна — Шрёдера ), утверждает, что если существуют инъективные отображения
f
:
A
→
B
{\displaystyle f:A\to B}
g
:
B
→
A
{\displaystyle g:B\to A}
множествами
A
{\displaystyle A}
B
{\displaystyle B}
взаимооднозначное отображение
h
:
A
→
B
{\displaystyle h:A\to B}
мощности множеств
A
{\displaystyle A}
B
{\displaystyle B}
|
A
|
=
|
B
|
.
{\displaystyle |A|=|B|.}
Другими словами, теорема утверждает следующее:
Из
a
⩽
b
{\displaystyle {\mathfrak {a}}\leqslant {\mathfrak {b}}}
b
⩽
a
{\displaystyle {\mathfrak {b}}\leqslant {\mathfrak {a}}}
a
=
b
,
{\displaystyle {\mathfrak {a}}={\mathfrak {b}},}
a
,
b
{\displaystyle {\mathfrak {a}},{\mathfrak {b}}}
кардинальные числа .
Теорема названа в честь Георга Кантора , Феликса Бернштейна и Эрнста Шрёдера .
Первоначальное доказательство использовало аксиому выбора , однако эта аксиома необязательна для доказательства данной теоремы.
Эрнст Шрёдер первым сформулировал теорему, но опубликовал неправильное доказательство.
Независимо эта теорема была сформулирована Кантором. Ученик Кантора Феликс Бернштейн опубликовал диссертацию, содержащую полностью корректное доказательство.
Пусть
C
0
=
A
∖
g
(
B
)
,
{\displaystyle C_{0}=A\setminus g(B),}
и
C
n
+
1
=
g
(
f
(
C
n
)
)
{\displaystyle C_{n+1}=g(f(C_{n}))\quad }
n
⩾
0
{\displaystyle n\geqslant 0}
и
C
=
⋃
n
=
0
∞
C
n
.
{\displaystyle C=\bigcup _{n=0}^{\infty }C_{n}.}
Тогда для любого
x
∈
A
{\displaystyle x\in A}
h
(
x
)
=
{
f
(
x
)
if
x
∈
C
g
−
1
(
x
)
if
x
∉
C
{\displaystyle 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
{\displaystyle x}
C
{\displaystyle C}
x
{\displaystyle x}
g
(
B
)
{\displaystyle g(B)}
B
{\displaystyle B}
g
{\displaystyle g}
g
−
1
(
x
)
{\displaystyle g^{-1}(x)}
h
{\displaystyle h}
Осталось проверить, что
h
:
A
→
B
{\displaystyle h:A\to B}
Проверим, что h — сюръекция.
Нужно доказать, что
∀
y
∈
B
∃
x
∈
A
:
h
(
x
)
=
y
{\displaystyle \forall y\in B\exists x\in A:h(x)=y}
∀
y
∈
B
{\displaystyle \forall y\in B}
I
{\displaystyle \mathrm {I} \ \ \ }
y
∈
f
(
C
)
{\displaystyle y\in f(C)}
∃
x
∈
C
f
(
x
)
=
y
{\displaystyle \exists x\in Cf(x)=y}
h
(
x
)
=
f
(
x
)
=
y
{\displaystyle h(x)=f(x)=y}
I
I
y
∉
f
(
C
)
{\displaystyle \mathrm {II} \;y\notin f(C)}
x
=
g
(
y
)
{\displaystyle x=g(y)}
x
∈
C
{\displaystyle x\in C}
x
∈
C
n
{\displaystyle x\in C_{n}}
n
>
0
{\displaystyle n>0}
x
∈
g
(
f
(
C
n
−
1
)
)
{\displaystyle x\in g(f(C_{n-1}))}
⇒
∃
c
∈
C
n
−
1
x
=
g
(
f
(
c
)
)
x
=
g
(
y
)
}
⇒
{\displaystyle \Rightarrow \exists c\in C_{n-1}{\begin{matrix}x=g(f(c))\\x=g(y)\end{matrix}}{\Bigg \}}\Rightarrow }
g
{\displaystyle g}
y
=
f
(
c
)
∈
f
(
C
)
{\displaystyle y=f(c)\in f(C)}
x
∉
C
{\displaystyle x\notin C}
h
(
x
)
=
g
−
1
(
x
)
=
g
−
1
(
g
(
y
)
)
=
y
{\displaystyle h(x)=g^{-1}(x)=g^{-1}(g(y))=y}
Проверим, что h — инъекция.
Нужно доказать, что
h
(
x
1
)
=
h
(
x
2
)
⇒
x
1
=
x
2
{\displaystyle h(x_{1})=h(x_{2})\Rightarrow x_{1}=x_{2}}
I
x
1
,
x
2
∈
C
{\displaystyle \mathrm {I} \;x_{1},x_{2}\in C}
f
(
x
1
)
=
f
(
x
2
)
⇒
x
1
=
x
2
{\displaystyle f(x_{1})=f(x_{2})\Rightarrow x_{1}=x_{2}}
f
{\displaystyle f}
I
I
x
1
,
x
2
∉
C
{\displaystyle \mathrm {II} \;x_{1},x_{2}\notin C}
g
−
1
(
x
1
)
=
g
−
1
(
x
2
)
⇒
x
1
=
g
(
g
−
1
(
x
1
)
)
=
g
(
g
−
1
(
x
2
)
)
=
x
2
{\displaystyle g^{-1}(x_{1})=g^{-1}(x_{2})\Rightarrow x_{1}=g(g^{-1}(x_{1}))=g(g^{-1}(x_{2}))=x_{2}}
I
I
I
x
1
∈
C
,
x
2
∉
C
{\displaystyle \mathrm {III} \;x_{1}\in C,x_{2}\notin C}
h
(
x
1
)
=
f
(
x
1
)
,
h
(
x
2
)
=
g
−
1
(
x
2
)
{\displaystyle h(x_{1})=f(x_{1}),h(x_{2})=g^{-1}(x_{2})}
h
(
x
1
)
=
h
(
x
2
)
{\displaystyle h(x_{1})=h(x_{2})}
x
2
=
g
(
h
(
x
2
)
)
=
g
(
h
(
x
1
)
)
=
g
(
f
(
x
1
)
)
∈
C
{\displaystyle x_{2}=g(h(x_{2}))=g(h(x_{1}))=g(f(x_{1}))\in C}
Определение отображения
h
{\displaystyle h}
неконструктивно , то есть не существует алгоритма определения за конечное число шагов, лежит ли некоторый элемент
x
{\displaystyle x}
A
{\displaystyle A}
C
{\displaystyle C}
Ершов Ю. Л., Палютин Е. А. Математическая логика: Учебное пособие. — 3-е, стереотип. изд. — СПб.: «Лань», 2004. — 336 с. 
