FANDOM


The Compactness Theorem states that if T is a collection of first-order statements and every finite subset of T is consistent, then T is itself consistent. A set of statements is consistent if it has a model.

By abuse of terminology, the following related fact is also frequently referred to as "compactness." Let M be a $ \kappa $-saturated model, $ D \subset M^n $ be a definable set, and $ \Sigma $ be a collection of definable subsets of $ M^n $, with $ \Sigma $ of size less than $ \kappa $. If $ \Sigma $ covers D, then some finite subset of $ \Sigma $ covers D. This fact follows from the definition of $ \kappa $-saturation. Compactness is used to prove the existence of $ \kappa $-saturated models, however.

Common Corollaries and Uses of CompactnessEdit

The compactness theorem has a number of commonly-used corollaries. These corollaries are often used implicitly in proofs, and explained only as "compactness."

Lemma: Let M be a model, and $ \Sigma(x) $ be a consistent partial type over M. Then there is an elementary extension $ M' \succeq M $ in which $ \Sigma(x) $ is realized.

Proof: Apply the Compactness Theorem to the union of the elementary diagram of M and the statements $ \Sigma(c) $, where $ c $ is a new constant symbol. QED

Lemma: Let T be a theory. Let $ \phi(x) $ be a formula, and let $ \{\psi_i(x) : i \in I\} $ be a collection of formulas. Suppose that in every model M of T, we have

$ \phi(M) \subseteq \bigcup_{i \in I} \psi_i(M) $.

Then there is a finite subset $ I_0 \subset I $ such that in every model M of T,

$ \phi(M) \subseteq \bigcup_{i \in I_0} \psi_i(M) $.

Proof: Apply compactness to the union of T and the statements

$ \{ \phi(c) \} \cup \{ \neg \psi_i(c) : i \in I\} $

where $ c $ is a new constant symbol. By assumption, this collection of statements is inconsistent, so by compactness, some finite subset is inconsistent. This yields $ I_0 $. QED

Lemma: Let T be a theory, and $ \phi(x) $ be a formula. Suppose that in every model M of T, the set $ \phi(M) $ is finite. Then there is a number n such that $ |\phi(M)| < n $ for every model M.

Proof: Apply compactness to the union of T and the set of sentences $ \psi_n $ asserting for each n that at least n elements of the model satisfy $ \phi $. By assumption, this is inconsistent. Consequently, there is some n such that $ \psi_n $ is inconsistent with T. This means exactly that $ |\phi(M)| < n $ in every model of T. QED

The analogous statement in saturated models is the following: Lemma: Let M be a $ \aleph_1 $-saturated model. Suppose that $ \phi(x;y) $ is a formula such that for every $ b \in M $, the set $ \phi(M;b) $ is finite. Then there is a uniform bound n on the size of $ \phi(M;b) $.

Other important and prototypical applications of compactness include the following:


Interpretation as Compactness of Stone SpaceEdit

Let S denote the space of all complete theories (in some fixed first-order language). For each sentence $ \phi $, let

$ [\phi] = \{ T \in S | \phi \in T \} $

There is a natural topology on S in which the sets of the form $ [\phi] $ are the basic open (and basic closed) subsets. The compactness theorem says exactly that S is compact with this topology.


Proofs of CompactnessEdit

Compactness follows easily from some forms of Gödel's Completeness Theorem. Specifically, a theory $ T $ is inconsistent if and only if $ \exists x : x \ne x $ holds in all models of $ T $. By the Completeness Theorem, this holds if and only if $ \exists x : x \neq x $ can be proven from $ T $. But proofs are finitary, so any proof must take only finitely many steps, and must use only a finite subset of $ T $. In particular, if $ T $ proves $ \exists x : x \neq x $, then so does some finite subset $ T_0 \subset T $. So if $ T $ is inconsistent, so is a finite subset.

Compactness can alternatively be proven from Łoś's Theorem.

Proof: Let T be a collection of statements, with every finite subset of T being consistent. Let X be the set of all finite of T. For each finite subset $ S \subset T $, let

$ X_S = \{ T' \in X | S \subset T'\} $

Note that $ X_S \cap X_T = X_{S \cup T} $ and that $ X_S \ne \emptyset $ for any S. It follows that any finite intersection of $ X_S $'s is non-empty. Therefore we can find an ultrafilter $ \mathcal{U} $ on X such that $ X_S \in \mathcal{U} $ for every S. In other words, for each S, $ \mathcal{U} $ thinks that "most" elements of X contain S.

For each finite subset S of T, we can find a model $ M_S $ of S, by assumption. Consider the ultraproduct

$ M = \prod_{S \in X} M_S / \mathcal{U} $

We claim that M is the desired model of T. Let $ \phi $ be a formula in T. Then

$ M_S \models \phi $

for every $ S \ni \phi $, or equivalently, for every $ S \in X_{\{\phi\}} $. But

$ X_{\{\phi\}} \in \mathcal{U} $.

Consequently, the set of S such that $ M_S \models \phi $ is "large" with respect to the ultrafilter $ \mathcal{U} $. By Łoś's Theorem, $ \phi $ holds in the ultraproduct M. QED