Teorema de compacidad

En lógica matemática, el teorema de compacidad establece que un conjunto (posiblemente infinito) de fórmulas bien formadas de la lógica de primer orden tiene un modelo si todos sus subconjuntos finitos tienen un modelo. Es decir, para todo conjunto de fórmulas \Gamma de un lenguaje L, si todo subconjunto finito de \Gamma es satisfacible, entonces \Gamma es satisfacible.

Enunciado del teorema

Si \Gamma es un conjunto de enunciados finitamente satisfacible, entonces \Gamma tiene un modelo de cardinal menor o igual que |\Gamma|+\aleph_0.

Una formulación alternativa es: los distintos lenguajes lógicos permiten relaciones de consecuencia lógica entre conjuntos infinitos de oraciones. Una relación de consecuencia lógica es compacta justo cuando \phi es una consecuencia lógica de un conjunto de enunciados \Gamma, sólo si \phi es una consecuencia lógica de un subconjunto finito de \Gamma:

Si \Gamma\vDash\phi entonces hay un subconjunto finito \Gamma_{0}\subseteq\Gamma tal que \Gamma_{0}\vDash\phi

La relación de consecuencia lógica para lenguajes de primer orden es compacta.

El teorema de compacidad para el cálculo proposicional es un resultado del teorema de Tychonoff (el cual dice que el producto de espacios compactos es compacto) aplicado a espacios de Stone compactos; de ahí el nombre del teorema. Juega un papel importante en la demostración del Teorema de Löwenheim-Skolem ascendente.

Hay una generalización de compacidad para lenguajes de orden más alto que los lenguajes de primer orden.

Véase también

This article is issued from Wikipedia - version of the Wednesday, July 24, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.