Compactness

Theorem 1. (Compactness Theorem)

1. If \(\Gamma \models \varphi\), then for some finite \(\Gamma_0 \subseteq \Gamma\) we have \(\Gamma_0 \models \varphi\).
2. If every finite subset \(\Gamma_0\) of \(\Gamma\) is satisfiable, then \(\Gamma\) is satisfiable.

Proof.

1. \[\begin{align*} \Gamma \models \varphi &\implies \Gamma \vdash \varphi \\ &\implies \Gamma_0 \vdash \varphi \text{ for some finite } \Gamma_0 \subseteq \Gamma \text{, deductions being finite} \\ &\implies \Gamma_0 \models \varphi \end{align*}\]
2. If every finite subset \(\Gamma_0\) of \(\Gamma\) is satisfiable, then by soundness \(\Gamma_0\) is consistent. Thus \(\Gamma\) is consistent (since deductions are finite). By completeness, \(\Gamma\) is also satisfiable.

■