Teorema de Compacidad

Si Γ es un conjunto de fórmulas tal que todo subconjunto finito de Γ es satisfactible. Entonces Γ es satisfactible

El teorema es equivalente a la siguiente proposición:

• Sea Γ un conjunto de fórmulas y α una fórmula. Si α es consecuencia lógica de Γ entonces existe un subconjunto finito Γ´ $\subseteq$ Γ tal que α es consecuencia lógica de Γ´

Prueba de la proposición

Supongamos primero que vale el teorema de compacidad. Sea $\Gamma \subseteq Form$ y $\alpha \in c(\Gamma )$. Entonces $\Gamma \cup \{\neg \alpha \}$ es insatisfactible. Por el teorema existe ${\hat {\Gamma }}\subseteq \Gamma \cup \{\neg \alpha \}$ finito e insatisfactible.

• Si ${\hat {\Gamma }}\subseteq \Gamma$ entonces ${\hat {\Gamma }}\cup \{\neg \alpha \}$ es insatisfactible y luego $\alpha \in c({\hat {\Gamma }})$.

• Si no, ${\hat {\Gamma }}$ contiene a $\neg \alpha$. ${\hat {\Gamma }}\cup \{\neg \alpha \}={\hat {\Gamma }}$. También se llega a $\alpha \in c({\hat {\Gamma }})$: ${\hat {\Gamma }}\setminus \{\neg \alpha \}\subseteq \Gamma$ y ${\hat {\Gamma }}\setminus \{\neg \alpha \}\cup \{\neg \alpha \}={\hat {\Gamma }}$ es insatisfactible.

Por lo tanto, $\alpha \in c({\hat {\Gamma }}\setminus \{\neg \alpha \})$