Teorema de Cantor-Bernstein-Schröder

Archiu:CantorEquivalenceTheorem1887b.gif

Teorema de Cantor-Bernstein-Schröder

La teorema de Schröder i Bernstein establix un criteri per a establir si existix una funció biyectiva entre dos conjunts qualssevol A i B:

Per a qualsevol conjunt A i B, si existix una funció inyectiva d'en B i existix una funció inyectiva de B en A, llavors existix una correspondència biunívoca entre B i A. Formalment:

El teorema pot semblar trivial per a conjunts finitos, pero l'enunciat de la teorema es complix per a conjunts de qualsevol cardinalidad. La teorema resulta útil en molts casos per a poder determinar si un conjunt té la mateixa cardinalidad que un atre conjunt, ya que dos conjunts tenen la mateixa cardinalidad just quan existix una correspondència biunívoca entre ells.

Aplicacions

La teorema de Cantor-Schröder-Bernstein permet definir correctament la cardinalidad com classe d'equivalència ya que com a punt de partida de la relació d'orde "tindre més elements que" es pren:

Òbviament s'espera que la relació binaria anterior siga antisimètrica, és dir:

Pero això, és lo que la teorema de Cantor-Shröder-Bernstein precisament afirma, a saber, que es dona l'implicació anterior, en la qual cosa la relació binaria efectivament és antisimètrica.

Demostració

Considere's el conjunt potencia d'i definixca's la següent aplicació h_p sobre dit conjunt:

A on:

$Y-X:=\{x|x\in Y\wedge x\notin X\}$

$f[U]:=\{y\in B|\mathrm{\exists }x\in U,f(x)=y\}$

Primer deu provar-se que l'aplicació h_p anterior té un punt fix. Per a això es considera la colecció de conjunts:

I es considera l'unió de conjunts de la colecció anterior, que per la pròpia de definició de la colecció $𝒰$ es té que:

Per a provar que $W=h_p(W)$ falta provar l'inclusió recíproca per a això es té que:

I per tant queda provat que el conjunt W és un punt fix de l'aplicació h_p, per a demostrar la teorema de Cantor-Schröder-Bernstein falta definir la biyección explícitament. Considerem, per eixemple:

Pot comprovar-se que l'aplicació $h:A\to B$ aixina definida és la biyección buscada.