Teorema de Cantor-Bernstein

Demostramos el teorema de Teorema de Cantor-Bernstein.

Teorema (Cantor-Bernstein). Sean $A$ y $B$ dos conjuntos tales que existen aplicaciones inyectivas $f:A\to B$ y $g:B\to A.$ Entonces, existe una biyección entre $A$ y $B.$

Demostración. Sea $b_1\in B.$ Vamos a construir una sucesión de elementos $b_1,a_1,b_2,a_2,b_3,a_3,\ldots$ de elementos con $b_i\in B$ y $a_i\in A$ de la siguiente manera. Puede existir o no $a_1\in A$ tal que $f(a_1)=b_1,$ pero al ser $f$ inyectiva si tal $a_1$ existe, es único y ya tendríamos $a_1.$ De nuevo, puede existir o no $b_2\in B$ tal que $g(b_2)=a_1$ pero si tal elemento existe es único y ya tendríamos $b_2.$ De forma similar, elegimos $a_2$ como el único elemento que cumple $f(a_2)=b_2$ si tal $a_2$ existe. Se pueden presentar los siguientes casos:
$(1)$ Llegamos a un $a_n$ y paramos porque no existe $b\in B$ tal que $g(b)=a_n.$
$(2)$ Llegamos a un $b_n$ y paramos porque no existe $a\in A$ tal que $f(a)=b_n.$
$(3)$ El proceso continúa indefinidamente.
Entonces, para todo $b\in B$ y eligiéndolo como $b_1$ estamos en uno y sólo uno de los tres casos anteriores. Podemos por tanto particionar $B$ en tres subconjuntos $$\begin{aligned}& B_A=\{b\in B: \text{ el proceso termina en un }a_n\},\\
& B_B=\{b\in B: \text{ el proceso termina en un }b_n\},\\
& B_\infty=\{b\in B: \text{ el proceso nunca termina}\}.
\end{aligned}$$ El mismo proceso se puede aplicar para todo $a\in A$ (y tomándolo como $a_1$) se puede particionar $A$ en los siguientes subconjuntos: $$\begin{aligned}& A_A=\{a\in A: \text{ el proceso termina en un }a_n\},\\
& A_B=\{a\in A: \text{ el proceso termina en un }b_n\},\\
& A_\infty=\{a\in A: \text{ el proceso nunca termina}\}.\end{aligned}$$ Para demostrar que existe una biyección entre $A$ y $B,$ bastara demostrar que existe una biyección entre $A_A$ y $B_A$, una entre $A_B$ y $B_B$ y otra entre $A_\infty$ y $B_\infty.$ Veamos que la restricción de $f$ a $A_A$ es una biyección entre $A_A$ y $B_A.$ Para ello y dado que $f$ es inyectiva, bastará demostrar dos cosas:
$(a)$ $a\in A_A\Rightarrow f(a)\in B_A.$
$(b)$ $\forall b\in B_A\;\exists a\in A_A:f(a)=b.$
       Si $a\in A_A$ el proceso aplicado a $a$ termina en $A.$ Consideremos el proceso aplicado a $f(a).$ El primer paso del proceso nos devuelve $a$ con lo cual el proceso continúa hasta finalizar en $A,$ es decir $f(a)\in B_A$ y por tanto se verifica $(a).$ Por otra parte, si $b\in B_A$ el proceso aplicado a $b$ termina en $A$ y por tanto ha de tener una primera etapa pues en caso contrario terminaría en $b\in B.$ Es decir, existe $a\in A$ tal que $b=f(a).$ Pero el proceso aplicado a este $a$ es el mismo que la prolongación del proceso aplicado a $b$ y por tanto termina en $A$ con lo cual $a\in A_A.$ En consecuencia, $f:A_A\to B_A$ es una biyección.
       Razonando de manera análoga demostramos que $g:B_B\to A_B$ es una biyección, y por tanto $g^{-1}: A_B\to B_B$ es biyección.
        Por último, demostremos que $f:A_\infty\to B_\infty$ es una biyección. Es una inyección pues $f:A\to B$ lo es por hipótesis. Si $b\in B_\infty$ entonces, $b=f(a)$ para algún $a\in A$ y éste $a$ pertenece a $A_\infty$ pues el proceso que empieza en $a$ es el mismo que el que empieza en $b$ después del primer paso y el proceso nunca termina pues $b\in B_\infty.$
       Resumiendo, $F:A\to B$ dada por $$F(x)=\left \{ \begin{matrix} f(x)& \text{si} & x\in A_A\\f(x)& \text{si} & x\in A_\infty\\g^{-1}(x)& \text{si} & x\in A_B.\end{matrix}\right.$$ es una biyección pues $A_A,$ $A_B$ y $A_\infty$ forma una partición de $A$, $B_A,$ $B_B$ y $B_\infty$ forman una partición de $B$ y las aplicaciones $f:A_A\to B_A,$ $f:A_\infty\to B_\infty,$ $g^{-1}:A_B\to B_B$ son biyecciones. Queda pues demostrado el teorema de Cantor-Bernstein.

Esta entrada fue publicada en Miscelánea matemática. Guarda el enlace permanente.