Schröder Amber Proof

Question

Estoy tratando de entender la demostración del teorema de Schröder-Bernstein en el libro de Halmos. Aquí está mi mejor intento de replicarlo.

Afirmación: Si existen inyecciones $f: X \to Y$ y $g: Y \to X$ entonces existe una biyección $h: X \to Y$ .

Dejemos que $f: X \hookrightarrow Y$ y $g: Y \hookrightarrow X$ sean inyecciones. Sin pérdida de generalidad, supongamos $X \cap Y = \emptyset$ . Si no, sustituimos $X$ y $Y'$ con copias isomorfas $X', Y'$ con $X' \cap Y' = \emptyset$ . Si $f: X \to Y$ es suryente, $f$ es biyectiva y tenemos $|X| = |Y|$ . Si $g: Y \to X$ es suryente, entonces existe $g^{-1} : X \to Y$ que es biyectiva. Procedemos bajo la suposición de que ni $f$ ni $g$ son suryentes. Llamamos $x \in X$ el padre del elemento $f(x) \in Y$ y $y \in Y$ el padre si $g(y) \in X$ . Cada elemento $x \in X$ tiene una secuencia infinita de descendientes , $$f(x), g(f(x)), f(g(f(x)), \ldots,$$ como lo hace cada $y \in Y$ , $$g(y), f(g(y)), g(f(g(y))), \ldots$$ Cada término de estas secuencias es, por construcción, un descendiente de todos los términos precedentes y un \emph {anfitrión} de todos los términos siguientes. Para cada elemento de $X \cup Y$ Tenemos tres posibilidades mutuamente excluyentes y exhaustivas. En primer lugar, un elemento $x \in X$ puede no tener un padre en $Y$ es decir, $x \neq g(y)$ para cualquier $y \in Y$ , por lo que tenemos $x \in X - g(Y)$ . Llamamos a este tipo de $x$ un \emph {orphan}. En segundo lugar, un elemento $y \in Y$ puede no tener un padre en $X$ es decir, tenemos $y \neq f(x)$ para cualquier $x \in X$ , por lo que tenemos $y \in Y - f(X)$ . En tercer lugar, el linaje puede retroceder infinitamente.

Definir $X_X$ para ser el conjunto de elementos $x \in X - g(Y)$ y sus descendientes en $X$ . Sea $X_Y$ sea el conjunto de elementos de los descendientes en $X$ de los elementos de $Y - f(X)$ . Sea $X_{\infty}$ sea el conjunto de elementos de $X$ sin un ancestro sin padres. Así que $X = X_X \sqcup X_Y \sqcup X_{\infty}$ . Del mismo modo, dejemos que $Y_X$ como los descendientes en $Y$ de los elementos en $X - f(X)$ , dejemos que $Y_Y$ sea el conjunto de elementos de $Y - g(Y)$ y sus descendientes en $Y$ y que $Y_{\infty}$ sea el conjunto de elementos de $Y$ con ningún ancestro sin padres. Así que $Y = Y_X \sqcup Y_Y \sqcup Y_{\infty}$ .

Observe que, por definición, $Y_X$ consiste en los descendientes en $Y$ de todos $x \in X_X$ . Así que si $x \in X_X$ tenemos $f(x) \in Y_X$ . Además, $f$ es inyectiva, por lo que si $x \neq x'$ en $X_X$ hay exactamente un elemento correspondiente en $Y_X$ . Además, cada elemento de $Y_X$ es el padre de exactamente un hijo $x \in X_X$ . Así que la restricción $f \mid_{X_X} : X_X \to Y_X$ es una biyección.

En segundo lugar, si $x \in X_Y$ entonces $x$ es descendiente de un elemento $y \in Y - g(Y)$ . Es decir, $x = g(y)$ para algunos $y \in Y_Y$ . Entonces tenemos $g^{-1} (x) = y \in Y_Y$ , donde $g^{-1}$ es el inverso de la izquierda $Y \to X$ cuya existencia está garantizada por el hecho de que $g$ es inyectiva. Afirmo que $g^{-1} \mid_{X_Y}: X_Y \to Y_Y$ es una biyección. En primer lugar, tenemos $g^{-1} \circ g = \mathrm{Id}_Y$ , $g$ es un inverso de la derecha de $g^{-1}$ Así que $g^{-1}$ es suryente. Además, dado $a,b \in X_Y$ , asuma que $g^{-1} (a) = g^{-1} (b)$ . Según la definición de $X_Y$ tenemos $a = g(s)$ y $b = g(t)$ para algunos $s,t \in Y$ . Así que $g^{-1} (g(s)) = g^{-1} (g(t))$ Así que $s = t$ . Como $g$ es una función bien definida $g(s) = g(t)$ Así que $a = b$ Así que $g^{-1}$ es una biyección.

Por último, si $x \in X_{\infty}$ , entonces su linaje retrocedió como infinitum, por lo que debemos tener $x \in Y_{\infty}$ . Afirmo que $f \mid_{X_{\infty}} : X_{\infty} \to Y_{\infty}$ es una biyección. Dado $y \in Y_{\infty}$ debe existir un padre $x \in X_{\infty}$ . Además, teniendo en cuenta $a,b \in X_{\infty}$ para lo cual $f(a) = f(b)$ tenemos $a = b$ desde $f$ es inyectiva.

Por lo tanto, definimos el mapa $\varphi: X \to Y$ por $$\varphi(x) = \begin{cases} f(x), \; & \text{ if $x \in X_X \cup X_{\infty}$} \\ g^{-1} (x), \; & \text{ if $x \in X_Y$} \end{cases}$$ Desde $f_{X_X}: X_X \to Y_X$ , $g_{-1}: X_Y \to Y_Y$ y $f \mid _{X_{\infty}}: X_{\infty} \to Y_{\infty}$ son biyecciones, $\varphi$ es una biyección $X \to Y$ , por lo que tenemos $|X| = |Y|$ , según se desee.

---

¿Cómo se ve esta prueba? ¿Me he perdido algo?

Answer 1

Algunos puntos menores:

1. "ni $X$ ni $Y$ es sobreyectiva" debe decir "ni $f$ no $g$ es sobreyectiva".
2. "el padre si $g(y) \in X$ "debe decir "el padre de $g(y) \in X$ ".
3. "así que debemos tener $x \in Y_\infty$ "debería ser, presumiblemente, algo parecido a "por lo que debemos tener $f(x) \in Y_\infty$ - $x$ ni siquiera está en $Y$ por lo que no puede estar en $Y_\infty$ (además, "as infinitum" debería decir "ad infinitum".

Más en serio, el párrafo que comienza con "Fíjate que, por definición" es defectuoso. Usted sabe que cada $y \in Y_X$ es el padre de exactamente una $f \in X_X$ pero luego usas eso cada $y \in Y_X$ es el niño de exactamente una $f \in X_X$ asumiendo esencialmente su conclusión.

El siguiente párrafo es poco convincente: ¿por qué es el caso que $g^{-1}\circ g$ ¿es la identidad?