El Teorema de Compacidad del Cálculo Proposicional (II)

TEOREMA DE COMPACIDAD.- Si un conjunto de fbfs $\Sigma$ es finitamente satisfacible, entonces es satisfacible.

Demostración.- Por el LEMA, existe un conjunto de fbfs $\Delta$ tal que $\Sigma \subseteq \Delta$ y $\Delta$ es finitamente satisfacible y completo.
Entonces $\forall \phi \in W, \phi \notin \Delta \iff N\phi \in \Delta$ pues, por ser $\Delta$ completo, si $\phi \notin \Delta$, entonces $N\phi \in \Delta$; y, por ser $\Delta$ finitamente satisfacible, si $N\phi \in \Delta$, entonces $\phi \notin \Delta$, porque en otro caso sería $\left\{N\phi ,\phi \right\}\subseteq \Delta$ satisfacible, lo que es falso.

Sea la valoración de verdad $v:S\to \left\{0,1\right\}$, dada por $\forall p\in S, v\left(p\right)=1 syss p\in \Delta$.

Por inducción sobre fbfs demostraremos que

(*) $\overline{v}\left(\phi \right)=1 syss \phi \in \Delta$

lo cual es equivalente a $\overline{v}\left(\phi \right)=0 syss \phi \notin \Delta$.

Para los símbolos aserción del lenguaje, se cumple (*), por definición de $v$ y ser $\overline{v}\left(p\right)=v\left(p\right), \forall p\in S$.

Si $\alpha \in \Delta$ cumple (*), entonces

$\overline{v}\left(N\alpha \right)=1 syss \overline{v}\left(\alpha \right)=0 syss \alpha \notin \Delta syss N\alpha \in \Delta$

También se tiene que

$\overline{v}\left(C\alpha \beta \right)=0 syss \overline{v}\left(\alpha \right)=1 y \overline{v}\left(\beta \right)=0 syss \alpha \in \Delta y \beta \notin \Delta syss \alpha \in \Delta y N\beta \in \Delta syss C\alpha \beta \notin \Delta$

pues, en caso contrario, si $C\alpha \beta \in \Delta$, se tendría que $\left\{\alpha ,N\beta ,C\alpha \beta \right\}\subseteq \Delta$, y de $\left\{\alpha ,C\alpha \beta \right\}╞\beta$ se verificaría que $\beta \in \Delta$, lo que es imposible pues $N\beta \in \Delta$ y $\Delta$ es finitamente satisfacible, no siéndolo $\left\{\beta ,N\beta \right\}\subseteq \Delta$.
Se ha probado, pues, que la valoración $v$ satisface a $\Delta$, luego también a $\Sigma \subseteq \Delta$. Q.E.D.