Teorema de compacidad

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 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, de ahí el nombre del teorema. Asimismo, es análoga a la caracterización de la propiedad de la intersección finita 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 hay algunas generalizaciones del teorema de compacidad a lógicas que no son de primer orden, el teorema de compacidad en sí mismo 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.

Principio de Robinson

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

Principio de Robinson: Si una frase de primer orden se mantiene en cada campo de la característica cero, entonces existe una constante p{displaystyle p} tal que la frase sostiene por cada campo de características más grandes que p.{displaystyle p.} Esto se puede ver como sigue: φ φ {displaystyle varphi } es una frase que sostiene en cada campo de la característica cero. Entonces su negación ¬ ¬ φ φ ,{displaystyle lnot varphi} junto con los axiomas de campo y la secuencia infinita de oraciones

1+1ل ل 0,1+1+1ل ل 0,...... {displaystyle 1+1neq 0,;;1+1neq 0,;ldots }

¬ ¬ φ φ {displaystyle lnot varphi }

A{displaystyle A}

A{displaystyle A}

¬ ¬ φ φ {displaystyle lnot varphi }

A{displaystyle A}

A{displaystyle A}

k,{displaystyle k,}

k{displaystyle k}

1+1+⋯ ⋯ +1ل ل 0.{displaystyle 1+1+cdots +1neq 0.}

B{displaystyle B}

A{displaystyle A}

¬ ¬ φ φ .{displaystyle lnot varphi.}

k{displaystyle k}

B,{displaystyle B,}

¬ ¬ φ φ {displaystyle lnot varphi }

B{displaystyle B}

φ φ {displaystyle varphi }

B,{displaystyle B,}

φ φ {displaystyle varphi }

k.{displaystyle k.}

El principio Lefschetz, uno de los primeros ejemplos de principio de transferencia, extiende este resultado. Una primera oración φ φ {displaystyle varphi } en el idioma de los anillos es verdad en algunos (o equivalentemente, en cada uno) campo algebraicamente cerrado de característica 0 (como los números complejos por ejemplo) si y sólo si existen infinitamente muchos primos p{displaystyle p} para la cual φ φ {displaystyle varphi } es verdad algunos campo algebraicamente cerrado de característica p,{displaystyle p,} en qué caso φ φ {displaystyle varphi } es verdad Todos campos cerrados algebraicamente de la característica no-0 suficientemente grande p.{displaystyle p.} Una consecuencia es el siguiente caso especial del teorema Ax-Grothendieck: todos los polinomios complejos inyectables Cn→ → Cn{displaystyle mathbb {C} }to mathbb {C} son subjetivos (de hecho, incluso se puede demostrar que su inverso también será un polinomio). De hecho, la conclusión de la subjetividad sigue siendo verdadera para cualquier polinomio inyectable Fn→ → Fn{displaystyle F^{n}to F^{n} Donde F{displaystyle F} es un campo finito o el cierre algebraico de tal campo.

Teorema de Löwenheim-Skolem hacia arriba

Una segunda aplicación del teorema de compactidad muestra que cualquier teoría que tenga modelos finitos arbitrariamente grandes, o un solo modelo infinito, tiene modelos de cardenalidad grande arbitraria (este es el teorema Upward Löwenheim–Skolem). Por ejemplo, hay modelos no estándar de Peano aritmético con incontables "números naturales". Para lograr esto, vamos T{displaystyle T} ser la teoría inicial y dejar κ κ {displaystyle kappa } ser cualquier número cardenal. Añadir al idioma de T{displaystyle T} un símbolo constante para cada elemento κ κ .{displaystyle kappa.} A continuación, añadir T{displaystyle T} a collection of sentences that say that the objects denoted by any two distinct constant symbols from the new collection are distinct (this is a collection of κ κ 2{displaystyle kappa ^{2} oraciones). Desde todos finito subconjunto de esta nueva teoría es satisfecha por un modelo finito suficientemente grande T,{displaystyle T,} o por cualquier modelo infinito, toda la teoría extendida es satisfecha. Pero cualquier modelo de la teoría extendida tiene al menos la cardinalidad κ κ {displaystyle kappa }.

Análisis no estándar

Una tercera aplicación del teorema de compactidad 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, vamos .. {displaystyle Sigma } ser una axiomatización de primer orden de la teoría de los números reales. Considere la teoría obtenida añadiendo un nuevo símbolo constante ε ε {displaystyle varepsilon } al idioma y acompañamiento .. {displaystyle Sigma } el axioma 0}" xmlns="http://www.w3.org/1998/Math/MathML">ε ε ■0{displaystyle varepsilon }0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e04ec3670b50384a3ce48aca42e7cc5131a06b12" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;"/> y el axioma <math alttext="{displaystyle varepsilon ε ε .1n{displaystyle varepsilon }{tfrac {1}{n}}<img alt="{displaystyle varepsilon para todos los enteros positivos n.{displaystyle n.} Claramente, los números reales estándar R{displaystyle mathbb {R} son un modelo para cada subconjunto finito de estos axiomas, porque los números reales satisfacen todo en .. {displaystyle Sigma } y, por elección adecuada de ε ε ,{displaystyle varepsilon} se puede hacer para satisfacer cualquier subconjunto finito de los axiomas alrededor ε ε .{displaystyle varepsilon.} Por el teorema de compactidad, hay un modelo Alternativa Alternativa R{displaystyle {} {fnMithbb} {R} que satisfice .. {displaystyle Sigma } y también contiene un elemento infinitesimal ε ε .{displaystyle varepsilon.}

Un argumento similar, esta vez acompañando los axiomas 0,;omega >1,ldots}" xmlns="http://www.w3.org/1998/Math/MathML">⋅ ⋅ ■0,⋅ ⋅ ■1,...... ,{displaystyle omega ¢0,;omega ¢1,ldots}0,;omega >1,ldots}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e03a88ad1a8d1ec1ef5e50e1b37e506c2ab8991" style="vertical-align: -0.671ex; width:17.884ex; height:2.509ex;"/> etc., muestra que la existencia de números con magnitudes infinitamente grandes no puede ser descartada por cualquier axiomatización .. {displaystyle Sigma } de los reales.

Se puede demostrar que los números hiperreal Alternativa Alternativa R{displaystyle {} {fnMithbb} {R} cumplir el principio de transferencia: una oración de primer orden es verdadera R{displaystyle mathbb {R} si y sólo si es verdad Alternativa Alternativa R.{fnMicrosoft Sans Serif}

Pruebas

Se puede probar el teorema de 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 probar ninguna contradicción a partir de él. Dado que las pruebas son siempre finitas y, por lo tanto, involucran solo un número finito de las 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.

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

Prueba: Arreglar un idioma de primer orden L,{displaystyle L. y dejar .. {displaystyle Sigma } ser una colección de L-sentencias tales que cada subcollección finita de L{displaystyle L.-sentencias, i⊆ ⊆ .. {displaystyle isubseteq Sigma} tiene un modelo Mi.{fnMicrosoft Sans Serif} También deja ∏ ∏ i⊆ ⊆ .. Mi{textstyle prod _{isubseteq "Sigma" ser el producto directo de las estructuras y I{displaystyle Yo... ser la colección de subconjuntos finitos de .. .{displaystyle Sigma.} Para cada uno i▪ ▪ I,{displaystyle iin I,} Deja Ai={}j▪ ▪ I:j⊇ ⊇ i}.{displaystyle A_{i}={jin I:jsupseteq i} La familia de todos estos conjuntos Ai{displaystyle A_{i} genera un filtro adecuado, así que hay un ultrafiltro U{displaystyle U} que contiene todos los conjuntos de la forma Ai.{displaystyle A_{i}.

Ahora para cualquier fórmula φ φ {displaystyle varphi } dentro .. :{displaystyle Sigma:}

• el conjunto A{}φ φ }{displaystyle A_{{\varphia {}}} está dentro U{displaystyle U}
• siempre j▪ ▪ A{}φ φ },{displaystyle jin A_{varphi}}} entonces φ φ ▪ ▪ j,{displaystyle varphi in j,} de aquí φ φ {displaystyle varphi } en Mj{fnMicrosoft Sans Serif}
• el conjunto de todos j{displaystyle j} con la propiedad que φ φ {displaystyle varphi } en Mj{fnMicrosoft Sans Serif} es un superset de A{}φ φ },{displaystyle A_{{varphi}}} así también U{displaystyle U}

El teorema de Lobo ahora implica que φ φ {displaystyle varphi } sostiene en el ultraproducto ∏ ∏ i⊆ ⊆ .. Mi/U.{textstyle prod _{isubseteq Sigma {M}_{i}/U.} Así que este ultraproducto satisface todas las fórmulas en .. .{displaystyle Sigma.}