Teorema de la compacidad - Compactness theorem

En lógica matemática , el teorema de la compacidad establece que un conjunto de oraciones de primer orden tiene un modelo si y solo si cada subconjunto finito 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 la compacidad para el cálculo proposicional es una consecuencia del teorema de Tychonoff (que dice que el producto de los espacios compactos es compacto) aplicado a los espacios de Stone compactos , de ahí el nombre del teorema. Asimismo, es análogo a la caracterización de la propiedad de intersección finita de 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 la 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 las lógicas que no son de primer orden, el teorema de la compacidad en sí no se cumple en ellas, excepto por un número muy limitado de ejemplos.

Historia

Kurt Gödel demostró el teorema de la compacidad contable en 1930. Anatoly Maltsev demostró el caso incontable en 1936.

Aplicaciones

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

El teorema de la compacidad implica el principio de Robinson : si una oración de primer orden se cumple en cada campo de característica cero, entonces existe una constante p tal que la oración se cumple para cada campo de característica mayor que p . Esto se puede ver de la siguiente manera: suponga que φ es una oración que se cumple en todos los campos de característica cero. Entonces su negación ¬φ, junto con los axiomas de campo y la secuencia infinita de oraciones 1 + 1 ≠ 0, 1 + 1 + 1 ≠ 0,…, no es satisfactoria (porque no hay un campo de característica 0 en el que ¬φ se cumple , 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 A de estas oraciones que no es satisfactorio. Podemos suponer que A contiene ¬φ, los axiomas de campo, y, para algunos k , las primeras k oraciones de la forma 1 + 1 + ... + 1 ≠ 0 (porque agregar más oraciones no cambia la insatisfacción). Deje que B contenga todas las oraciones de A excepto ¬φ. Entonces, cualquier campo con una característica mayor que k es un modelo de B , y ¬φ junto con B no es satisfactorio. Esto significa que φ debe cumplirse en cada modelo de B , lo que significa precisamente que φ se cumple en cada campo de característica mayor que k .

Una segunda aplicación del teorema de la compacidad muestra que cualquier teoría que tenga modelos finitos arbitrariamente grandes, o un solo modelo infinito, tiene modelos de cardinalidad arbitraria grande (este es el teorema ascendente de Löwenheim-Skolem ). Así, por ejemplo, existen modelos no estándar de aritmética de Peano con innumerables 'números naturales'. Para lograr esto, sea T la teoría inicial y sea κ cualquier número cardinal . Agregue al lenguaje de T un símbolo constante por cada elemento de κ. Luego agregue a T 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 satisfactorio por un modelo finito suficientemente grande de T , o por cualquier modelo infinito, toda la teoría extendida es satisfactoria. Pero cualquier modelo de la teoría extendida tiene cardinalidad al menos κ

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, sea Σ 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 a Σ el axioma ε> 0 y los axiomas ε <1 / n para todos los enteros positivos n . Claramente, los números reales estándar R 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 pueden hacer para satisfacer cualquier subconjunto finito de los axiomas sobre ε. Según el teorema de la compacidad, hay un modelo * R que satisface Σ y también contiene un elemento infinitesimal ε. Un argumento similar, axiomas contiguos ω> 0, ω> 1, etc., muestra que la existencia de números enteros infinitamente grandes no puede descartarse mediante ninguna axiomatización Σ de los reales.

Pruebas

Se puede probar el teorema de la compacidad utilizando el teorema de completitud de Gödel , que establece que un conjunto de oraciones es satisfactorio 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 sigue el teorema de la compacidad. De hecho, el teorema de la 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 .

Gödel probó originalmente el teorema de la compacidad precisamente de esta manera, pero más tarde se encontraron algunas pruebas "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 ultraproductos que dependen del axioma de elección de la siguiente manera:

Demostración: Fije un lenguaje de primer orden L, y sea Σ una colección de oraciones L de manera que cada subcolección finita de oraciones L, i  ⊆ has tenga un modelo . También sea ​​el producto directo de las estructuras y yo sea ​​la colección de subconjuntos finitos de Σ. Para cada i en , dejo A _i  : = { j ∈ I  : j ⊇ i }. La familia de todos estos conjuntos A _i genera un filtro adecuado , por lo que hay un ultrafiltro U que contiene todos los conjuntos de la forma A _i . ${\ Displaystyle {\ mathcal {M}} _ {i}}$${\ Displaystyle \ prod _ {i \ subseteq \ Sigma} {\ mathcal {M}} _ {i}}$

Ahora, para cualquier fórmula φ en Σ tenemos:

• el conjunto A _{φ} está en U
• siempre que j  ∈ A _{φ} , entonces φ ∈  j , por lo tanto φ se mantiene en ${\ Displaystyle {\ mathcal {M}} _ {j}}$
• el conjunto de todo j con la propiedad que φ tiene en es un superconjunto de A _{φ} , por lo tanto también en U${\ Displaystyle {\ mathcal {M}} _ {j}}$

Usando el teorema de Łoś vemos que φ se cumple en el ultraproducto . Entonces este ultraproducto satisface todas las fórmulas en Σ. ${\ Displaystyle \ prod _ {i \ subseteq \ Sigma} {\ mathcal {M}} _ {i} / U}$

Ver también

• Teorema de compacidad barwise
• Teorema de herbrand
• Lista de temas de álgebra de Boole  - artículo de la lista de Wikimedia
• Teorema de Löwenheim-Skolem  - Teorema matemático

Notas

Referencias

• Boolos, George; Jeffrey, Richard; Burgess, John (2004). Computabilidad y lógica (cuarta ed.). Prensa de la Universidad de Cambridge.
• Chang, CC; Keisler, H. Jerome (1989). Model Theory (tercera ed.). 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 . Prensa de la Universidad de Cambridge. ISBN   0-521-30442-3 .
• Marker, David (2002). Teoría de modelos: una introducción . Textos de Posgrado en Matemáticas 217. Springer. ISBN   0-387-98760-6 .
• Truss, John K. (1997). Fundamentos del análisis matemático . Prensa de la Universidad de Oxford. ISBN   0-19-853375-6 .