Teorema de Schröder-Bernstein

Teorema en la teoría de conjuntos

En teoría de conjuntos , el teorema de Schröder-Bernstein establece que, si existen funciones inyectivas f  : A → B y g  : B → A entre los conjuntos A y B , entonces existe una función biyectiva h  : A → B .

En términos de la cardinalidad de los dos conjuntos, esto implica clásicamente que si | A | ≤ | B | y | B | ≤ | A | , entonces | A | = | B | ; es decir, A y B son equipotentes . Esta es una característica útil en la ordenación de números cardinales .

El teorema recibe su nombre en honor a Felix Bernstein y Ernst Schröder . También se lo conoce como teorema de Cantor-Bernstein o teorema de Cantor-Schröder-Bernstein , en honor a Georg Cantor , quien lo publicó por primera vez (aunque sin prueba).

Prueba

Definición de König de una biyección h : A  →  B a partir de las inyecciones de ejemplo dadas f : A  →  B y g : B  →  A . Un elemento en A y B se denota por un número y una letra, respectivamente. La secuencia 3 → e → 6 → ... es un A -stopper, lo que lleva a las definiciones h (3) =  f (3) =  e , h (6) =  f (6), .... La secuencia d  → 5 →  f  → ... es un B -stopper, lo que lleva a h (5) =  g ⁻¹ (5) =  d , .... La secuencia ... →  a  → 1 →  c  → 4 → ... es doblemente infinita, lo que lleva a h (1) =  g ⁻¹ (1) =  a , h (4) =  g ⁻¹ (4) =  c , .... La secuencia b  → 2 →  b es cíclica, lo que lleva a h (2) =  g ⁻¹ (2) =  b .

La siguiente prueba se atribuye a Julius König . ^[1]

Supongamos sin pérdida de generalidad que A y B son disjuntos . Para cualquier a en A o b en B podemos formar una única secuencia bilateral de elementos que están alternativamente en A y B , aplicando repetidamente y para ir de A a B y y para ir de B a A (donde se definen; las inversas y se entienden como funciones parciales ). ${\displaystyle f}$ ${\displaystyle g^{-1}}$ ${\displaystyle g}$ ${\displaystyle f^{-1}}$ ${\displaystyle f^{-1}}$ ${\displaystyle g^{-1}}$

${\displaystyle \cdots \rightarrow f^{-1}(g^{-1}(a))\rightarrow g^{-1}(a)\rightarrow a\rightarrow f(a)\rightarrow g(f(a))\rightarrow \cdots }$

Para cualquier a en particular , esta secuencia puede terminar hacia la izquierda o no, en un punto donde o no está definido. ${\displaystyle f^{-1}}$ ${\displaystyle g^{-1}}$

Por el hecho de que y son funciones inyectivas, cada a en A y b en B está en exactamente una de tales sucesiones dentro de la identidad: si un elemento aparece en dos sucesiones, todos los elementos a la izquierda y a la derecha deben ser los mismos en ambas, por la definición de las sucesiones. Por lo tanto, las sucesiones forman una partición de la unión (disjunta) de A y B . Por lo tanto, basta con producir una biyección entre los elementos de A y B en cada una de las sucesiones por separado, como sigue: ${\displaystyle f}$ ${\displaystyle g}$

Llamemos a una secuencia A-stopper si se detiene en un elemento de A o B-stopper si se detiene en un elemento de B. De lo contrario, llámela doblemente infinita si todos los elementos son distintos o cíclica si se repite. Vea la imagen para ver ejemplos.

• Para un A-stopper , la función es una biyección entre sus elementos en A y sus elementos en B. ${\displaystyle f}$
• Para un B-stopper , la función es una biyección entre sus elementos en B y sus elementos en A. ${\displaystyle g}$
• Para una secuencia doblemente infinita o una secuencia cíclica , o servirá ( se utiliza en la imagen). ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle g}$

Corolario para el par sobreyectivo

Si asumimos el axioma de elección, entonces un par de funciones sobreyectivas y también implica la existencia de una biyección. Construimos una función inyectiva h  : B → A de eligiendo un solo elemento de la imagen inversa de cada punto en . La sobreyectividad de garantiza la existencia de al menos un elemento en cada una de esas imágenes inversas. Hacemos lo mismo para obtener una función inyectiva k  : A → B de . El teorema de Schröder-Bernstein se puede aplicar entonces a las inyecciones h y k . ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f^{-1}}$ ${\displaystyle B}$ ${\displaystyle f}$ ${\displaystyle g^{-1}}$

Ejemplos

Función biyectiva de ${\displaystyle [0,1]\to [0,1)}$

Nota: es el conjunto semiabierto de 0 a 1, incluido el límite 0 y excluido el límite 1. ${\displaystyle [0,1)}$

Sea con y con las dos funciones inyectivas. ${\displaystyle f:[0,1]\to [0,1)}$ ${\displaystyle f(x)=x/2;}$ ${\displaystyle g:[0,1)\to [0,1]}$ ${\displaystyle g(x)=x;}$

De acuerdo con ese procedimiento ${\displaystyle C_{0}=\{1\},\;C_{k}=\{2^{-k}\},\;C=\bigcup _{k=0}^{\infty }C_{k}=\{1,{\tfrac {1}{2}},{\tfrac {1}{4}},{\tfrac {1}{8}},...\}}$

Entonces es una función biyectiva de . ${\displaystyle h(x)={\begin{cases}{\frac {x}{2}},&\mathrm {for} \ x\in C\\x,&\mathrm {for} \ x\in [0,1]\smallsetminus C\end{cases}}}$ ${\displaystyle [0,1]\to [0,1)}$

Función biyectiva de ${\displaystyle [0,2)\to [0,1)^{2}}$

Dejar con ${\displaystyle f:[0,2)\to [0,1)^{2}}$ ${\displaystyle f(x)=(x/2;0);}$

Luego se pueden utilizar las expansiones y con ${\displaystyle (x;y)\in [0,1)^{2}}$ ${\displaystyle x=\sum _{k=1}^{\infty }a_{k}\cdot 10^{-k}}$ ${\displaystyle y=\sum _{k=1}^{\infty }b_{k}\cdot 10^{-k}}$ ${\displaystyle a_{k},b_{k}\in \{0,1,...,9\}}$

y ahora se puede establecer que define una función inyectiva . (Ejemplo: ) ${\displaystyle g(x;y)=\sum _{k=1}^{\infty }(10\cdot a_{k}+b_{k})\cdot 10^{-2k}}$ ${\displaystyle [0,1)^{2}\to [0,2)}$ ${\displaystyle g({\tfrac {1}{3}};{\tfrac {2}{3}})=0.363636...={\tfrac {12}{33}}}$

Y por lo tanto se puede construir una función biyectiva con el uso de y . ${\displaystyle h}$ ${\displaystyle f(x)}$ ${\displaystyle g^{-1}(x)}$

En este caso todavía es fácil pero ya se vuelve bastante complicado. ${\displaystyle C_{0}=[1,2)}$ ${\displaystyle C_{1}=g(f(C_{0}))=g(\{(x;0)|x\in [{\tfrac {1}{2}},1)\,\})}$

Nota: Por supuesto, hay una manera más sencilla de utilizar la definición de función (que ya es biyectiva) . Entonces, sería el conjunto vacío y para todo x. ${\displaystyle g_{2}(x;y)=2\cdot \sum _{k=1}^{\infty }(10\cdot a_{k}+b_{k})\cdot 10^{-2k}}$ ${\displaystyle C}$ ${\displaystyle h(x)=g_{2}^{-1}(x)}$

Historia

El nombre tradicional "Schröder-Bernstein" se basa en dos pruebas publicadas de forma independiente en 1898. A menudo se añade el nombre de Cantor porque fue el primero en formular el teorema en 1887, mientras que el nombre de Schröder se omite a menudo porque su prueba resultó ser errónea, mientras que el nombre de Richard Dedekind , quien lo demostró por primera vez, no está relacionado con el teorema. Según Bernstein, Cantor había sugerido el nombre de teorema de equivalencia (Äquivalenzsatz). ^[2]

Primera formulación del teorema de Cantor (1887) ^[3]

• 1887 Cantor publica el teorema, aunque sin demostración. ^{[3] [2]}
• 1887 El 11 de julio, Dedekind demuestra el teorema (sin basarse en el axioma de elección ) ^[4] pero no publica su prueba ni se la cuenta a Cantor. Ernst Zermelo descubrió la prueba de Dedekind y en 1908 ^[5] publica su propia prueba basada en la teoría de cadenas del artículo de Dedekind Was sind und was sollen die Zahlen? ^{[2] [6]}
• 1895 Cantor enuncia el teorema en su primer artículo sobre la teoría de conjuntos y los números transfinitos. Lo obtiene como una consecuencia fácil del orden lineal de los números cardinales. ^{[7] [8] [9]} Sin embargo, no pudo demostrar este último teorema, que en 1915 Friedrich Moritz Hartogs demostró que era equivalente al axioma de elección . ^{[2] [10]}
• 1896 Schröder anuncia una prueba (como corolario de un teorema de Jevons ). ^[11]
• 1897 Bernstein , un estudiante de 19 años del Seminario de Cantor, presenta su prueba. ^{[12] [13]}
• 1897 Casi simultáneamente, pero independientemente, Schröder encuentra una prueba. ^{[12] [13]}
• 1897 Después de una visita de Bernstein, Dedekind demuestra independientemente el teorema por segunda vez.
• 1898 La prueba de Bernstein (que no se basa en el axioma de elección) es publicada por Émile Borel en su libro sobre funciones. ^[14] (Comunicado por Cantor en el Congreso Internacional de Matemáticos de 1897 en Zúrich). En el mismo año, la prueba también aparece en la disertación de Bernstein . ^{[15] [2]}
• 1898 Schröder publica su prueba ^{[16] , que sin embargo,} Alwin Reinhold Korselt demuestra ser errónea en 1902 (justo antes de la muerte de Schröder), ^[17] (confirmada por Schröder), ^{[2] [18]} pero el artículo de Korselt se publica recién en 1911.

Ambas pruebas de Dedekind se basan en sus famosas memorias de 1888 Was sind und was sollen die Zahlen? y las derivan como corolario de una proposición equivalente a la afirmación C en el artículo de Cantor, ^[7] que dice A ⊆ B ⊆ C y | A | = | C | implica | A | = | B | = | C | . Cantor observó esta propiedad ya en 1882/83 durante sus estudios en teoría de conjuntos y números transfinitos y, por lo tanto, se basaba (implícitamente) en el axioma de elección .

Prerrequisitos

La prueba de Cantor de 1895 se basó, en efecto, en el axioma de elección al inferir el resultado como un corolario del teorema de buen orden . ^{[8] [9]} Sin embargo, la prueba de König dada anteriormente muestra que el resultado también puede demostrarse sin utilizar el axioma de elección.

Por otra parte, la prueba de König utiliza el principio del tercero excluido para extraer una conclusión a través del análisis de casos. Como tal, la prueba anterior no es constructiva. De hecho, en una teoría de conjuntos constructiva como la teoría de conjuntos intuicionista , que adopta el axioma completo de separación pero prescinde del principio del tercero excluido, asumir el teorema de Schröder-Bernstein implica este último. ^[19] A su vez, no hay prueba de la conclusión de König en esta o en teorías constructivas más débiles. Por lo tanto, los intuicionistas no aceptan el enunciado del teorema de Schröder-Bernstein. ^[20] ${\displaystyle {\mathsf {IZF}}}$

También hay una prueba que utiliza el teorema del punto fijo de Tarski . ^[21]

Véase también

• Teorema de isomorfismo de Myhill
• Teorema de Netto , según el cual las biyecciones construidas por el teorema de Schröder-Bernstein entre espacios de diferentes dimensiones no pueden ser continuas
• Teorema de Schröder-Bernstein para espacios mensurables
• Teoremas de Schröder-Bernstein para álgebras de operadores
• Propiedad de Schröder-Bernstein

Notas

1. J. König (1906). "Sobre la teoría de los conjuntos". Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences . 143 : 110-112.
2. Felix Hausdorff (2002), Egbert Brieskorn ; Srishti D. Chatterji; et al. (eds.), Grundzüge der Mengenlehre (1. ed.), Berlín/Heidelberg: Springer, pág. 587, ISBN 978-3-540-42224-2– Edición original (1914)
3. Georg Cantor (1887), "Mitteilungen zur Lehre vom Transfiniten", Zeitschrift für Philosophie und philosophische Kritik , 91 : 81-125
   Reimpreso en: Georg Cantor (1932), Adolf Fraenkel (Lebenslauf); Ernst Zermelo (eds.), Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, Berlín: Springer, págs. 378–439Aquí: p.413 abajo
4. Richard Dedekind (1932), Robert Fricke ; Emmy Noether; Øystein Ore (eds.), Gesammelte mathematische Werke, vol. 3, Brunswick: Friedr. Vieweg y Sohn, págs. 447–449 (capítulo 62)
5. Ernst Zermelo (1908), Félix Klein; Walther von Dyck ; David Hilbert; Otto Blumenthal (eds.), "Untersuchungen über die Grundlagen der Mengenlehre I", Mathematische Annalen , 65 (2): 261–281, aquí: p.271–272, doi :10.1007/bf01449999, ISSN  0025-5831, S2CID  120085563
6. Richard Dedekind (1888), ¿Fue sind und was sollen die Zahlen? (2., sin cambios (1893) ed.), Braunschweig: Friedr. Vieweg & Sohn
7. Georg Cantor (1932), Adolf Fraenkel (Lebenslauf); Ernst Zermelo (eds.), Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, Berlín: Springer, págs. 285 ("Satz B")
8. Georg Cantor (1895). "Beiträge zur Begründung der transfiniten Mengenlehre (1)". Annalen Matemáticas . 46 (4): 481–512 (Teorema, ver "Satz B", p.484). doi :10.1007/bf02124929. S2CID  177801164.
9. ( Georg Cantor (1897). "Beiträge zur Begründung der transfiniten Mengenlehre (2)". Mathematische Annalen . 49 (2): 207–246. doi :10.1007/bf01444205. S2CID  121665994.)
10. Friedrich M. Hartogs (1915), Félix Klein; Walther von Dyck; David Hilbert; Otto Blumenthal (eds.), "Über das Problem der Wohlordnung", Mathematische Annalen , 76 (4): 438–443, doi :10.1007/bf01458215, ISSN  0025-5831, S2CID  121598654
11. Ernst Schröder (1896). "Über G. Cantorsche Sätze". Jahresbericht der Deutschen Mathematiker-Vereinigung . 5 : 81–82.
12. Oliver Deiser (2010), Einführung in die Mengenlehre - Die Mengenlehre Georg Cantors und ihre Axiomatisierung durch Ernst Zermelo , Springer-Lehrbuch (3ª, edición corregida), Berlín/Heidelberg: Springer, págs.71, 501, doi :10.1007 /978-3-642-01445-1, ISBN 978-3-642-01444-4
13. Patrick Suppes (1972), Teoría de conjuntos axiomáticos (1. ed.), Nueva York: Dover Publications, pp. 95 y siguientes, ISBN 978-0-486-61630-8
14. Émile Borel (1898), Leçons sur la théorie des fonctions, París: Gauthier-Villars et fils, págs.103 y siguientes
15. Felix Bernstein (1901), Untersuchungen aus der Mengenlehre, Halle a. S.: Buchdruckerei des Waisenhauses
    Reimpreso en: Felix Bernstein (1905), Felix Klein; Walther von Dyck; David Hilbert (eds.), "Untersuchungen aus der Mengenlehre", Mathematische Annalen , 61 (1): 117–155, (teorema, consulte "Satz 1" en la p.121), doi :10.1007/bf01457734, ISSN  0025-5831, S2CID  119658724
16. Ernst Schröder (1898), Kaiserliche Leopoldino-Carolinische Deutsche Akademie der Naturforscher (ed.), "Ueber zwei Definiciónen der Endlichkeit und G. Cantor'sche Sätze", Nova Acta , 71 (6): 303–376 (prueba: p .336–344)
17. Alwin R. Korselt (1911), Félix Klein; Walther von Dyck; David Hilbert; Otto Blumenthal (eds.), "Über einen Beweis des Äquivalenzsatzes", Mathematische Annalen , 70 (2): 294–296, doi :10.1007/bf01461161, ISSN  0025-5831, S2CID  119757900
18. Korselt (1911), pág. 295
19. Pradic, Cécilia; Brown, Chad E. (2019). "Cantor-Bernstein implica medio excluido". arXiv : 1904.09193 [math.LO].
20. Ettore Carruccio (2006). Matemáticas y lógica en la historia y en el pensamiento contemporáneo . Transaction Publishers. pág. 354. ISBN 978-0-202-30850-0.
21. Roland Uhl. "Teorema del punto fijo de Tarski". MathWorld .Ejemplo 3.

Referencias

• Martin Aigner y Gunter M. Ziegler (1998) Demostraciones de EL LIBRO , § 3 Análisis: Conjuntos y funciones, Springer books MR 1723092, quinta edición 2014 MR 3288091, sexta edición 2018 MR 3823190
• Hinkis, Arie (2013), Demostraciones del teorema de Cantor-Bernstein. Una excursión matemática , Science Networks. Historical Studies, vol. 45, Heidelberg: Birkhäuser/Springer, doi :10.1007/978-3-0348-0224-6, ISBN 978-3-0348-0223-9, Sr.  3026479
• Searcóid, Míchaél Ó (2013). "Sobre la historia y las matemáticas del teorema de equivalencia". Mathematical Proceedings of the Royal Irish Academy . 113A (2): 151–68. doi :10.1353/mpr.2013.0006. JSTOR  42912521. S2CID  245841055.

Enlaces externos

• Weisstein, Eric W. "Teorema de Schröder-Bernstein". MundoMatemático .
• Teorema de Cantor-Schroeder-Bernstein en el laboratorio n
• Teorema de Cantor-Bernstein en un semianillo de Marcel Crabbé.
• Este artículo incorpora material del artículo de Citizendium "Teorema_de_Schröder-Bernstein", que está licenciado bajo la Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported pero no bajo la Licencia GFDL .