The Compactness Theorem and Applications

Motivation: Working with Infinite Theories via Finite Ones

The compactness theorem is one of the most powerful tools in model theory. It allows us to “construct” models with desired properties by verifying an infinite set of requirements: we only need to ensure that every finite requirement is satisfiable. This is how nonstandard analysis, nonstandard models of arithmetic, and ultraproducts are built.

The Compactness Theorem

Theorem (follows from Gödel’s completeness theorem): A set of LFP statements $\Gamma$ is satisfiable ⟺ every finite subset $\Gamma_0 \subset \Gamma$ is satisfiable.

Two ways to prove it:

Via the completeness theorem: $\Gamma$ is unsatisfiable ⟺ $\Gamma \vdash \bot$ ⟺ $\vdash$ uses only finitely many axioms from $\Gamma$.
Via ultraproducts (more constructive).

Nonstandard Analysis (Robinson, 1960)

*The ℝ construction: Consider $\operatorname{Th}(\mathbb{R}) \cup {0 < \varepsilon, \varepsilon < 1, \varepsilon < 1/2, \varepsilon < 1/3, \ldots}$. Every finite subset is satisfiable (take $\varepsilon < 1/n$). By compactness → there exists *ℝ with an “infinitesimal” $\varepsilon > 0$, less than $1/n$ for all standard $n$.

*ℝ is an elementary extension of ℝ: *ℝ ⊨ $\operatorname{Th}(\mathbb{R})$. The transfer principle: an LFP statement is true in ℝ ⟺ true in *ℝ.

Differentiation: $f'(a) = \operatorname{st}\left(\frac{f(a+\varepsilon) - f(a)}{\varepsilon}\right)$, where $\operatorname{st}$ means “standard part” (nearest real number).

Example: $f(x) = x^2$, $\varepsilon$ is infinitesimal. $(a+\varepsilon)^2 = a^2 + 2a\varepsilon + \varepsilon^2$. Hence $((a+\varepsilon)^2 - a^2)/\varepsilon = 2a + \varepsilon$. $\operatorname{st}(2a + \varepsilon) = 2a$ → $f'(a) = 2a$ ✓.

Ultraproducts

Filter $U$ on set $I$: $U \subseteq P(I)$ with (F1) $I \in U$; (F2) $A,B \in U \rightarrow A\cap B \in U$; (F3) $A \in U, A\subseteq B \rightarrow B \in U$.

Ultrafilter: maximal filter. For every $A \subseteq I$: either $A \in U$, or $I \setminus A \in U$.

Ultraproduct $\prod_U M_i$: we identify $(a_i){i\in I} \sim_U (b_i){i\in I}$ if ${i : a_i = b_i} \in U$. Relations: $(a_i) \in R^{\prod_U M_i} \iff {i : a_i \in R_i} \in U$.

Łoś’s theorem: $\prod_U M_i \equiv M_i$ (for $I = {$all $i}$ and fixed ultrafilter $U$) — ultrapower $\prod_U M \equiv M$.

Numerical Example

Problem: Using compactness, prove: if every finite subgraph of $G$ is 3-colorable, then $G$ (possibly infinite) is also 3-colorable.

Step 1. Introduce a language with constants $v_i$ (vertices of $G$) and predicates $R^c(v_i)$ for each color $c \in {1,2,3}$: “vertex $v_i$ has color $c$”.

Step 2. Axioms $\Gamma$:

$\forall i$: $R^{c_1}(v_i) \vee R^{c_2}(v_i) \vee R^{c_3}(v_i)$ — “each vertex has a color.”
$\forall i$: $\neg(R^{c_1}(v_i) \wedge R^{c_2}(v_i)) \wedge \ldots$ — “no more than one color.”
For each edge $(v_i,v_j)$ and color $c$: $\neg(R^c(v_i) \wedge R^c(v_j))$ — “adjacent vertices have different colors.”

Step 3. Finite $\Gamma_0 \subset \Gamma$ mentions only a finite set of vertices → they form a finite subgraph $G_0$. By assumption $G_0$ is 3-colorable → $\Gamma_0$ is satisfiable.

Step 4. By compactness: $\Gamma$ is satisfiable → there is a model → coloring for all of $G$ ✓. ■

Real-Life Application

Nonstandard analysis is used in economics (infinitesimal methods in equilibrium models with continuous time), physics (quantum fields as nonstandard objects), and in didactics (Leibnizian analysis with $dx, dy$ as mathematically rigorous objects, not “mnemonic symbols”).

Additional Aspects

The compactness theorem is a spiritual dual to topological compactness and one of the strongest tools in model theory. Its consequences: impossibility to axiomatize finiteness (the set of propositions “there exist exactly $n$ elements” for all $n$ is not finitely realizable), existence of nonstandard models of arithmetic (Skolem 1934), Robinson’s nonstandard analysis with infinitesimals and infinitely large elements (which provides a rigorous justification for Leibniz’s $dx, dy$). The compactness theorem is also a tool in constructing models in combinatorics (Ramsey-type theorems extend from the countable to uncountable case) and in graph theory (compactness of infinite graphs via ultrafilters). In algorithmic applications, SMT solvers use compactness ideas when dealing with infinite domains.

Connection with Other Areas of Mathematics

Compactness of logical theories is closely intertwined with topological compactness. The classical correspondence: the space of Stone ultrafilters of a Boolean algebra of associated propositions turns out to be compact in the sense of Aleksandrov–Urysohn, and the compactness theorem is derived from Tychonoff’s theorem on the product of compact spaces. This line is developed in detail by Stone and in the Chikhan–Nogura monograph on ideals and ultrafilters.

In differential equations, compactness appears in nonstandard analysis as an alternative language for existence theorems. For example, solving the Cauchy problem for systems of ordinary differential equations can be described by hyperset approximations and the transfer principle can be applied instead of classical Gronwall estimates. This technique is discussed by Nelson in Internal Set Theory and by Lax in the context of equations of mathematical physics.

In algebra, the compactness theorem underlies results about spectral and primary decompositions. The model-theoretic proof of the Löwenheim–Skolem theorem gives the existence of nonstandard fields, pseudo-algebraically closed fields, and models of the theory of fields with operators, actively used by Cherovani, Mackenzie, and Poisson in distinguishable theories. In semigroup and group theory, compactness allows construction of universal and ultra-universal objects, as in the works of Sabo and Neumann.

In probability theory, model-theoretic methods via compactness are applied to constructing extensions of probability fields with saturated $\sigma$-algebras, and to the analysis of processes via ultralimits, as seen in the works of Loos and Hewitt–Savage. In numerical methods, compactness ideas appear in proofs of the existence of generalized solutions of partial differential equations: via ultraproducts of lattice schemes one can formalize the limit of Galerkin or finite volume methods, as discussed in the works of Diatata and Robbins.

Historical Background and Development of the Idea

The roots of the compactness theorem trace back to the completeness of first-order logic. In 1930, Kurt Gödel publishes in his monograph “Über formal unentscheidbare Sätze…” a proof of the completeness theorem, from which compactness immediately follows: inconsistency of an infinite theory is witnessed by a finite derivation. In the 1940s, Thoralf Skolem and Leon Henkin refine the technique: Henkin models become the standard tool for constructive proofs of both completeness and compactness. In the 1950s, Malewski, Tarski, and Chang develop the idea through ultraproducts. In the article by Chang and Keiseki (1951), published in Proceedings of the American Mathematical Society, the modern formulation of Łoś’s theorem and the system of constructing elementary extensions appears, providing an alternative proof of compactness without explicit reference to provability. In the second half of the 20th century, the compactness theorem becomes a central tool of model theory. Alfred Tarski, Asheronovich, Shelah use it to build nonstandard models of arithmetic and theories of fields.