Teorema de Cantor-Bernstein

El teorema de Cantor-Bernstein (en la literatura inglesa, el teorema de Cantor-Bernstein-Schroeder ), establece que si hay aplicaciones inyectivas y entre los conjuntos y , entonces hay una aplicación uno a uno . En otras palabras, que las cardinalidades de los conjuntos y coincidan: $f:A\a B$ ${\ estilo de visualización g: B \ a A}$ $A$ $B$ $h:A\a B$ $A$ $B$

{\ estilo de visualización | A | = | B |.}

En otras palabras, el teorema establece lo siguiente:

Se sigue de y de donde son los números cardinales . ${\mathfrak {a}}\leqslant {\mathfrak {b}}$ ${\mathfrak {b}}\leqslant {\mathfrak {a}}$ ${\mathfrak{a}}={\mathfrak{b}},$ ${\mathfrak {a)],{\mathfrak {b))$

Historia

El teorema lleva el nombre de Georg Cantor , Felix Bernstein y Ernst Schröder .

La prueba original usaba el axioma de elección , sin embargo, este axioma no es necesario para la prueba de este teorema.

Ernst Schröder fue el primero en formular el teorema, pero publicó una demostración incorrecta. Este teorema fue formulado de forma independiente por Cantor. El alumno de Cantor, Felix Bernstein, publicó una disertación que contenía una prueba completamente correcta.

Prueba

Dejar

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

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

n\geqslant 0

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

Entonces para cualquiera ponemos $x \ en A$

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

Si no está en , entonces debe estar en (la imagen del conjunto bajo la acción del mapeo ). Y luego existe , y el mapeo. $X$ $C$ $X$ ${\ estilo de visualización g (B)}$ $B$ $gramo$ ${\ estilo de visualización g^{-1} (x)}$ $h$

Queda por comprobar que es una biyección. $h:A\a B$

Verifiquemos que h es una sobreyección.

Necesitamos demostrar que $\forall y\in B\existe x\in A:h(x)=y$
${\ estilo de visualización \ para todos y \ en B}$

${\ estilo de visualización \ mathrm {yo} \ \ \ }$ Si , entonces . Después ${\ estilo de visualización y \ en f (C)}$ $\existe x\in Cf(x)=y$ ${\ estilo de visualización h (x) = f (x) = y}$

$\mathrm {II} \;y\notin f(C)$
deja _ Supongamos . Entonces , para , significa , ya que es una inyección, lo que contradice la suposición. Entonces _ Después ${\ estilo de visualización x = g (y)}$ ${\ estilo de visualización x \ en C}$ ${\ estilo de visualización x \ en C_ {n}}$ $n>0$ ${\ estilo de visualización x \ en g (f (C_ {n-1}))}$
$\Rightarrow \existe c\en C_{n-1}{\begin{matriz}x=g(f(c))\\x=g(y)\end{matriz}}{\Bigg \} }\Flecha correcta$ $gramo$ ${\ estilo de visualización y = f (c) \ en f (C)}$
${\ estilo de visualización x \ no en C}$ $h(x)=g^{-1}(x)=g^{-1}(g(y))=y$

Comprobemos que h es una inyección.

Necesitamos demostrar que $h(x_{1})=h(x_{2})\flecha derecha x_{1}=x_{2}$

$\mathrm {I} \;x_{1},x_{2}\en C$
$f(x_{1})=f(x_{2})\flecha derecha x_{1}=x_{2}$ ( - inyección) $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}\en C,x_{2}\noten C$
$h(x_{1})=f(x_{1}),h(x_{2})=g^{-1}(x_{2})$
${\ estilo de visualización h (x_ {1}) = h (x_ {2})}$
$x_{2}=g(h(x_{2}))=g(h(x_{1}))=g(f(x_{1}))\en C$ . Así que este caso es imposible.

Nota

La definición de mapeo anterior no es constructiva , es decir, no existe un algoritmo para determinar en un número finito de pasos si algún elemento del conjunto se encuentra en el conjunto o no. Aunque para algunos casos especiales existe tal algoritmo. $h$ $X$ $A$ $C$

Véase también

Literatura

N. K. Vereshchagin, A. Shen. Conferencias sobre lógica matemática y teoría de algoritmos. Parte 1. Inicios de la teoría de conjuntos.

Ershov Yu. L., Palyutin E. A. Lógica matemática: libro de texto. - 3º, estereotipo. edición - San Petersburgo: "Lan", 2004. - 336 p.