Compacidad (lógica)

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.

La lógica proposicional como la lógica de primer orden satisfacen el teorema de compacidad. Es decir, si de un conjunto de proposiciones se sigue una consecuencia, entonces existe un subconjunto finito de proposiciones de las cuales se sigue la misma conclusión. Análogamente si cada conjunto finito de proposiciones de un conjunto admite un modelo, entonces el conjunto completo admite un modelo. Si bien la lógica de primer orden tiene compacidad en el sentido previamente explicado, otras lógicas "más potentes" como la lógica de segundo orden no tienen la propiedad de compacidad.

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$ , solo 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

Datos: Q1149458