Teorema de compacidad

Teorema

En lógica matemática , el teorema de la compacidad establece que un conjunto de oraciones de primer orden tiene un modelo si y sólo si cada subconjunto finito del mismo 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 Tychonoff (que dice que el producto de espacios compactos es compacto) aplicado a espacios compactos de Stone , ^[1] de ahí el nombre del teorema. Asimismo, es análogo a la propiedad de intersección finita caracterización de 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 descendente de Löwenheim-Skolem , que se utiliza en el teorema de Lindström para caracterizar la lógica de primer orden. Aunque existen algunas generalizaciones del teorema de la compacidad a lógicas que no son de primer orden, el teorema de la 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 contable en 1930. Anatoly Maltsev demostró el caso incontable en 1936. ^{[3] [4]}

Aplicaciones

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

principio de robinson

El teorema de la compacidad implica el siguiente resultado, declarado por Abraham Robinson en su disertación de 1949 .

Principio de Robinson: ^{[5] [6]} Si una oración de primer orden se cumple en cada campo de característica cero, entonces existe una constante tal que la oración se cumple para cada campo de característica mayor que Esto se puede ver de la siguiente manera: supongamos que es un oración que se cumple en cada campo de característica cero. Luego su negación junto con los axiomas de campo y la secuencia infinita de oraciones. ${\displaystyle p}$ ${\displaystyle p.}$ ${\displaystyle \varphi }$ ${\displaystyle \lnot \varphi ,}$

$${\displaystyle 1+1\neq 0,\;\;1+1+1\neq 0,\;\ldots }$$

satisfactoria ${\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 principio de transferencia , amplía este resultado. Una oración de primer orden en el lenguaje de los anillos es verdadera en algún (o equivalentemente, en cada ) campo algebraicamente cerrado de característica 0 (como los números complejos, por ejemplo) si y sólo si existen infinitos números primos para los cuales es verdadera en algún campo algebraicamente cerrado de característica en cuyo caso es cierto en todos los campos algebraicamente cerrados de característica distinta de 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 cierta para cualquier polinomio inyectivo donde haya un campo finito o la clausura algebraica de dicho campo. ^[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 la 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 Upward Löwenheim-Skolem ). Así, por ejemplo, existen 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 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 mediante un modelo finito suficientemente grande o mediante cualquier modelo infinito, toda la teoría extendida es satisfacible. Pero cualquier modelo de la teoría extendida tiene al menos cardinalidad . ${\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 la 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, hagamos una axiomatización de primer orden de la teoría de los números reales. Considere la teoría obtenida agregando un nuevo símbolo constante al lenguaje y adjuntando al axioma y a los axiomas para todos los números 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 se puede hacer que satisfaga cualquier subconjunto finito de los axiomas sobre Por el teorema de la compacidad, existe 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 si y sólo si es verdadera para ${\displaystyle {}^{*}\mathbb {R} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle {}^{*}\mathbb {R} .}$

Pruebas

Se puede probar el teorema de compacidad utilizando el teorema de completitud de Gödel , que establece que un conjunto de oraciones es satisfacible si y sólo si no se puede demostrar ninguna contradicción a partir de él. Dado que las demostraciones son siempre finitas y, por lo tanto, involucran sólo un número finito de oraciones dadas, se sigue 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 booleano , una forma débil del axioma de elección . ^[10]

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

Prueba : arregle un lenguaje de primer orden y sea una colección de oraciones tal que cada subcolección finita de oraciones tenga un modelo . También sea el producto directo de las estructuras y sea la colección de subconjuntos finitos de Para cada let La familia de todos estos conjuntos genera un filtro adecuado , 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 para cualquier oración en ${\displaystyle \varphi }$ ${\displaystyle \Sigma :}$

• el conjunto está en ${\displaystyle A_{\{\varphi \}}}$ ${\displaystyle U}$
• siempre que entonces se mantenga 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 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. Entonces este ultraproducto satisface todas las fórmulas en ${\displaystyle \varphi }$ ${\textstyle \prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}/U.}$ ${\displaystyle \Sigma .}$

Ver también

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

Notas

1. Ver Armadura (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 definibilidad. 645--716, ver Teoremas 4.5.9, 4.6.12 y Proposición 4.6.9. Para lógicas compactas para una noción ampliada de modelo, consulte Ziegler, M. Capítulo XV: Teoría del modelo topológico. 557--577. Para lógicas sin la propiedad de relativización es posible tener simultáneamente compacidad e interpolación, mientras que el problema aún está abierto para lógicas con relativización. Véase Xavier Caicedo, Una solución simple al cuarto problema de Friedman, 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 teoría de modelos". Revista de lógica simbólica 51 (1986), no. 4, 869–882
4. Robinson, A .: Análisis no estándar . North-Holland Publishing Co., Ámsterdam 1966. página 48.
5. Marker 2002, págs.
6. Gowers, Barrow-Green y 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, pag. 11.
10. Véase Hodges (1993).

Referencias

• Boolos, George; Jeffrey, Ricardo; Burgess, Juan (2004).Computabilidad y Lógica(cuarta ed.). Prensa de la Universidad de Cambridge.
• Chang, CC; Keisler, H. Jerome (1989). Teoría de modelos (tercera ed.). Elsevier. ISBN 0-7204-0692-7.
• Dawson, John W. hijo (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 . Prensa de la Universidad de Cambridge. ISBN 0-521-30442-3.
• Goldblatt, Robert (1998). Conferencias sobre los hiperreales . Nueva York: Springer Verlag. ISBN 0-387-98464-X.
• Gowers, Timoteo; Barrow-Green, junio; Líder, Imre (2008). El compañero de matemáticas de Princeton . Princeton: Prensa de la Universidad de Princeton. págs. 635–646. ISBN 978-1-4008-3039-8. OCLC  659590835.
• Marcador, David (2002). Teoría de modelos: una introducción . Textos de Posgrado en Matemáticas . vol. 217. Saltador. ISBN 978-0-387-98760-6. OCLC  49326991.
• Robinson, JA (1965). "Una lógica orientada a máquinas basada en el principio de resolución". Revista de la ACM . Asociación de Maquinaria de Computación (ACM). 12 (1): 23–41. doi : 10.1145/321250.321253 . ISSN  0004-5411. S2CID  14389185.
• Armadura, John K. (1997). Fundamentos del análisis matemático . Prensa de la Universidad de Oxford. ISBN 0-19-853375-6.

enlaces externos

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