The Compactness Theorem

The Compactness Theorem

The Compactness Theorem asserts the following: A theory $T$ has a model if and only if every finite sub-theory $S\subseteq T$ has a model. This is equivalent to a logic $\mathcal{L}$ having the strong compactness property.

Before doing the proof of the Compactness Theorem, there is an important result that is needed: Result: If $\varphi$ is an $\mathcal{L}$-formula and $T\models \varphi$, then there exists some finite $T_0\subseteq T$ such that $T_0\models \varphi$

Proof (Compactness Theorem): We will start w/ the contrapositive of the Compactness Theorem: if $T$ is unsatisfiable, then there is some $T_0\subseteq T$ that is unsatisfiable. Since $T$ is not satisfiable, then $T\models \varphi \wedge \neg \varphi$ for some sentence $\varphi$ of the (first-order) language $\mathcal{L}$. By the completeness theorem, $T⊢(\varphi \wedge \neg \varphi )$ $⟹$ There is some proof w/ assumptions (axioms) in $T$ and conclusion $\varphi \wedge \neg \varphi$. However, proofs (in first-order logic) are finite objects, and so there is some $T_0\subseteq T$ such that $T⊢\varphi \wedge \neg \varphi$ by the above result. Then by the soundness theorem, $T_0\models \varphi \wedge \neg \varphi$, and so $T_0$ is satisfiable as required.

Theorem (strengthened compactness): If $T$ is a finitely-satisfiable $\mathcal{L}$-theory (i.e., for every finite subset $T_0\subseteq T$, then there exists a structure $\mathcal{M}$ such that $\mathcal{M}\models T_0$) and $\kappa$ is an infinite cardinal w/ $\kappa \ge |\mathcal{L}|$, then there is a model $\mathcal{N}\models T$ such that $|N|\le \kappa$. Proof:

Other Notions of Compactness

$\kappa$-Compactness: A logic $\mathcal{L}$ is $\kappa$-compact if for a set of sentences $T\subseteq \mathcal{L}[\tau ]$, such that $|T|\le \kappa$, has a model if and only if every finite sub-theory $S\subseteq T$ (i.e., $|S|<{\aleph }_0$) has a model.

The Countable Compactness Property: A logic $\mathcal{L}$ is countably compact if for a countable theory $T\subseteq \mathcal{L}[\tau ]$ (i.e., $|T|\le {\aleph }_0$) has a model if and only if every finite sub-theory $S\subseteq T$ has a model. $\to$ i.e., the case where $\kappa ={\aleph }_0$

$(\kappa ,\lambda )$-compactness: A logic $\mathcal{L}$ is $(\kappa ,\lambda )$-compact if for all vocabularies $\tau$ and $\Phi \subseteq \mathcal{L}[\tau ]$ such that $|\Phi |<\kappa$, if each subset $\Psi \subseteq \Phi$ such that $|\Psi |<\lambda$ has a model, then $\Phi$ has a model

References

Model Theoretic Logics.pdf Model Theory D.Marker Soundness & Completeness