Si ponemos $A$ y $B$ . Suponiendo que existe un mapa inyectivo desde $A$ a $B$ y un mapa inyectivo de $B$ a $A$ . Cómo demostrar que existe una biyección entre $A$ y $B$ .
Respuestas
¿Demasiados anuncios?
DanV
Puntos
281
El resultado es probablemente uno de los resultados teóricos de conjuntos más famosos de las matemáticas y se conoce como el teorema de Cantor-Bernstein (también Cantor-Schröder-Bernstein). Tiene una rica historia, y se le han dado varias pruebas diferentes.
Puede encontrar algunos de sus aspectos históricos más destacados, así como una de las pruebas en esta página web .
Como se ha señalado en los comentarios, este es el Teorema de Cantor-Schröder-Bernstein de la que se conocen varias pruebas. La que me parece más fácil de entender es una versión de la debida a König.
Dejemos que $A_0=A\setminus g[B]$ y $B_0=B\setminus f[A]$ . Dado $A_n$ y $B_n$ para algunos $n\in\omega$ , dejemos que $B_{n+1}=f[A_n]$ y $A_{n+1}=g[B_n]$ . Por último, dejemos que $A_\omega=A\setminus\bigcup_{n\in\omega}A_n$ y $B_\omega=B\setminus\bigcup_{n\in\omega}B_n$ . Claramente $\{A_\xi:\xi\le\omega\}$ y $\{B_\xi:\xi\le\omega\}$ son particiones de $A$ y $B$ respectivamente. Obsérvese también que para cada $n\in\omega$ , $f\upharpoonright A_n$ es una biyección de $A_n$ a $B_{n+1}$ y $g\upharpoonright B_n$ es una biyección de $B_n$ a $A_{n+1}$ . El siguiente párrafo puede hacer que esto sea más fácil de visualizar.
Digamos que un elemento $b\in B$ puede ser se retiró si $b\in f[A]$ para que haya un único $a=f^{-1}(b)\in A$ En este caso, diré que $b$ puede ser retirado a $a$ y llamar a $a$ el retroceso de $b$ . Del mismo modo, digamos que $a\in A$ puede ser se retiró si $a\in g[B]$ para que haya un único $g^{-1}(a)\in B$ . Entonces $A_0$ es el conjunto de elementos de $A$ que no puede ser retirado, y $B_0$ es el conjunto de elementos de $B$ que no puede ser retirado. Elementos de $A_1$ y $B_1$ puede retirarse una vez, para $B_0$ y $A_0$ , respectivamente, pero no se puede tirar de ellos. Los elementos de $A_2$ y $B_2$ puede ser retirado a $B_1$ y $A_1$ , respectivamente, y sus retrocesos pueden volver a serlo. Una fácil inducción establece que para cada $n\in\omega$ , elementos de $A_n$ y $B_n$ puede ser retirado exactamente $n$ tiempos.
Si $b\in B_\omega$ entonces $b\in f[A]$ Así que $b$ puede retroceder, pero su retroceso no es en $A_n$ para cualquier $n\in\omega$ Así que.., $f^{-1}(b)\in A_\omega$ . Por el contrario, si $a\in A_\omega$ entonces $f(a)\in B\setminus\bigcup_{n\in\omega}B_n=B_\omega$ y se deduce que $f\upharpoonright A_\omega$ es una biyección de $A_\omega$ a $B_\omega$ . (De hecho, $A_\omega$ y $B_\omega$ contienen aquellos elementos de $A$ y $B$ respectivamente, que pueden ser retirados infinitas veces). Ahora tenemos las piezas necesarias para construir una biyección $h$ de $A$ a $B$ .
La idea es sencilla. Primero, en $A_\omega$ podemos utilizar simplemente $f\upharpoonright A_\omega$ que "golpea" a todos los $B_\omega$ . Si $n\in\omega$ es uniforme, podemos utilizar $f\upharpoonright A_n$ , golpeando $B_{n+1}$ . Y si $n\in\omega$ es impar, podemos utilizar $g^{-1}\upharpoonright A_n$ , golpeando $B_{n-1}$ . En otras palabras, dejemos que
$$h:A\to B:a\mapsto\begin{cases} f(a),&\text{if }a\in A_{2n}\text{ for some }n\in\omega\\ g^{-1}(a),&\text{if }a\in A_{2n+1}\text{ for some }n\in\omega\\ f(a),&\text{if }a\in A_\omega\;. \end{cases}$$
Si prefieres pensar en una función como un conjunto de pares ordenados, deja que $E=A_\omega\cup\bigcup_{n\in\omega}A_{2n}$ y definir
$$h=\big(f\upharpoonright E\big)\cup\left(g^{-1}\upharpoonright(A\setminus E)\right)\;.$$
Claramente $h$ es una biyección de $A$ a $B$ .
(Si tengo tiempo, añadiré un diagrama para acompañar esto).
También hay una prueba muy corta de Teorema del punto fijo de Tarski que a su vez es bastante fácil de demostrar. Esa prueba se puede encontrar aquí (como Ejemplo $3$ ). Sin embargo, por muy elegante que sea, no lo encuentro tan intuitivamente satisfactorio.
