# 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.