Teorema de compacidad

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]

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[editar]