Teorema del isomorfismo de Cantor

Unicidad de órdenes lineales densos contables.

En la teoría del orden y la teoría de modelos , ramas de las matemáticas, el teorema de isomorfismo de Cantor establece que cada dos órdenes lineales densos e ilimitados contables son isomorfos de orden . Por ejemplo, la función del signo de interrogación de Minkowski produce un isomorfismo (una correspondencia uno a uno que preserva el orden) entre el orden numérico de los números racionales y el ordenamiento numérico de los racionales diádicos .

El teorema lleva el nombre de Georg Cantor , quien lo publicó por primera vez en 1895, usándolo para caracterizar el orden (incontable) de los números reales . Puede demostrarse mediante un método de ida y vuelta que a veces también se atribuye a Cantor, pero que en realidad fue publicado más tarde por Felix Hausdorff . El mismo método de ida y vuelta también demuestra que los órdenes densos e ilimitados contables son altamente simétricos y pueden aplicarse a otros tipos de estructuras. Sin embargo, la prueba original de Cantor sólo utilizó la mitad "de salida" de este método. En términos de teoría de modelos , el teorema del isomorfismo se puede expresar diciendo que la teoría de primer orden de órdenes lineales densos ilimitados es contablemente categórica , lo que significa que tiene un solo modelo contable, hasta la equivalencia lógica.

Una aplicación del teorema del isomorfismo de Cantor implica la lógica temporal , un método para utilizar la lógica para razonar sobre el tiempo. En esta aplicación, el teorema implica que es suficiente usar intervalos de números racionales para modelar intervalos de tiempo: usar números irracionales para este propósito no conducirá a ningún aumento en la potencia lógica.

Declaración y ejemplos

La función de signo de interrogación de Minkowski proporciona un isomorfismo concreto de racionales a racionales diádicos

El teorema del isomorfismo de Cantor se enuncia utilizando los siguientes conceptos:

• Un orden lineal u orden total se define por un conjunto de elementos y una operación de comparación que da un orden a cada par de elementos distintos y obedece a la ley transitiva . ^{[1] [2]} Los ordenamientos numéricos familiares de los números enteros , números racionales y números reales son todos ejemplos de órdenes lineales . ^[2]
• Ilimitación significa que el ordenamiento no contiene un elemento mínimo o máximo. Esto es diferente del concepto de conjunto acotado en un espacio métrico . Por ejemplo, el intervalo abierto (0,1) es ilimitado como conjunto ordenado, aunque está acotado como subconjunto de los números reales, porque ni su mínimo 0 ni su supremo 1 pertenecen al intervalo. ^[1] Los números enteros, racionales y reales también son ilimitados. ^[2]
• Un ordenamiento es denso cuando cada par de elementos tiene otro elemento entre ellos. ^[1] Esto es diferente de ser un conjunto topológicamente denso dentro de los números reales . ^[2] Los números racionales y los números reales son densos en este sentido, ya que la media aritmética de dos números cualesquiera pertenece al mismo conjunto y se encuentra entre ellos, pero los números enteros no son densos porque no hay otro número entero entre dos números enteros consecutivos . ^[3]
• Tanto los números enteros como los racionales forman conjuntos contables , pero los números reales no, según un resultado diferente de Cantor, su prueba de que los números reales son incontables . ^[2]
• Dos órdenes lineales son isomórficos de orden cuando existe una correspondencia uno a uno entre ellos que preserva su ordenamiento. ^{[1] [2]} Por ejemplo, los números enteros y pares son de orden isomórfico, bajo una biyección que multiplica cada número entero por dos. ^[3]

Con estas definiciones en la mano, el teorema del isomorfismo de Cantor establece que cada dos órdenes lineales densos contables ilimitados son de orden isomorfo. ^[1]

Dentro de los números racionales, ciertos subconjuntos también son contables, ilimitados y densos. Los números racionales en el intervalo unitario abierto son un ejemplo. Otro ejemplo es el conjunto de números racionales diádicos , los números que se pueden expresar como una fracción con un numerador entero y una potencia de dos como denominador. Según el teorema del isomorfismo de Cantor, los números racionales diádicos son de orden isomorfos al conjunto completo de números racionales. En este ejemplo, la función de signo de interrogación de Minkowski proporciona un isomorfismo de orden explícito . ^[4] Otro ejemplo de un orden lineal denso ilimitado contable lo da el conjunto de números algebraicos reales , las raíces reales de polinomios con coeficientes enteros. En este caso, son un superconjunto de números racionales, pero nuevamente son de orden isomorfos. ^[5] También es posible aplicar el teorema a otros órdenes lineales cuyos elementos no están definidos como números. Por ejemplo, las cadenas binarias que terminan en 1, en su orden lexicográfico , forman otro orden isomórfico. ^[6]

Pruebas

Una prueba del teorema del isomorfismo de Cantor, en algunas fuentes llamada "la prueba estándar", ^[7] utiliza el método de ida y vuelta . Esta prueba construye un isomorfismo entre dos órdenes dados cualesquiera, utilizando un algoritmo codicioso , en un orden dado por una enumeración contable de los dos ordenamientos. Más detalladamente, la prueba mantiene dos subconjuntos finitos isomorfos de orden y de los dos órdenes dados, inicialmente vacíos. Aumenta repetidamente los tamaños de y agregando un nuevo elemento de un orden, el primer elemento faltante en su enumeración, y combinándolo con un elemento equivalente al orden del otro orden, cuya existencia se ha demostrado utilizando la densidad y la falta de puntos finales del orden. Los dos ordenamientos cambian de roles en cada paso: la prueba encuentra el primer elemento faltante de primer orden, lo agrega a , lo relaciona con un elemento de segundo orden y lo agrega a ; luego encuentra el primer elemento faltante de segundo orden, lo agrega a , lo relaciona con un elemento de primer orden y lo agrega a , etc. Cada elemento de cada orden eventualmente coincide con un elemento de orden equivalente del otro ordenamiento, por lo que los dos ordenamientos son isomórficos. ^[8] ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$

Aunque el método de ida y vuelta también se ha atribuido a Cantor, la publicación original de Cantor de este teorema en 1895-1897 utilizó una prueba diferente. ^[8] En una investigación de la historia de este teorema realizada por el lógico Charles L. Silver, el primer ejemplo de la prueba de ida y vuelta encontrada por Silver se encontraba en un libro de texto de 1914 de Felix Hausdorff , su Grundzüge der Mengenlehre . ^[8]

En lugar de construir subconjuntos isomorfos de orden e ir "de ida y vuelta" entre la enumeración de primer orden y la enumeración de segundo orden, la prueba original de Cantor sólo utiliza la mitad "de ida y vuelta" del método de ida y vuelta. . ^[1] Aumenta repetidamente los dos conjuntos finitos y agregando al primer elemento faltante de la enumeración de primer orden, y agregando al elemento equivalente de orden que está primero en la enumeración de segundo orden. Naturalmente, esto encuentra una equivalencia entre el primer orden y un subconjunto del segundo orden, y Cantor luego argumenta que se incluye todo el segundo orden. ^{[1] [8]} ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

La prueba de ida y vuelta se ha formalizado como una prueba verificada por computadora utilizando Coq , un demostrador de teoremas interactivo . Este proceso de formalización condujo a un resultado reforzado de que cuando dos órdenes lineales enumerables computablemente tienen un predicado de comparación computable y funciones computables que representan sus propiedades de densidad e ilimitación, entonces el isomorfismo entre ellos también es computable. ^[9]

Teoría de modelos

Una forma de describir el teorema del isomorfismo de Cantor utiliza el lenguaje de la teoría de modelos . La teoría de primer orden de órdenes lineales densos ilimitados consta de oraciones en lógica matemática sobre variables que representan los elementos de un orden, con una relación binaria utilizada como operación de comparación del orden. Aquí, una oración significa una fórmula bien formada que no tiene variables libres . Estas oraciones incluyen ambos axiomas, que formulan en términos lógicos los requisitos de un orden lineal denso, y todas las demás oraciones que pueden demostrarse como consecuencias lógicas de esos axiomas. Los axiomas de este sistema se pueden expresar como: ^{[10] [11]}

Un modelo de esta teoría es cualquier sistema de elementos y una relación de comparación que obedece a todos los axiomas; es un modelo contable cuando el sistema de elementos forma un conjunto contable . Por ejemplo, la relación de comparación habitual de los números racionales es un modelo contable de esta teoría. El teorema del isomorfismo de Cantor se puede expresar diciendo que la teoría de primer orden de órdenes lineales densos ilimitados es contablemente categórica : tiene un solo modelo contable, hasta la equivalencia lógica. ^{[1] [12]} Sin embargo, no es categórico para cardinalidades superiores : para cualquier cardinalidad superior , existen múltiples órdenes lineales ilimitados, densos y no equivalentes con la misma cardinalidad. ^[13]

Se puede utilizar un método de eliminación de cuantificadores en la teoría de primer orden de órdenes lineales densos ilimitados para demostrar que es una teoría completa . Esto significa que cada oración lógica en el lenguaje de esta teoría es un teorema, es decir, demostrable como consecuencia lógica de los axiomas, o la negación de un teorema. Esto está estrechamente relacionado con ser categórico (una oración es un teorema si es cierta para el modelo contable único; consulte la prueba de Łoś-Vaught ), pero pueden existir múltiples modelos distintos que tengan la misma teoría completa. En particular, tanto el ordenamiento de los números racionales como el ordenamiento de los números reales son modelos de la misma teoría, aunque sean modelos diferentes. La eliminación de cuantificadores también se puede utilizar en un algoritmo para decidir si una oración determinada es un teorema. ^[11]

Resultados relacionados

La gráfica de un automorfismo de orden lineal por partes de números racionales que toma los cuatro puntos {1,4,5,8} a ​​{3,4,6,7}

El mismo método de ida y vuelta utilizado para demostrar el teorema del isomorfismo de Cantor también demuestra que los órdenes lineales densos contables son altamente simétricos. Sus simetrías se denominan automorfismos de orden y consisten en biyecciones que preservan el orden de todo el orden lineal hacia sí mismo. Mediante el método de ida y vuelta, cada orden lineal denso contable tiene automorfismos de orden que asignan cualquier conjunto de puntos a cualquier otro conjunto de puntos. Esto también se puede probar directamente para el orden de los racionales, mediante la construcción de un automorfismo de orden lineal por partes con puntos de interrupción en los puntos dados. Esta equivalencia de conjuntos de puntos de todos los elementos se resume diciendo que el grupo de simetrías de un orden lineal denso contable es "altamente homogéneo". Sin embargo, no existe un automorfismo de orden que mapee un par ordenado de puntos en su reverso, por lo que estas simetrías no forman un grupo 2-transitivo . ^[1] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

El teorema del isomorfismo se puede extender a coloraciones de un orden lineal contable denso ilimitado, con un conjunto finito o contable de colores, de modo que cada color es denso, en el sentido de que existe un punto de ese color entre otros dos puntos cualesquiera del todo. ordenar. Los subconjuntos de puntos con cada color dividen el orden en una familia de ordenamientos lineales contables densos e ilimitados. Cualquier partición de un ordenamiento lineal contable denso e ilimitado en subconjuntos, con la propiedad de que cada subconjunto es ilimitado (dentro del conjunto completo, no sólo en sí mismo) y denso (nuevamente, dentro del conjunto completo) proviene de una coloración de esta manera. Cada dos coloraciones con el mismo número de colores son de orden isomórfico, bajo cualquier permutación de sus colores. Bhattacharjee et al. (1997) dan como ejemplo la partición de los números racionales en racionales diádicos y su complemento; Estos dos conjuntos son densos entre sí y su unión tiene un isomorfismo de orden con respecto a cualquier otro par de órdenes lineales ilimitados que sean contables y densos entre sí. A diferencia del teorema del isomorfismo de Cantor, la prueba necesita el argumento completo de ida y vuelta, y no sólo el argumento de "avance" . ^[1]

Cantor utilizó el teorema del isomorfismo para caracterizar el orden de los números reales , un conjunto incontable. A diferencia de los números racionales, los números reales son completos de Dedekind , lo que significa que cada subconjunto de reales que tiene un límite superior finito tiene un límite superior mínimo real. Contienen los números racionales, que son densos en los números reales. Al aplicar el teorema del isomorfismo, Cantor demostró que siempre que un ordenamiento lineal tiene las mismas propiedades de ser completo de Dedekind y contener un subconjunto denso e ilimitado contable, debe ser de orden isomorfo a los números reales. ^[14] El problema de Suslin pregunta si los órdenes que tienen ciertas otras propiedades del orden de los números reales, incluida la ilimitación, la densidad y la completitud, deben ser de orden isomorfo a los reales; la verdad de esta afirmación es independiente de la teoría de conjuntos de Zermelo-Fraenkel con el axioma de elección (ZFC). ^[15]

Aunque los ordenamientos densos ilimitados incontables pueden no ser isomorfos de orden, del método de ida y vuelta se deduce que dos ordenamientos cualesquiera son elementalmente equivalentes . ^{[7] [16]} Otra consecuencia de la prueba de Cantor es que todo orden lineal finito o contable puede integrarse en los racionales, o en cualquier ordenamiento denso ilimitado. Al llamar a esto un resultado "bien conocido" de Cantor, Wacław Sierpiński demostró un resultado análogo para una cardinalidad superior: suponiendo la hipótesis del continuo , existe un ordenamiento lineal de cardinalidad en el que se pueden incluir todos los demás ordenamientos lineales de cardinalidad. ^[17] El axioma de Baumgartner , formulado por James Earl Baumgartner en 1973 para estudiar la hipótesis del continuo, se refiere a conjuntos densos de números reales, conjuntos ilimitados con la propiedad de que cada dos elementos están separados exactamente por otros elementos. Afirma que cada dos de estos conjuntos son de orden isomorfo, proporcionando de esta manera otro análogo de cardinalidad superior del teorema de isomorfismo de Cantor ( se define como la cardinalidad del conjunto de todos los ordinales contables). El axioma de Baumgartner es consistente con ZFC y la negación de la hipótesis del continuo, e implícito en el axioma de forzamiento adecuado , ^[18] pero independiente del axioma de Martin . ^[19] ${\displaystyle \aleph _{1}}$ ${\displaystyle \aleph _{1}}$ ${\displaystyle \aleph _{1}}$ ${\displaystyle \aleph _{1}}$ ${\displaystyle \aleph _{1}}$

En lógica temporal , se puede demostrar que varias formalizaciones del concepto de intervalo de tiempo son equivalentes a definir un intervalo por un par de elementos distintos de un orden lineal denso e ilimitado. Esta conexión implica que estas teorías también son contablemente categóricas y pueden modelarse únicamente mediante intervalos de números racionales. ^{[20] [21]}

Referencias

1. Bhattacharjee, Meenaxi; Macpherson, Dugald; Möller, Rögnvaldur G.; Neumann, Peter M. (1997), "Números racionales", Notas sobre grupos de permutación infinitos , Textos y lecturas de matemáticas, vol. 12, Berlín: Springer-Verlag, págs. 77–86, doi :10.1007/978-93-80250-91-5_9, ISBN 81-85931-13-5, señor  1632579
2. Dasgupta, Abhijit (2014), "Capítulos 7 y 8: Órdenes y tipos de órdenes; Órdenes densas y completas", Teoría de conjuntos , Springer New York, págs. 131-174, doi : 10.1007/978-1-4614-8854 -5
3. Chekmasov, Andrei (23 de octubre de 2019), "Curiosidades de los conjuntos ordenados linealmente", Chalkdust
4. Girgensohn, Roland (1996), "Construcción de funciones singulares mediante fracciones de Farey", Journal of Mathematical Analysis and Applications , 203 (1): 127–141, doi : 10.1006/jmaa.1996.0370 , MR  1412484
5. Bosi, G.; Mehta, GB (2002), "Existencia de una función de utilidad continua o semicontinua: un enfoque unificado y una prueba elemental", Journal of Mathematical Economics , 38 (3): 311–328, doi :10.1016/S0304-4068(02) 00058-7, SEÑOR  1940365; ver Observación 3, p. 323
6. Lohrey, Markus; Mathissen, Christian (2013), "Isomorfismo de palabras y árboles regulares", Información y Computación , 224 : 71–105, arXiv : 1102.2782 , doi : 10.1016/j.ic.2013.01.002 , MR  3016459
7. Bryant, Ross (2006), Un cálculo del rango de isomorfismo parcial en estructuras ordinales (tesis doctoral), Universidad del Norte de Texas, p. 1, 305292986
8. Silver, Charles L. (1994), "¿Quién inventó el argumento de ida y vuelta de Cantor?", Modern Logic , 4 (1): 74–78, MR  1253680
9. Kirst, Dominik (2022), "Argumentos computacionales de ida y vuelta en la teoría de tipos constructivos", en Andronick, junio; de Moura, Leonardo (eds.), 13.ª Conferencia internacional sobre demostración interactiva de teoremas, ITP 2022, 7 al 10 de agosto de 2022, Haifa, Israel , LIPIcs, vol. 237, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 22:1–22:12, doi :10.4230/LIPIcs.ITP.2022.22
10. Para esta axiomatización de órdenes lineales estrictos, consulte: Goldrei, Derek (2005), Cálculo proposicional y predicado: un modelo de argumento , Springer, p. 193, ISBN 9781846282294. Los axiomas se pueden formular lógicamente utilizando una comparación estricta o una comparación no estricta, pero la comparación estricta simplifica la expresión de los axiomas para las propiedades de ser ilimitado y denso. Nótese que no es necesario especificar que estos órdenes son antisimétricos, es decir, que ; esto es una consecuencia de la irreflexividad y la transitividad. ${\displaystyle <}$ ${\displaystyle \leq }$ ${\displaystyle a<b\Rightarrow \lnot (b<a)}$
11. Worrell, James (2016), "Teorías decidibles" (PDF) , Lógica y prueba (apuntes de la conferencia), Universidad de Oxford; Worrell utiliza una axiomatización diferente pero equivalente para órdenes lineales estrictos y combina los dos axiomas de ilimitación en un solo axioma.
12. Büchi, J. Richard ; Danhof, Kenneth J. (1973), "Variaciones sobre un tema de Cantor en la teoría de estructuras relacionales", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 19 : 411–426, doi :10.1002/malq.19730192604, MR  0337567
13. Morley, Michael (1965), "Categoricidad en el poder", Transactions of the American Mathematical Society , 114 : 514–538, doi : 10.2307/1994188 , MR  0175782
14. Jech, Thomas (2003), Teoría de conjuntos , Springer Monographs in Mathematics (edición del tercer milenio), Berlín: Springer-Verlag, Teorema 4.3, p. 38, doi :10.1007/3-540-44761-X, ISBN 3-540-44085-2, SEÑOR  1940513
15. Devlin, Keith J .; Johnsbråten, Håvard (1974), El problema de Souslin , Lecture Notes in Mathematics, vol. 405, Berlín y Nueva York: Springer-Verlag, MR  0384542
16. Langford, CH (1926-1927), "Algunos teoremas sobre deducibilidad", Annals of Mathematics , segunda serie, 28 (1–4): 16–40, doi :10.2307/1968352, MR  1502760
17. Sierpiński, Wacław (1932), "Généralisation d'un théorème de Cantor concernant les ensembles ordonnés dénombrables", Fundamenta Mathematicae (en francés), 18 : 280–284, doi : 10.4064/fm-18-1-280-284 , Zbl  0004.20502
18. Baumgartner, James E. (1973), "Todos los conjuntos densos de reales pueden ser isomórficos", Fundamenta Mathematicae , 79 (2): 101–106, doi : 10.4064/fm-79-2-101-106 , SEÑOR  0317934 ${\displaystyle \aleph _{1}}$
19. Abraham, Uri; Shelah, Saharon (1981), "El axioma de Martin no implica que cada dos conjuntos de reales densos sean isomórficos", Israel Journal of Mathematics , 38 (1–2): 161–176, doi :10.1007/BF02761858, MR  0599485 ${\displaystyle \aleph _{1}}$
20. van Benthem, Johan (1984), "Lógica tensa y tiempo", Notre Dame Journal of Formal Logic , 25 (1): 1–16, doi : 10.1305/ndjfl/1093870515 , SEÑOR  0723616
21. Ladkin, Peter B. (1987), "Modelos de axiomas para intervalos de tiempo", en Forbus, Kenneth D.; Shrobe, Howard E. (eds.), Actas de la VI Conferencia Nacional sobre Inteligencia Artificial. Seattle, WA, EE. UU., julio de 1987 , Morgan Kaufmann, págs. 234-239