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 \})$