Cantor-Bernstein theorem

Arrows indicate images.

The Cantor – Bernstein theorem (in the English literature, the Cantor – Bernstein – Schröder theorem ) states that if there are injective mappings $f:A\to B$ ${\ displaystyle f: A \ to B}$ $f: A \ to B$ and $g:B\to A$ ${\ displaystyle g: B \ to A}$ ${\ displaystyle g: B \ to A}$ between sets $A$ ${\ displaystyle A}$ $A$ and $B$ ${\ displaystyle B}$ $B$ , then there is a one-to-one mapping $h:A\to B$ ${\ displaystyle h: A \ to B}$ ${\ displaystyle h: A \ to B}$ . In other words, that cardinality sets $A$ ${\ displaystyle A}$ $A$ and $B$ ${\ displaystyle B}$ $B$ match up:

|A|=|B|.

{\ displaystyle | A | = | B |.}

{\ displaystyle | A | = | B |.}

In other words, the theorem states the following:

Of ${\mathfrak {a}}\leqslant {\mathfrak {b}}$ ${\ displaystyle {\ mathfrak {a}} \ leqslant {\ mathfrak {b}}}$ ${\ displaystyle {\ mathfrak {a}} \ leqslant {\ mathfrak {b}}}$ and ${\mathfrak {b}}\leqslant {\mathfrak {a}}$ ${\ displaystyle {\ mathfrak {b}} \ leqslant {\ mathfrak {a}}}$ ${\ displaystyle {\ mathfrak {b}} \ leqslant {\ mathfrak {a}}}$ follows that ${\mathfrak {a}}={\mathfrak {b}},$ ${\ displaystyle {\ mathfrak {a}} = {\ mathfrak {b}},}$ ${\ displaystyle {\ mathfrak {a}} = {\ mathfrak {b}},}$ Where ${\mathfrak {a}},{\mathfrak {b}}$ ${\ displaystyle {\ mathfrak {a}}, {\ mathfrak {b}}}$ ${\ displaystyle {\ mathfrak {a}}, {\ mathfrak {b}}}$ - cardinal numbers .

Content

History

The theorem is named after Georg Cantor , Felix Bernstein and Ernst Schröder .

The initial proof used the axiom of choice , but this axiom is not necessary to prove this theorem.

Ernst Schroeder was the first to formulate a theorem, but published an incorrect proof. Independently, this theorem was formulated by Cantor. Cantor’s student Felix Bernstein published a dissertation containing completely correct proof.

Proof

Let be

C_{0}=A\setminus g(B),

{\ displaystyle C_ {0} = A \ setminus g (B),}

and

C_{n+1}=g(f(C_{n}))\quad

{\ displaystyle C_ {n + 1} = g (f (C_ {n})) \ quad}

at

n\geqslant 0

{\ displaystyle n \ geqslant 0}

and

C=\bigcup _{n=0}^{\infty }C_{n}.

{\ displaystyle C = \ bigcup _ {n = 0} ^ {\ infty} C_ {n}.}

Then, for any $x\in A$ ${\ displaystyle x \ in A}$ put

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

{\ 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.}

If a $x$ ${\ displaystyle x}$ does not lie in $C$ ${\ displaystyle C}$ then $x$ ${\ displaystyle x}$ should be in $g(B)$ ${\ displaystyle g (B)}$ (image of the set $B$ ${\ displaystyle B}$ under the action of the mapping $g$ ${\ displaystyle g}$ ) And then there is $g^{-1}(x)$ ${\ displaystyle g ^ {- 1} (x)}$ , and $h$ ${\ displaystyle h}$ display.

It remains to verify that $h:A\to B$ ${\ displaystyle h: A \ to B}$ - bijection.

Let us verify that h is surjection.

It is necessary to prove that $\forall y\in B\exists x\in A:h(x)=y$ ${\ displaystyle \ forall y \ in B \ exists x \ in A: h (x) = y}$
$\forall y\in B$ ${\ displaystyle \ forall y \ in B}$

$\mathrm {I} \ \ \$ ${\ displaystyle \ mathrm {I} \ \ \}$ If a $y\in f(C)$ ${\ displaystyle y \ in f (C)}$ then $\exists x\in Cf(x)=y$ ${\ displaystyle \ exists x \ in Cf (x) = y}$ . Then $h(x)=f(x)=y$ ${\ displaystyle h (x) = f (x) = y}$

$\mathrm {II} \;y\notin f(C)$ ${\ displaystyle \ mathrm {II} \; y \ notin f (C)}$
Let be $x=g(y)$ ${\ displaystyle x = g (y)}$ . Suppose $x\in C$ ${\ displaystyle x \ in C}$ . Then $x\in C_{n}$ ${\ displaystyle x \ in C_ {n}}$ at $n>0$ ${\ displaystyle n> 0}$ means $x\in g(f(C_{n-1}))$ ${\ displaystyle 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$ ${\ displaystyle \ Rightarrow \ exists c \ in C_ {n-1} {\ begin {matrix} x = g (f (c)) \\ x = g (y) \ end {matrix}} {\ Bigg \} } \ Rightarrow}$ , because $g$ ${\ displaystyle g}$ - injection then $y=f(c)\in f(C)$ ${\ displaystyle y = f (c) \ in f (C)}$ , which contradicts the assumption.
Means $x\notin C$ ${\ displaystyle x \ notin C}$ . Then $h(x)=g^{-1}(x)=g^{-1}(g(y))=y$ ${\ displaystyle h (x) = g ^ {- 1} (x) = g ^ {- 1} (g (y)) = y}$

We verify that h is an injection.

It is necessary to prove that $h(x_{1})=h(x_{2})\Rightarrow x_{1}=x_{2}$ ${\ displaystyle h (x_ {1}) = h (x_ {2}) \ Rightarrow x_ {1} = x_ {2}}$

$\mathrm {I} \;x_{1},x_{2}\in C$ ${\ displaystyle \ mathrm {I} \; x_ {1}, x_ {2} \ in C}$
$f(x_{1})=f(x_{2})\Rightarrow x_{1}=x_{2}$ ${\ displaystyle f (x_ {1}) = f (x_ {2}) \ Rightarrow x_ {1} = x_ {2}}$ ( $f$ ${\ displaystyle f}$ - injection)

$\mathrm {II} \;x_{1},x_{2}\notin C$ ${\ displaystyle \ 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}$ ${\ displaystyle 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$ ${\ 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}))\in C$ ${\ displaystyle x_ {2} = g (h (x_ {2})) = g (h (x_ {1})) = g (f (x_ {1})) \ in C}$ So this case is impossible.

Note

Display Definition $h$ ${\ displaystyle h}$ unconstructive above, i.e. there is no algorithm for determining in a finite number of steps whether some element lies $x$ ${\ displaystyle x}$ many $A$ ${\ displaystyle A}$ in the multitude $C$ ${\ displaystyle C}$ or not. Although for some special cases such an algorithm exists.

Literature

N.K. Vereshchagin, A. Shen. Lectures on mathematical logic and theory of algorithms. Part 1. The beginnings of set theory.

Ershov Yu. L., Palyutin EA. Mathematical logic: textbook. - 3rd, stereotype. ed. - St. Petersburg: "Doe", 2004. - 336 p.