Teorema de Cantor-Bernstein-Schröder

El teorema de Schröder y Bernstein establece un criterio para establecer si existe una función biyectiva entre dos conjuntos cualesquiera A y B:

Para cualquier conjunto A y B, si existe una función inyectiva de A en B y existe una función inyectiva de B en A, entonces existe una correspondencia biunívoca entre B y A. Formalmente:

${displaystyle exists f,g (f:A o Bland g:B o A) land (f,g {mbox{inyectivas}})Rightarrow exists h (h:A o B) land (h {mbox{biyectiva}})}$

El teorema puede parecer trivial para conjuntos finitos, pero el enunciado del teorema se cumple para conjuntos de cualquier cardinalidad. El teorema resulta útil en muchos casos para poder determinar si un conjunto tiene la misma cardinalidad que otro conjunto, ya que dos conjuntos tienen la misma cardinalidad justo cuando existe una correspondencia biunívoca entre ellos.

El teorema de Cantor-Schröder-Bernstein permite definir correctamente la cardinalidad como clase de equivalencia ya que como punto de partida de la relación de orden "tener más elementos que" se toma:

${displaystyle |A|leq |B|Leftrightarrow exists f (f:A o B) land (f {mbox{es inyectiva}})}$

Obviamente se espera que la relación binaria anterior sea antisimétrica, es decir:

${displaystyle |A|leq |B| land |B|leq |A|Rightarrow |B|=|A|}$

Pero eso, es lo que el teorema de Cantor-Shröder-Bernstein precisamente afirma, a saber, que se da la implicación anterior, con lo cual la relación binaria efectivamente es antisimétrica.

Considérese el conjunto de partes de A y defínase la siguiente aplicación h_p sobre dicho conjunto:

${displaystyle h_{p}:{mathcal {P}}(A) o {mathcal {P}}(A),qquad h_{p}(U)=A-g[B-f[U]]}$

Donde:

Primero debe probarse que la aplicación h_p anterior tiene un punto fijo. Para ello se considera la colección de conjuntos:

${displaystyle {mathcal {U}}:={Uin {mathcal {P}}(A)|Usubset h_{p}(U)}}$

Y se considera la unión de conjuntos de la colección anterior, que por la propia de definición de la colección ${displaystyle {mathcal {U}}}$ se tiene que:

${displaystyle W:=igcup _{Uin {mathcal {U}}}Usubset igcup _{Uin {mathcal {U}}}h_{p}(U)subset h_{p}(W)}$

Para probar que ${displaystyle scriptstyle W=h_{p}(W)}$ falta probar la inclusión recíproca para ello se tiene que:

${displaystyle Wsubset h_{p}(W)Rightarrow h_{p}(W)subset h_{p}(h_{p}(W)))Rightarrow h_{p}(W)in {mathcal {U}}Rightarrow h_{p}(W)subset W}$

Y por tanto queda probado que el conjunto W es un punto fijo de la aplicación h_p, para demostrar el teorema de Cantor-Schröder-Bernstein falta definir la biyección explícitamente. Consideremos, por ejemplo:

${displaystyle h(x):={egin{cases}f(x)&xin W\g^{-1}(x)&x otin Wend{cases}}}$

Puede comprobarse que la aplicación ${displaystyle scriptstyle h:A o B}$ así definida es la biyección buscada.

---