Compactness Theorem

The compactness theorem is one of the most fundamental results in mathematical logic, asserting that a theory has a model if and only if every finite subset does. It has far-reaching consequences in algebra, combinatorics, and analysis.

Statement

Theorem4.1Compactness Theorem

A set $T$ of first-order sentences has a model if and only if every finite subset of $T$ has a model. Equivalently, if $T \models \sigma$ , then there exists a finite $T_0 \subseteq T$ with $T_0 \models \sigma$ .

Proof via Ultraproducts

Proof

The forward direction is trivial. For the converse, assume every finite subset of $T$ has a model. Let $\mathcal{F} = \{T_0 \subseteq T : T_0 \text{ is finite}\}$ . For each $T_0 \in \mathcal{F}$ , let $\mathcal{M}_{T_0}$ be a model of $T_0$ . For each $T_0 \in \mathcal{F}$ , define $U_{T_0} = \{T_1 \in \mathcal{F} : T_0 \subseteq T_1\}$ .

The collection $\{U_{T_0} : T_0 \in \mathcal{F}\}$ has the finite intersection property: $U_{T_0} \cap U_{T_1} \supseteq U_{T_0 \cup T_1}$ . By Zorn's lemma, extend this collection to an ultrafilter $\mathcal{U}$ on $\mathcal{F}$ .

Consider the ultraproduct $\mathcal{M} = \prod_{T_0 \in \mathcal{F}} \mathcal{M}_{T_0} / \mathcal{U}$ . For any sentence $\sigma \in T$ , the set $\{T_0 : \mathcal{M}_{T_0} \models \sigma\} \supseteq U_{\{\sigma\}} \in \mathcal{U}$ , so by Los's theorem, $\mathcal{M} \models \sigma$ . Thus $\mathcal{M} \models T$ . $\square$

■

Applications

ExampleGraph Coloring

If every finite subgraph of a graph $G$ is $k$ -colorable, then $G$ itself is $k$ -colorable. Proof: For each vertex $v$ , introduce a constant $c_v$ and colors $\{1, \ldots, k\}$ . The theory states each $c_v$ takes a color value, and for each edge $\{u, v\}$ , $c_u \neq c_v$ . Every finite subset involves finitely many vertices, hence a finite subgraph, which is $k$ -colorable. By compactness, the full theory has a model.

RemarkNon-Standard Models

Compactness implies the existence of non-standard models. The theory $\mathrm{Th}(\mathbb{N}) \cup \{c > \underline{n} : n \in \mathbb{N}\}$ (with new constant $c$ and $\underline{n}$ for each natural number) is finitely satisfiable, hence has a model: a nonstandard model of arithmetic with an "infinite" element $c$ .