Teorema de compacidad

Teorema

En lógica matemática , el teorema de compacidad establece que un conjunto de oraciones de primer orden tiene un modelo si y solo si cada subconjunto finito de este tiene un modelo. Este teorema es una herramienta importante en la teoría de modelos , ya que proporciona un método útil (pero generalmente no efectivo ) para construir modelos de cualquier conjunto de oraciones que sea finitamente consistente .

El teorema de compacidad para el cálculo proposicional es una consecuencia del teorema de Tichonoff (que dice que el producto de espacios compactos es compacto) aplicado a espacios de Stone compactos , ^[1] de ahí el nombre del teorema. Asimismo, es análogo a la propiedad de intersección finita que caracteriza la compacidad en espacios topológicos : una colección de conjuntos cerrados en un espacio compacto tiene una intersección no vacía si cada subcolección finita tiene una intersección no vacía.

El teorema de compacidad es una de las dos propiedades clave, junto con el teorema de Löwenheim-Skolem descendente , que se utiliza en el teorema de Lindström para caracterizar la lógica de primer orden. Aunque existen algunas generalizaciones del teorema de compacidad a lógicas que no son de primer orden, el teorema de compacidad en sí no se cumple en ellas, excepto en un número muy limitado de ejemplos. ^[2]

Historia

Kurt Gödel demostró el teorema de compacidad numerable en 1930. Anatoly Maltsev demostró el caso incontable en 1936. ^{[3] [4]}

Aplicaciones

El teorema de compacidad tiene muchas aplicaciones en la teoría de modelos; aquí se esbozan algunos resultados típicos.

Principio de Robinson

El teorema de compacidad implica el siguiente resultado, enunciado por Abraham Robinson en su tesis de 1949 .

Principio de Robinson: ^{[5] [6]} Si una oración de primer orden se cumple en todo campo de característica cero, entonces existe una constante tal que la oración se cumple para todo campo de característica mayor que Esto se puede ver de la siguiente manera: supongamos que es una oración que se cumple en todo campo de característica cero. Entonces su negación junto con los axiomas de campo y la secuencia infinita de oraciones no es satisfacible (porque no hay ningún campo de característica 0 en el que se cumpla, y la secuencia infinita de oraciones asegura que cualquier modelo sería un campo de característica 0). Por lo tanto, hay un subconjunto finito de estas oraciones que no es satisfacible. debe contener porque de lo contrario sería satisfacible. Debido a que agregar más oraciones a no cambia la insatisfacibilidad, podemos suponer que contiene los axiomas de campo y, para algunas las primeras oraciones de la forma Sea contiene todas las oraciones de excepto Entonces cualquier campo con una característica mayor que es un modelo de y junto con no es satisfacible. Esto significa que debe cumplirse en cada modelo, lo que significa precisamente que se cumple en cada campo de característica mayor que Esto completa la prueba. ${\displaystyle p}$ ${\displaystyle p.}$ ${\displaystyle \varphi }$ ${\displaystyle \lnot \varphi ,}$ $${\displaystyle 1+1\neq 0,\;\;1+1+1\neq 0,\;\ldots }$$ ${\displaystyle \lnot \varphi }$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle \lnot \varphi }$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle k,}$ ${\displaystyle k}$ ${\displaystyle 1+1+\cdots +1\neq 0.}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle \lnot \varphi .}$ ${\displaystyle k}$ ${\displaystyle B,}$ ${\displaystyle \lnot \varphi }$ ${\displaystyle B}$ ${\displaystyle \varphi }$ ${\displaystyle B,}$ ${\displaystyle \varphi }$ ${\displaystyle k.}$

El principio de Lefschetz , uno de los primeros ejemplos de un principio de transferencia , extiende este resultado. Una oración de primer orden en el lenguaje de los anillos es verdadera en algún (o equivalentemente, en cada ) cuerpo algebraicamente cerrado de característica 0 (como los números complejos , por ejemplo) si y solo si existen infinitos primos para que es verdadero en algún cuerpo algebraicamente cerrado de característica en cuyo caso es verdadero en todos los cuerpos algebraicamente cerrados de característica no 0 suficientemente grande ^[5] Una consecuencia es el siguiente caso especial del teorema de Ax-Grothendieck : todos los polinomios complejos inyectivos son sobreyectivos ^[5] (de hecho, incluso se puede demostrar que su inverso también será un polinomio). ^[7] De hecho, la conclusión de sobreyectividad sigue siendo verdadera para cualquier polinomio inyectivo donde es un cuerpo finito o el cierre algebraico de tal cuerpo. ^[7] ${\displaystyle \varphi }$ ${\displaystyle p}$ ${\displaystyle \varphi }$ ${\displaystyle p,}$ ${\displaystyle \varphi }$ ${\displaystyle p.}$ ${\displaystyle \mathbb {C} ^{n}\to \mathbb {C} ^{n}}$ ${\displaystyle F^{n}\to F^{n}}$ ${\displaystyle F}$

Teorema de Löwenheim-Skolem ascendente

Una segunda aplicación del teorema de compacidad muestra que cualquier teoría que tenga modelos finitos arbitrariamente grandes, o un único modelo infinito, tiene modelos de cardinalidad arbitrariamente grande (este es el teorema de Löwenheim-Skolem ascendente ). Entonces, por ejemplo, hay modelos no estándar de aritmética de Peano con incontables 'números naturales'. Para lograr esto, sea la teoría inicial y sea cualquier número cardinal . Agregue al lenguaje de un símbolo constante para cada elemento de Luego agregue a una colección de oraciones que digan que los objetos denotados por dos símbolos constantes distintos de la nueva colección son distintos (esta es una colección de oraciones). Dado que cada subconjunto finito de esta nueva teoría es satisfacible por un modelo finito suficientemente grande de o por cualquier modelo infinito, toda la teoría extendida es satisfacible. Pero cualquier modelo de la teoría extendida tiene cardinalidad al menos . ${\displaystyle T}$ ${\displaystyle \kappa }$ ${\displaystyle T}$ ${\displaystyle \kappa .}$ ${\displaystyle T}$ ${\displaystyle \kappa ^{2}}$ ${\displaystyle T,}$ ${\displaystyle \kappa }$

Análisis no estándar

Una tercera aplicación del teorema de compacidad es la construcción de modelos no estándar de los números reales, es decir, extensiones consistentes de la teoría de los números reales que contienen números "infinitesimales". Para ver esto, sea una axiomatización de primer orden de la teoría de los números reales. Considérese la teoría obtenida añadiendo un nuevo símbolo constante al lenguaje y adjuntando al axioma y los axiomas para todos los enteros positivos Claramente, los números reales estándar son un modelo para cada subconjunto finito de estos axiomas, porque los números reales satisfacen todo en y, mediante la elección adecuada de pueden hacerse para satisfacer cualquier subconjunto finito de los axiomas sobre Por el teorema de compacidad, hay un modelo que satisface y también contiene un elemento infinitesimal ${\displaystyle \Sigma }$ ${\displaystyle \varepsilon }$ ${\displaystyle \Sigma }$ ${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon <{\tfrac {1}{n}}}$ ${\displaystyle n.}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \Sigma }$ ${\displaystyle \varepsilon ,}$ ${\displaystyle \varepsilon .}$ ${\displaystyle {}^{*}\mathbb {R} }$ ${\displaystyle \Sigma }$ ${\displaystyle \varepsilon .}$

Un argumento similar, esta vez adjunto a los axiomas, etc., muestra que la existencia de números con magnitudes infinitamente grandes no puede descartarse mediante ninguna axiomatización de los reales. ^[8] ${\displaystyle \omega >0,\;\omega >1,\ldots ,}$ ${\displaystyle \Sigma }$

Se puede demostrar que los números hiperreales satisfacen el principio de transferencia : ^[9] una oración de primer orden es verdadera de si y solo si es verdadera de ${\displaystyle {}^{*}\mathbb {R} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle {}^{*}\mathbb {R} .}$

Pruebas

El teorema de compacidad se puede demostrar utilizando el teorema de completitud de Gödel , que establece que un conjunto de oraciones es satisfacible si y solo si no se puede demostrar ninguna contradicción a partir de él. Dado que las demostraciones son siempre finitas y, por lo tanto, involucran solo un número finito de las oraciones dadas, se deduce el teorema de compacidad. De hecho, el teorema de compacidad es equivalente al teorema de completitud de Gödel, y ambos son equivalentes al teorema del ideal primo de Boole , una forma débil del axioma de elección . ^[10]

Gödel demostró originalmente el teorema de compacidad de esta manera, pero más tarde se encontraron algunas pruebas "puramente semánticas" del teorema de compacidad; es decir, pruebas que se refieren a la verdad pero no a la demostrabilidad . Una de esas pruebas se basa en ultraproductos que dependen del axioma de elección, como sigue:

Demostración : Fijemos un lenguaje de primer orden y sea una colección de -oraciones tales que cada subcolección finita de -oraciones, de tiene un modelo. También sea el producto directo de las estructuras y sea la colección de subconjuntos finitos de Para cada sea La familia de todos estos conjuntos genera un filtro apropiado , por lo que hay un ultrafiltro que contiene todos los conjuntos de la forma ${\displaystyle L,}$ ${\displaystyle \Sigma }$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle i\subseteq \Sigma }$ ${\displaystyle {\mathcal {M}}_{i}.}$ ${\textstyle \prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}}$ ${\displaystyle I}$ ${\displaystyle \Sigma .}$ ${\displaystyle i\in I,}$ ${\displaystyle A_{i}=\{j\in I:j\supseteq i\}.}$ ${\displaystyle A_{i}}$ ${\displaystyle U}$ ${\displaystyle A_{i}.}$

Ahora bien, para cualquier oración en ${\displaystyle \varphi }$ ${\displaystyle \Sigma :}$

• El conjunto esta en ${\displaystyle A_{\{\varphi \}}}$ ${\displaystyle U}$
• siempre que entonces por lo tanto se cumple en ${\displaystyle j\in A_{\{\varphi \}},}$ ${\displaystyle \varphi \in j,}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {M}}_{j}}$
• el conjunto de todos con la propiedad que se cumple en es un superconjunto de por lo tanto también en ${\displaystyle j}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {M}}_{j}}$ ${\displaystyle A_{\{\varphi \}},}$ ${\displaystyle U}$

El teorema de Łoś ahora implica que se cumple en el ultraproducto Por lo tanto, este ultraproducto satisface todas las fórmulas en ${\displaystyle \varphi }$ ${\textstyle \prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}/U.}$ ${\displaystyle \Sigma .}$

Véase también

• Teorema de compacidad en el sentido de las barras
• Teorema de Herbrand  : reducción de la lógica matemática de primer orden a la lógica proposicionalPáginas que muestran descripciones de wikidata como alternativa
• Lista de temas de álgebra de Boole
• Teorema de Löwenheim-Skolem  : Existencia y cardinalidad de modelos de teorías lógicas

Notas

1. Véase Truss (1997).
2. J. Barwise, S. Feferman, eds., Model-Theoretic Logics (Nueva York: Springer-Verlag, 1985) [1], en particular, Makowsky, JA Capítulo XVIII: Compacidad, incrustaciones y definabilidad. 645--716, véanse los teoremas 4.5.9, 4.6.12 y la proposición 4.6.9. Para lógicas compactas para una noción extendida de modelo, véase Ziegler, M. Capítulo XV: Teoría de modelos topológicos. 557--577. Para lógicas sin la propiedad de relativización es posible tener simultáneamente compacidad e interpolación, mientras que el problema sigue abierto para lógicas con relativización. Véase Xavier Caicedo, A Simple Solution to Friedman's Fourth Problem, J. Symbolic Logic, Volumen 51, Número 3 (1986), 778-784. doi :10.2307/2274031 JSTOR  2274031
3. Vaught, Robert L. : "El trabajo de Alfred Tarski en la teoría de modelos". Journal of Symbolic Logic 51 (1986), n.º 4, 869–882
4. Robinson, A. : Análisis no estándar . North-Holland Publishing Co., Amsterdam 1966. página 48.
5. Marker 2002, págs. 40–43.
6. Gowers, Barrow-Green & Leader 2008, págs. 639–643.
7. Terence, Tao (7 de marzo de 2009). "Campos infinitos, campos finitos y el teorema de Ax-Grothendieck".
8. Goldblatt 1998, págs. 10-11.
9. Goldblatt 1998, pág. 11.
10. Véase Hodges (1993).

Referencias

• Boolos, George; Jeffrey, Richard; Burgess, John (2004).Computabilidad y lógica(cuarta ed.). Cambridge University Press.
• Chang, CC; Keisler, H. Jerome (1989). Model Theory (tercera edición). Elsevier. ISBN 0-7204-0692-7.
• Dawson, John W. junior (1993). "La compacidad de la lógica de primer orden: de Gödel a Lindström". Historia y filosofía de la lógica . 14 : 15–37. doi :10.1080/01445349308837208.
• Hodges, Wilfrid (1993). Teoría de modelos . Cambridge University Press. ISBN 0-521-30442-3.
• Goldblatt, Robert (1998). Lecciones sobre los hiperreales . Nueva York: Springer Verlag. ISBN. 0-387-98464-X.
• Gowers, Timothy; Barrow-Green, June; Leader, Imre (2008). The Princeton Companion to Mathematics . Princeton: Princeton University Press. págs. 635–646. ISBN 978-1-4008-3039-8.OCLC 659590835  .
• Marker, David (2002). Teoría de modelos: una introducción . Textos de posgrado en matemáticas . Vol. 217. Springer. ISBN 978-0-387-98760-6.OCLC 49326991  .
• Robinson, JA (1965). "Una lógica orientada a la máquina basada en el principio de resolución". Revista de la ACM . 12 (1). Asociación para Maquinaria Computacional (ACM): 23–41. doi : 10.1145/321250.321253 . ISSN  0004-5411. S2CID  14389185.
• Truss, John K. (1997). Fundamentos del análisis matemático . Oxford University Press. ISBN 0-19-853375-6.

Enlaces externos

• Teorema de compacidad, Enciclopedia de Filosofía de Internet .