Saltar al contenido
Topos Uranos
Español

El teorema de compacidad

Resumen

Una deducción es una sucesión finita y solo usa un número finito de premisas; la satisfacción de un conjunto infinito de fórmulas, en cambio, exige una sola valoración que dé el valor 11 a infinitas fórmulas a la vez, y nada en su definición dice que baste examinar partes finitas. El teorema de compacidad afirma que basta: un conjunto de fórmulas es satisfacible si y solo si lo es cada uno de sus subconjuntos finitos. Esta clase lo demuestra por un argumento semántico directo, sin pasar por la deducción: se fijan uno a uno los valores de las variables v1,v2,…v_1, v_2, \ldots, conservando en cada paso el invariante de que todo subconjunto finito del conjunto sigue siendo satisfacible por una valoración que respeta lo ya fijado; si ninguna de las dos elecciones posibles lo conservara, la unión de los dos testigos finitos de ese fracaso contradiría el invariante anterior, y al final cada fórmula queda satisfecha por el lema de coincidencia, porque tiene un número finito de variables. Como las variables están numeradas, la construcción no necesita el axioma de elección. De la compacidad se siguen sus formas equivalentes (un conjunto es insatisfacible si y solo si lo es alguna parte finita; una fórmula es consecuencia de un conjunto si y solo si lo es de alguna parte finita) y, con la completitud para premisas finitas de la clase anterior, la completitud fuerte: Γ⊨φ\Gamma \models \varphi implica Γ⊢φ\Gamma \vdash \varphi para todo conjunto Γ\Gamma, de donde la deducción y la consecuencia semántica coinciden siempre. La clase termina con aplicaciones combinatorias: la coloración de grafos infinitos a partir de las de sus partes finitas, las cotas finitas que se esconden en los enunciados infinitos y los límites de lo que un conjunto de fórmulas puede expresar.

Objetivos de aprendizaje

  1. Definir los conjuntos finitamente satisfacibles y demostrar el teorema de compacidad por fijación sucesiva de los valores de las variables, explicando el papel del invariante, del argumento de los dos testigos y del lema de coincidencia, y por qué la construcción no necesita el axioma de elección.
  2. Enunciar, demostrar y aplicar las formas equivalentes de la compacidad, la de la insatisfacibilidad y la de la consecuencia, y pasar de cada una a las otras.
  3. Deducir la completitud fuerte de la compacidad, de la completitud para conjuntos finitos de premisas y de la monotonía, y obtener de ella la coincidencia de la deducción con la consecuencia semántica y de la consistencia con la satisfacibilidad.
  4. Codificar en conjuntos de fórmulas problemas combinatorios sobre conjuntos infinitos (coloraciones, órdenes, emparejamientos) y resolverlos con la compacidad, distinguiendo lo que el teorema asegura de lo que no asegura.

Lo que se usa de las clases anteriores

Esta clase trabaja casi enteramente en la semántica, y usa de ella lo siguiente. Una valoración es una función v ⁣:V→{0,1}v\colon V \to \{0, 1\} sobre el conjunto VV de las variables v1,v2,v3,…v_1, v_2, v_3, \ldots, que se extiende de un único modo a todas las fórmulas; una valoración satisface un conjunto Γ\Gamma de fórmulas, v⊨Γv \models \Gamma, si da el valor 11 a cada una de ellas, y Γ\Gamma es satisfacible si alguna valoración lo satisface e insatisfacible en caso contrario. Todo ello está en la clase sobre la semántica de la lógica proposicional, junto con el instrumento central de esta clase, el lema de coincidencia: si dos valoraciones coinciden en las variables de φ\varphi, que son un conjunto finito V(φ)V(\varphi), dan a φ\varphi el mismo valor.

De la clase sobre consecuencia y equivalencia semántica se usan la definición de Γ⊨φ\Gamma \models \varphi (toda valoración que satisface Γ\Gamma satisface φ\varphi), sus propiedades estructurales, en particular la monotonía (si Γ⊆Δ\Gamma \subseteq \Delta y Γ⊨φ\Gamma \models \varphi, entonces Δ⊨φ\Delta \models \varphi) y la quinta (un conjunto insatisfacible tiene por consecuencia toda fórmula), y el teorema de consecuencia e insatisfacibilidad: Γ⊨φ\Gamma \models \varphi si y solo si Γ∪{¬φ}\Gamma \cup \{\neg\varphi\} es insatisfacible. De la clase sobre las leyes generalizadas de De Morgan y de distribución se usa el lema del valor: ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i vale 11 si y solo si todos sus términos valen 11, y ⋁i=1nφi\bigvee_{i=1}^{n} \varphi_i, si y solo si alguno vale 11. Por último, ⊤:=(v1→v1)\top := (v_1 \rightarrow v_1) es una tautología y ⊥:=¬⊤\bot := \neg\top, una contradicción.

Del lado de la deducción, la clase sobre los sistemas deductivos formales demostró la monotonía (Mon: si Γ⊆Δ\Gamma \subseteq \Delta y Γ⊢φ\Gamma \vdash \varphi, entonces Δ⊢φ\Delta \vdash \varphi) y el carácter finito (Fin: si Γ⊢φ\Gamma \vdash \varphi, algún subconjunto finito Γ0\Gamma_0 de Γ\Gamma cumple Γ0⊢φ\Gamma_0 \vdash \varphi), y la clase sobre las cuatro técnicas de deducción comprobó que ambas valen en el sistema del curso (los esquemas A1, A2 y A3, el modus ponens y el reemplazo de la doble negación, RDN), al que se refiere en adelante el signo ⊢\vdash. Finalmente, la clase sobre corrección y completitud demostró el teorema de corrección (Γ⊢φ\Gamma \vdash \varphi implica Γ⊨φ\Gamma \models \varphi, para todo Γ\Gamma) y la completitud para conjuntos finitos de premisas: si {γ1,…,γk}⊨φ\{\gamma_1, \ldots, \gamma_k\} \models \varphi, entonces {γ1,…,γk}⊢φ\{\gamma_1, \ldots, \gamma_k\} \vdash \varphi.