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 | Un | ≤ | B | y | B | ≤ | Un | , entonces | Un | = | B | ; es decir, A y B son equipotentes . Esta es una característica útil en el ordenamiento de números cardinales .

El teorema lleva el nombre de Felix Bernstein y Ernst Schröder . También se le 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 pruebas).

Prueba

Definición de König de una biyección h : A  →  B a partir de inyecciones de ejemplo dadas f : A  →  B y g : B  →  A . Un elemento en A y B se denota mediante un número y una letra, respectivamente. La secuencia 3 → e → 6 → ... es un tapón A , lo que lleva a las definiciones h (3) =  f (3) =  e , h (6) =  f (6), .... La secuencia d  → 5 →  f  → ... es un tapón B , lo que lleva a h (5) =  g ⁻¹ (5) =  d , .... La secuencia ... →  a  → 1 →  c  → 4 → .. .es doblemente infinito, 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) =  gramo ⁻¹ (2) =  segundo .

The following proof is attributed to Julius König.^[1]

Assume without loss of generality that A and B are disjoint. For any a in A or b in B we can form a unique two-sided sequence of elements that are alternately in A and B, by repeatedly applying ${\displaystyle f}$ and ${\displaystyle g^{-1}}$ to go from A to B and ${\displaystyle g}$ and ${\displaystyle f^{-1}}$ to go from B to A (where defined; the inverses ${\displaystyle f^{-1}}$ and ${\displaystyle g^{-1}}$ are understood as partial functions.)

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

For any particular a, this sequence may terminate to the left or not, at a point where ${\displaystyle f^{-1}}$ or ${\displaystyle g^{-1}}$ is not defined.

By the fact that ${\displaystyle f}$ and ${\displaystyle g}$ are injective functions, each a in A and b in B is in exactly one such sequence to within identity: if an element occurs in two sequences, all elements to the left and to the right must be the same in both, by the definition of the sequences. Therefore, the sequences form a partition of the (disjoint) union of A and B. Hence it suffices to produce a bijection between the elements of A and B in each of the sequences separately, as follows:

Call a sequence an A-stopper if it stops at an element of A, or a B-stopper if it stops at an element of B. Otherwise, call it doubly infinite if all the elements are distinct or cyclic if it repeats. See the picture for examples.

• For an A-stopper, the function ${\displaystyle f}$ is a bijection between its elements in A and its elements in B.
• For a B-stopper, the function ${\displaystyle g}$ is a bijection between its elements in B and its elements in A.
• For a doubly infinite sequence or a cyclic sequence, either ${\displaystyle f}$ or ${\displaystyle g}$ will do ( ${\displaystyle g}$ is used in the picture).

Examples

Bijective function from ${\displaystyle [0,1]\to [0,1)}$

Note: ${\displaystyle [0,1)}$ is the half open set from 0 to 1, including the boundary 0 and excluding the boundary 1.

Let ${\displaystyle f:[0,1]\to [0,1)\;}$ with ${\displaystyle f(x)=x/2;\;}$ and ${\displaystyle g:[0,1)\to [0,1]\;}$ with ${\displaystyle g(x)=x;\;}$ the two injective functions as in the previous procedure of proof.

In line with that procedure ${\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]\setminus 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);\;}$

Entonces uno puede usar 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 cuál 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 sigue siendo 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 forma más sencilla de utilizar la definición de función (ya 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 agrega Cantor porque estableció el teorema por primera vez en 1887, mientras que el nombre de Schröder a menudo se omite porque su prueba resultó ser defectuosa, mientras que el nombre de Richard Dedekind , quien fue el primero en demostrarlo, no está relacionado con el teorema. Según Bernstein, Cantor había sugerido el teorema de equivalencia de nombres (Äquivalenzsatz). ^[2]

Primera declaració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 demostración ni se lo 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 expone el teorema en su primer artículo sobre teoría de conjuntos y números transfinitos. Lo obtiene como una fácil consecuencia del orden lineal de los números cardinales. ^{[7] [8] [9]} Sin embargo, no pudo demostrar este último teorema, que en 1915 se demostró que era equivalente al axioma de elección de Friedrich Moritz Hartogs . ^{[2] [10]}
• 1896 Schröder anuncia una demostración (como corolario de un teorema de Jevons ). ^[11]
• 1897 Bernstein , un estudiante de 19 años en el Seminario de Cantor, presenta su prueba. ^{[12] [13]}
• 1897 Casi al mismo tiempo, pero de forma independiente, Schröder encuentra una prueba. ^{[12] [13]}
• 1897 Después de una visita de Bernstein, Dedekind demuestra de forma independiente el teorema por segunda vez.
• 1898 Émile Borel publica la prueba de Bernstein (que no se basa en el axioma de elección) en su libro sobre funciones. ^[14] (Comunicado por Cantor en el Congreso Internacional de Matemáticos de 1897 en Zurich.) Ese 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, resulta defectuosa por Alwin Reinhold Korselt en 1902 (justo antes de la muerte de Schröder), ^[17] (confirmada por Schröder), ^{[2] [18]} pero se publica el artículo de Korselt sólo en 1911.

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

Requisitos previos

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

Por otro lado, la prueba de König utiliza el principio del tercero excluido para sacar una conclusión mediante el 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, asumiendo que el teorema de Schröder-Bernstein implica este último. ^[19] A su vez, ni en esta teoría constructiva ni en las más débiles hay pruebas de la conclusión de König. Por tanto, los intuicionistas no aceptan el enunciado del teorema de Schröder-Bernstein. ^[20] ${\displaystyle {\mathsf {IZF}}}$

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

Ver también

• Teorema del 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
• Schröder–Bernstein theorem for measurable spaces
• Schröder–Bernstein theorems for operator algebras
• Schröder–Bernstein property

Notes

1. J. König (1906). "Sur la théorie des ensembles". 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.), Berlin/Heidelberg: Springer, p. 587, ISBN 978-3-540-42224-2 – Original edition (1914)
3. Georg Cantor (1887), "Mitteilungen zur Lehre vom Transfiniten", Zeitschrift für Philosophie und philosophische Kritik, 91: 81–125
   Reprinted in: Georg Cantor (1932), Adolf Fraenkel (Lebenslauf); Ernst Zermelo (eds.), Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, Berlin: Springer, pp. 378–439 Here: p.413 bottom
4. Richard Dedekind (1932), Robert Fricke; Emmy Noether; Øystein Ore (eds.), Gesammelte mathematische Werke, vol. 3, Braunschweig: Friedr. Vieweg & Sohn, pp. 447–449 (Ch.62)
5. Ernst Zermelo (1908), Felix Klein; Walther von Dyck; David Hilbert; Otto Blumenthal (eds.), "Untersuchungen über die Grundlagen der Mengenlehre I", Mathematische Annalen, 65 (2): 261–281, here: p.271–272, doi:10.1007/bf01449999, ISSN 0025-5831, S2CID 120085563
6. Richard Dedekind (1888), Was sind und was sollen die Zahlen? (2., unchanged (1893) ed.), Braunschweig: Friedr. Vieweg & Sohn
7. Georg Cantor (1932), Adolf Fraenkel (Lebenslauf); Ernst Zermelo (eds.), Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, Berlin: Springer, pp. 285 ("Satz B")
8. Georg Cantor (1895). "Beiträge zur Begründung der transfiniten Mengenlehre (1)". Mathematische Annalen. 46 (4): 481–512 (Theorem see "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, págs. 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.295
19. Prádic, Pierre; Marrón, Chad E. (2019). "Cantor-Bernstein implica medio excluido". arXiv : 1904.09193 [matemáticas.LO].
20. Ettore Carruccio (2006). Matemáticas y Lógica en la Historia y en el Pensamiento Contemporáneo . Editores de transacciones. pag. 354.ISBN​ 978-0-202-30850-0.
21. R. Uhl, "Teorema del punto fijo de Tarski", de MathWorld , un recurso web de Wolfram, creado por Eric W. Weisstein. (Ejemplo 3)

Referencias

• Martin Aigner y Gunter M. Ziegler (1998) Pruebas del LIBRO , § 3 Análisis: conjuntos y funciones, libros Springer MR 1723092, quinta edición 2014 MR 3288091, sexta edición 2018 MR 3823190
• Hinkis, Arie (2013), Pruebas del teorema de Cantor-Bernstein. Una excursión matemática , Redes Científicas. Estudios históricos, vol. 45, Heidelberg: Birkhäuser/Springer, doi :10.1007/978-3-0348-0224-6, ISBN 978-3-0348-0223-9, señor  3026479
• Searcóid, Míchaél Ó (2013). "Sobre la historia y las matemáticas del teorema de equivalencia". Actas matemáticas de la Real Academia Irlandesa . 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 semiring de Marcel Crabbé.
• Este artículo incorpora material del artículo de Citizendium "Schröder-Bernstein_theorem", que tiene la licencia Creative Commons Attribution-ShareAlike 3.0 Unported , pero no la GFDL .