5.1 Compactness Theorem

The compactness theorem is one of the central structural results of first order logic, and it expresses a precise relationship between finite and infinite behavior of theories, showing that global satisfiability is completely controlled by finite fragments.

Definition 5.1 (Structures and Satisfaction)

Let $\mathcal{L}$ be a first order language, and let $\mathcal{M}$ be an $\mathcal{L}$ -structure.

For a sentence $A$ in $\mathcal{L}$ , we write:

\mathcal{M} \models A

to mean that $A$ is true in $\mathcal{M}$ .

If $\Gamma$ is a set of sentences, we write:

\mathcal{M} \models \Gamma

to mean that:

\mathcal{M} \models A

for every $A \in \Gamma$ .

Thus $\mathcal{M}$ is a model of $\Gamma$ exactly when it satisfies every sentence in $\Gamma$ .

Definition 5.2 (Satisfiability and Consistency)

A set of sentences $\Gamma$ is satisfiable if there exists an $\mathcal{L}$ -structure $\mathcal{M}$ such that:

\mathcal{M} \models \Gamma

A set of sentences $\Gamma$ is unsatisfiable if no such structure exists.

A set of sentences $\Gamma$ is syntactically consistent if:

\Gamma \nvdash \bot

In first order logic, the completeness theorem connects these two notions by saying that a set of sentences is satisfiable exactly when it is syntactically consistent.

Definition 5.3 (Finite Satisfiability)

A set of sentences $\Gamma$ is finitely satisfiable if every finite subset:

\Gamma_0 \subseteq \Gamma

is satisfiable.

This means that whenever one chooses only finitely many sentences from $\Gamma$ , there is a structure in which all chosen sentences are true at the same time.

Theorem 5.4 (Compactness Theorem)

Let $\Gamma$ be a set of first order sentences.

If $\Gamma$ is finitely satisfiable, then $\Gamma$ is satisfiable.

Equivalently, if every finite subset of $\Gamma$ has a model, then there is a single structure that is a model of all sentences in $\Gamma$ .

The theorem says that an infinite set of first order requirements can fail to have a model only when some finite part of those requirements already fails to have a model.

Assume that $\Gamma$ is finitely satisfiable, and suppose for contradiction that $\Gamma$ is not satisfiable.

Then:

\Gamma \models \bot

By the completeness theorem for first order logic:

\Gamma \vdash \bot

A formal proof is finite, so this derivation of contradiction can use only finitely many assumptions from $\Gamma$ . Hence there is a finite subset:

\Gamma_0 \subseteq \Gamma

such that:

\Gamma_0 \vdash \bot

By soundness, or equivalently by completeness applied in the opposite direction, this finite subset is unsatisfiable:

\Gamma_0 \models \bot

This contradicts the assumption that every finite subset of $\Gamma$ is satisfiable. Therefore $\Gamma$ must be satisfiable.

Theorem 5.5 (Compactness in Consequence Form)

Let $\Gamma$ be a set of sentences, and let $A$ be a sentence.

If:

\Gamma \models A

then there exists a finite subset:

\Gamma_0 \subseteq \Gamma

such that:

\Gamma_0 \models A

Assume:

\Gamma \models A

Then there is no model of:

\Gamma \cup \{¬A\}

Thus:

\Gamma \cup \{¬A\}

is unsatisfiable.

By compactness, some finite subset is already unsatisfiable. Therefore there exists a finite set:

\Gamma_0 \subseteq \Gamma

such that:

\Gamma_0 \cup \{¬A\}

is unsatisfiable.

This means that every model of $\Gamma_0$ must be a model of $A$ , and hence:

\Gamma_0 \models A

Example 5.6 (Infinite Models from Finite Conditions)

Let the language contain one unary predicate symbol $P$ .

For each natural number $n \geq 1$ , let $A_n$ be the sentence:

\exists x_1 \cdots \exists x_n \left( \bigwedge_{1 \leq i < j \leq n} x_i \neq x_j \land \bigwedge_{1 \leq i \leq n} P(x_i) \right)

The sentence $A_n$ says that there are at least $n$ distinct elements satisfying $P$ .

Let:

\Gamma = \{A_n : n \geq 1\}

Every finite subset of $\Gamma$ contains only finitely many sentences:

A_{n_1}, A_{n_2}, \dots, A_{n_k}

Let:

N = \max(n_1,n_2,\dots,n_k)

A structure with $N$ elements, all satisfying $P$ , is a model of all these finitely many sentences.

Thus every finite subset of $\Gamma$ is satisfiable.

By compactness, $\Gamma$ itself is satisfiable. In any model of $\Gamma$ , for every natural number $n$ there are at least $n$ distinct elements satisfying $P$ . Therefore the set of elements satisfying $P$ is infinite.

Example 5.7 (Nonstandard Models of Arithmetic)

Let $\mathcal{L}$ be the usual language of arithmetic, and extend it by adding a new constant symbol $c$ .

Let $\Gamma$ consist of the axioms of arithmetic together with the sentences:

c > 0,\quad c > 1,\quad c > 2,\quad \dots

Every finite subset of $\Gamma$ mentions only finitely many inequalities:

c > 0,\quad c > 1,\quad \dots,\quad c > n

This finite set can be satisfied in the standard natural numbers by interpreting $c$ as a number larger than $n$ .

Therefore every finite subset of $\Gamma$ is satisfiable.

By compactness, the whole set $\Gamma$ has a model. In that model, the element denoted by $c$ is greater than every standard natural number.

Such a model cannot be the standard model $\mathbb{N}$ , because no ordinary natural number is greater than all ordinary natural numbers. Hence first order arithmetic has nonstandard models.

Corollary 5.8 (Finiteness is Not First Order Axiomatizable)

There is no set of first order sentences whose models are exactly the finite structures.

Suppose, for contradiction, that $\Gamma$ is a set of first order sentences such that a structure satisfies $\Gamma$ exactly when it is finite.

For each $n \geq 1$ , let $B_n$ be the sentence saying that there are at least $n$ distinct elements:

\exists x_1 \cdots \exists x_n \bigwedge_{1 \leq i < j \leq n} x_i \neq x_j

Consider:

\Gamma \cup \{B_n : n \geq 1\}

Every finite subset of this theory requires only finitely many distinct elements, and so it has a finite model satisfying $\Gamma$ .

By compactness, the whole theory has a model.

That model satisfies every $B_n$ , so it is infinite. It also satisfies $\Gamma$ , so by the assumed property of $\Gamma$ it must be finite.

This is impossible. Therefore finiteness cannot be characterized by any first order theory.

Corollary 5.9 (Arbitrarily Large Finite Models Give an Infinite Model)

Let $\Gamma$ be a first order theory.

If $\Gamma$ has finite models of arbitrarily large size, then $\Gamma$ has an infinite model.

For each $n \geq 1$ , let $B_n$ be the sentence saying that there are at least $n$ distinct elements:

\exists x_1 \cdots \exists x_n \bigwedge_{1 \leq i < j \leq n} x_i \neq x_j

Consider:

\Gamma \cup \{B_n : n \geq 1\}

Every finite subset of this theory requires only a lower bound on the size of a model. Since $\Gamma$ has finite models of arbitrarily large size, every such finite subset is satisfiable.

By compactness, the whole theory is satisfiable.

Any model of the whole theory has at least $n$ distinct elements for every $n$ , and therefore it is infinite.

Conceptual Meaning

Compactness says that first order satisfiability is controlled by finite information.

This is a powerful model construction principle. To build a model with infinitely many requirements, it is enough to show that every finite selection of those requirements can be satisfied.

At the same time, compactness reveals a limitation of first order logic. Properties that require a genuinely global distinction between finite and infinite behavior cannot usually be expressed by first order sentences.