FANDOM

78 Pages

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