¿Por qué se llama compacidad a la lógica?

Question

En lógica, se dice que una semántica es compacta si cada subconjunto finito de un conjunto de oraciones tiene un modelo, entonces también lo tiene todo el conjunto.

La mayoría de los textos de lógica o bien no explican la terminología, o bien aluden a la propiedad topológica de la compacidad. Veo una analogía como, dado un espacio topológico X y un subconjunto de él S, S es compacto si para cada cubierta abierta de S, hay una subcubierta finita de S. Pero, no parece lo suficientemente fuerte como para justificar la terminología.

¿Hay algo más en la elección de la terminología en la lógica que esta analogía?

Answer 1

El teorema de la compacidad es equivalente a la compacidad del Espacio de piedra de la Álgebra de Lindenbaum-Tarski del lenguaje de primer orden $L$ . (Este es también el espacio de $0$ -tipos sobre la teoría vacía).

Un punto en el espacio Stone $S_L$ es una teoría completa $T$ en la lengua $L$ . Es decir, $T$ es un conjunto de sentencias de $L$ que es cerrado bajo deducción lógica y contiene exactamente uno de $\sigma$ o $\lnot\sigma$ para cada frase $\sigma$ de la lengua. La topología sobre el conjunto de tipos tiene como base los conjuntos abiertos $U(\sigma) = \{T:\sigma\in T\}$ para cada frase $\sigma$ de $L$ . Obsérvese que todos ellos son conjuntos cerrados, ya que $U(\lnot\sigma)$ es complementario a $U(\sigma)$ .

Para ver cómo el Teorema de la compacidad implica la compacidad de $S_L$ Supongamos que los conjuntos abiertos básicos $U(\sigma_i)$ , $i\in I$ forman una cubierta de $S_L$ . Esto significa que toda teoría completa $T$ contiene al menos una de las frases $\sigma_i$ . Afirmo que esta cubierta tiene una subcubierta finita. Si no es así, entonces el conjunto $\{\lnot\sigma_i:i\in I\}$ es finitamente consistente. Por el Teorema de la Compactación, el conjunto es consistente y por tanto (por el Lemma de Zorn) está contenido en un conjunto máximamente consistente $T$ . Esta teoría $T$ es un punto del espacio de Stone que no está contenido en ningún $U(\sigma_i)$ lo que contradice nuestra hipótesis de que el $U(\sigma_i)$ , $i\in I$ , forman una cubierta del espacio.

Para ver cómo la compacidad de $S_L$ implica el Teorema de la compacidad, supongamos que $\{\sigma_i:i\in I\}$ es un conjunto incoherente de sentencias en $L$ . Entonces $U(\lnot\sigma_i),i\in I$ forma una cubierta de $S_L$ . Esta cubierta tiene una subcubierta finita, que corresponde a un subconjunto inconsistente finito de $\{\sigma_i:i\in I\}$ . Por lo tanto, todo conjunto inconsistente tiene un subconjunto inconsistente finito, lo cual es la contraposición del Teorema de la compacidad.

Answer 2

La analogía para el teorema de la compacidad del cálculo proposicional es la siguiente. Sea $p_i $ son variables proposicionales; juntas, toman valores en el espacio del producto $2^{\mathbb{N}}$ . Supongamos que tenemos una colección de declaraciones $S_t$ en estas variables booleanas tales que cada subconjunto finito es satisfacible. Entonces afirmo que podemos demostrar que todos ellos son simultáneamente satisfacibles utilizando un argumento de compacidad.

Dejemos que $F$ sea un conjunto finito. Entonces el conjunto de todas las asignaciones de verdad (es un subconjunto de $2^{\mathbb{N}}$ ) que satisfacen $S_t$ para $t \in F$ es un conjunto cerrado $V_F$ de asignaciones que satisfacen las sentencias en $F$ . La intersección de cualquier número finito de $V_F$ es no vacía, por lo que por la propiedad de intersección finita, la intersección de todas ellas es no vacía (ya que el espacio producto es compacto), por lo que cualquier verdad en esta intersección satisface todas las afirmaciones.

No sé cómo funciona esto en la lógica de predicados.

Answer 3

Lema: Un espacio topológico $X$ es compacto si y sólo si para cada colección $\mathcal{C}$ de conjuntos cerrados con la propiedad de intersección finita tiene intersección no vacía sobre la colección.

Propuesta: $\mathbb{M}(\mathcal{L})$ es compacta si y sólo si cada uno de los elementos finitos satisfechos $\mathcal{L}$ -La teoría es satisfacible.

Prueba: Considere el espacio $\mathbb{M}(\mathcal{L})=\{\Phi \; | \; \Phi \; \text{is a maximal} \; \mathcal{L} \text{-theory}\}$ . Para cada $\mathcal{L}$ -sentencia $\varphi$ dejar $[(\varphi)]=\{ \Phi \in \mathbb{M}(\mathcal{L}) \; | \; \varphi \in \Phi\}$ . Una subbase $\cal{B}$ para una topología en $\mathbb{M}(\mathcal{L})$ viene dada por los conjuntos $[(\varphi)]$ . Es decir, los subconjuntos abiertos de $\mathbb{M}(\mathcal{L})$ son la unión de las intersecciones finitas de los elementos de $\mathcal{B}$ . Para ver que $\mathcal{B}$ define una topología en nota que $[(\forall x(x\neq x))]=\emptyset$ y $[(\forall x(x=x))]=\mathbb{M}(\mathcal{L})$ . Además, las uniones arbitrarias ya están definidas para estar en la topología y las intersecciones finitas están en la topología ya que $[(\varphi)]\cap [(\theta)]=[(\varphi \wedge \theta)]$ que se define como abierto.

Asumir la compacidad lógica. Obsérvese que $\bigcap_{i\in I} [(\varphi_i)]=\emptyset$ si y sólo si no es satisfacible. Sea $\mathcal{C}$ sea una subcolección de la subbase de la topología de $\mathbb{M}(\mathcal{L})$ con la propiedad de intersección finita. Entonces todo subconjunto finito de $\mathcal{C}$ es satisfacible y por el teorema de la compacidad esto implica $\bigcap [(\varphi)]$ que abarca todos los elementos de $\cal{C}$ es satisfacible, por lo que $$ \bigcap_{[(\varphi)] \in \cal{B}} [(\varphi)]\neq \emptyset. $$ Así, $\mathbb{M}(\mathcal{L})$ es compacto.

Supongamos que $\mathbb{M}(\mathcal{L})$ es compacto. Sea $\Phi$ ser un $\mathcal{L}$ -en la que es finitamente satisfacible. Sea $\mathcal{C}_\Phi=\{[(\varphi)] \; | \; \varphi \in \Phi\}$ . Cada elemento de $\mathcal{C}_\Phi$ es cerrado y todo subconjunto finito de $\mathcal{C}_\Phi$ tiene una intersección no vacía ya que $\Phi$ es finitamente satisfacible. Dado que $\mathbb{M}(\mathcal{L})$ es compacto, $\bigcap_{\varphi \in \Phi} [(\varphi)]\neq\emptyset$ por lo que es satisfacible. $\square$

Answer 4

Un lema relacionado (y a veces verdadero) es "las pruebas son finitas". En la mayoría de los sistemas de lógica considerados, el enunciado y una prueba del mismo son cadenas finitas de símbolos. Se puede pensar en ellos como una representación "compacta". Qué bien entonces que ciertos sistemas permitan siempre encontrar una prueba si la hay. Si bien esto no ofrece una conexión estrecha con la topología, sugiere (y hay que trabajar esto por su cuenta para convencerse) que ciertas anormalidades infinitas (como una prueba infinita) no ocurrirán. Una afirmación topológica similar es que, para conjuntos compactos, una cadena inclusiva infinita de ciertos subconjuntos tendrá una intersección no vacía, afirmación que se ve fácilmente que es falsa para algunos conjuntos no compactos, como la colección { C_n | C_n = {x | x >= n y x es un número real } para n un número entero no negativo } .

Answer 5

Por lo que sé, el vínculo proviene de la teoría sintáctica. Se le da un conjunto de símbolos de la oración F = {f_i} y se le permite formar enunciados complejos con ellos. Puedes combinar las sentencias elementales con los operadores AND, OR, NOT y paréntesis, de la forma habitual.

Así se obtiene un conjunto X de frases compuestas, como

(f Y g) O (NO h)

o algo así.

Una versión sintáctica del teorema de la compacidad dice lo siguiente.

Supongamos que para cada subconjunto finito Y de X se pueden asignar valores de verdad a las f_i de forma que todas las sentencias de Y sean verdaderas. Entonces puedes hacer lo mismo para X.

Prueba

Consideremos el espacio topológico A obtenido tomando el producto de {0, 1} sobre el conjunto F. La topología sobre A es la topología del producto. Por el teorema de Tychonoff, A es compacto. Para todo enunciado compuesto s, el conjunto de valores de verdad que hacen que s sea verdadero es una intersección finita de cilindros, por lo que es un conjunto cerrado de A. La hipótesis dice que toda intersección finita de tales conjuntos cerrados, para s que varían en X, no es vacía. Por lo tanto, la intersección de todos esos conjuntos cerrados no es vacía, lo que significa que se pueden hacer verdaderas todas las afirmaciones de X.