Lamport afirma que hay un error en Kelley ' s prueba del teorema de Schroeder-Bernstein. ¿Qué es?

Question

En la sección 4.1 de su nota de Cómo escribir una prueba, Leslie Lamport menciona un error en Kelley exposición de la Schröder-Bernstein teorema:

Hace unos veinte años, me he decidido a escribir una prueba de la Schröder-Bernstein teorema para una clase de introducción a la clase de matemáticas. El más simple prueba de que he podido encontrar es en Kelley clásico general de la topología de texto [4, página 28]. Desde Kelley fue escrito para una audiencia más sofisticada, he tenido que añadir una gran cantidad de explicaciones a su media página de prueba. Yo había escrito cinco páginas cuando me di cuenta de que Kelley prueba de que estaba mal. Recientemente, he querido ilustrar una conferencia sobre la prueba de estilo con una convincente incorrecta de la prueba, así que me volví a Kelley. Pude encontrar nada malo con su prueba; parecía obviamente correcto! Leer - ción y la relectura de la prueba me convenció de que mi memoria había fallado, o de lo contrario me fue muy estúpido de hace veinte años. Aún así, Kelley de la prueba fue de corta y podría servir como un buen ejemplo, así que empecé a escribirlo como una estructura de prueba. En cuestión de minutos, he redescubierto el error.

Sin embargo, Lamport no explica lo que este error es. Miré a Kelley de la prueba y se quedó mirando por un largo tiempo, pero yo era incapaz de descubrir el error. Podría alguien por favor que me explique lo que este presunto error que podría ser?

Aquí Kelley de la prueba (que él atribuye a Birkhoff y Mac Lane) en su totalidad (Kelley, Topología General, página 28):

Teorema Si hay un uno-a-uno en función de un conjunto $A$ a es subconjunto de un conjunto $B$ y también hay un uno-a-uno la función $B$ a un subconjunto de $A$, entonces $A$ y $B$ son son equiparables.

Prueba Supongamos que $f$ es un uno-a-uno el mapa de $A$ a $B$ y $g$ es de uno a uno en $B a$ a $A$. Se puede suponer que $A$ y $B$ son disjuntas. La prueba del teorema se logra por la descomposición de $A$ y $B$ en las clases en las que más fácilmente se describe en términos de la partenogénesis. Un punto de $x$ (de $Un$ o $B$) es un antepasado de un punto de $y$ ffi $$ y puede ser obtenido a partir de $x$ por aplicaciones sucesivas de $f$ y $g$ (o $g$ y $f$). Ahora descomponer $A$ en tres grupos: deja de $A_E$ consisten en todos los puntos de $$ que tiene un número par de los antepasados, deje de $A_O$ constan de puntos que tienen un número impar de los antepasados, y deje de $A_I$ consisten en puntos con infinidad de antepasados. Descomponer $B$ del mismo modo y observar: $f$ mapas de $A_E$ en $B_O$ y $A_I$ en $B_I$ y $g^{-1}$ mapas de $A_O$ en $B_E$. Por lo tanto la función que está de acuerdo con de $f$ en $A_{E} \cup A_{I}$ y se compromete con $g^{-1}$ en $A_{O}$ es un uno-a-uno el mapa de $A$ a $B$.

Tengo la sospecha de que el error podría estar con el borde de los casos (los puntos en $A_E$ y $B_{E}$ con ningún antepasado), pero el argumento parece funcionar.

Gracias de antemano.

Answer 1

Supongamos que hay un ciclotal que $g(f(a)) = un$ algún $ $a. Entonces $a$ y $ $f(a) se cuenta como teniendo un número incluso de antepasados, a saber $\ {a, f (a) \} $.

Esto contradice la afirmación de que $f$ mapas $A_E$ (en) a $ $B_O.

Answer 2

Suponga que $f$ es un uno-a-uno el mapa de $A$ a $B$ y $g$ es de uno a uno en $B a$ a $A$.

Esto es permitido por las condiciones dadas.

Se puede suponer que a y B son disjuntos.

De hecho, de lo contrario vamos a $B=\{A\}\times B$, que es distinto a $A$ y en obvio bijection a $B$, permitiendo así que las definiciones de los mapas de $A\B'$, $B'\$ en consecuencia.

La prueba del teorema se logra por la descomposición de $A$ y $B$ en las clases en las que más fácilmente se describe en términos de la partenogénesis. Un punto de $x$ (de $Un$ o $B$) es un antepasado de un punto de $y$ ffi $$ y puede ser obtenido a partir de $x$ por aplicaciones sucesivas de $f$ y $g$ (o $g$ y $f$).

Esto define un (transitivo) la relación en $A\cup B$.

Ahora descomponer $A$ en tres grupos: deja de $A_E$ consisten en todos los puntos de $$ que tiene un número par de los antepasados, deje de $A_O$ constan de puntos que tienen un número impar de los antepasados, y deje de $A_I$ consisten en puntos con infinidad de antepasados.

No hay problema aquí. La cardinalidad de un conjunto es par o impar o infinito.

Descomponer $B$ del mismo modo y observar: $f$ mapas de $A_E$ en $B_O$ y $A_I$ en $B_I$,

Tenemos que ser cuidadosos en este punto: El conjunto de los antepasados de $f(a)$ es el conjunto de los antepasados de $a$, junto con los$$. Por lo tanto, si el primer conjunto es infinito, también lo es el segundo. Y si el primer conjunto es par, entonces la segunda es impar siempre la primera no contiene $a$. Uno podría ver un descuidado definición aquí como finito , sino cíclico antepasado secuencias deben ser contabilizados a $A_I$ y $B_I$, respectivamente.

y $g^{-1}$ mapas de $A_O$ en $B_E$.

Podemos aplicar $g^{-1}$ $A_O$ porque cada elemento tiene al menos un antepasado. Sin embargo, el mismo advertencias acerca de la cíclica de los casos se aplica.

Por lo tanto la función que está de acuerdo con de $f$ en $A_E\copa A_I$ y se compromete con $g^{-1}$ en $A_O$ es un uno-a-uno el mapa de $A$ a $B$.

Esto está muy bien.