---
title: Compactness and the Löwenheim–Skolem Theorems
module: Models, Compactness, and Theories
moduleNumber: 5
lessonNumber: 1
order: 501
summary: >
  A set of first-order sentences has a model whenever each of its finite
  subsets does. This compactness theorem follows from completeness and yields
  the finiteness limitation, the downward and upward Löwenheim–Skolem theorems,
  models of every infinite cardinality, and nonstandard models of arithmetic.
topics: [Models, Compactness, and Theories]
sources:
  - book: Enderton
    ref: "Ch. 2 — First-Order Logic; §2.6 Models of Theories (compactness, sizes of models)"
draft: false
---

The [completeness theorem](/logic/deductive-calculus/completeness-and-consistency)
equates deduction and truth for first-order logic:
$\Gamma \deduces \varphi$ exactly when $\Gamma \models \varphi$. Read at the level
of a whole set of sentences, that equivalence converts a finiteness fact about
deductions — every deduction is a finite object using only finitely many
hypotheses — into a theorem about models.

## Compactness for first-order logic

A deduction of $\varphi$ from $\Gamma$ is a finite sequence of formulas. It can
therefore invoke only finitely many members of $\Gamma$ as hypotheses. Combined
with the equivalence of consistency and satisfiability from the completeness
proof, this yields the semantic form of compactness.

> **Theorem (Compactness).** Let $\Gamma$ be a set of first-order sentences.
> $\Gamma$ is satisfiable if and only if every finite subset of $\Gamma$ is
> satisfiable. Equivalently, $\Gamma \models \varphi$ if and only if
> $\Gamma_0 \models \varphi$ for some finite $\Gamma_0 \subseteq \Gamma$.

The forward direction is immediate: a model of $\Gamma$ is a model of each
finite subset. The content is the converse. Suppose $\Gamma$ is unsatisfiable.
By completeness it is inconsistent, so $\Gamma \deduces \varphi$ and
$\Gamma \deduces \neg\varphi$ for some $\varphi$. Each of those two deductions is
finite and uses finitely many members of $\Gamma$; collect them into a finite
$\Gamma_0 \subseteq \Gamma$. Then $\Gamma_0$ proves both $\varphi$ and
$\neg\varphi$, so $\Gamma_0$ is inconsistent, hence unsatisfiable. Contrapositively,
if every finite subset is satisfiable then so is $\Gamma$.

$$
% caption: Every finite subset of $\Gamma$ having a model forces the whole
% infinite set to have one, because unsatisfiability could only come from a
% single finite inconsistent piece.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[draw, minimum width=20mm, minimum height=8mm, align=center] (a) at (0,1.6) {f\/inite piece\\has a model};
  \node[draw, minimum width=20mm, minimum height=8mm, align=center] (b) at (0,0.0) {f\/inite piece\\has a model};
  \node[draw, minimum width=20mm, minimum height=8mm, align=center] (c) at (0,-1.6) {f\/inite piece\\has a model};
  \node[align=center, font=\scriptsize] at (0,-2.7) {every f\/inite subset};
  \node[draw=acc, thick, fill=acc!10, minimum width=24mm, minimum height=16mm, align=center] (w) at (6.2,0) {whole set\\has a model};
  \draw[->, acc, thick] (a.east) -- (w.north west);
  \draw[->, acc, thick] (b.east) -- (w.west);
  \draw[->, acc, thick] (c.east) -- (w.south west);
\end{tikzpicture}
$$

The [sentential version](/logic/sentential-logic/compactness-and-effectiveness)
was proved directly from König's lemma; here the first-order version is a
corollary of completeness.[^cat]

## Finite and infinite models

Some sentences constrain the size of their models. Every model of
$\forall x \, \forall y \; x = y$ has exactly one element. Others admit only
infinite models: the sentence asserting that $<$ is an ordering with no largest
element is true in $(\mathbb{N}, <)$ but in no finite ordering. Compactness
forbids the intermediate case where a set of sentences has arbitrarily large
finite models but no infinite one.

For each integer $k \geq 2$ there is a sentence $\lambda_k$ saying "there are at
least $k$ distinct things," built by asserting the existence of $k$ pairwise
distinct elements:

$$
\lambda_2 = \exists v_1 \, \exists v_2 \; v_1 \neq v_2,
\qquad
\lambda_3 = \exists v_1 \, \exists v_2 \, \exists v_3 \; (v_1 \neq v_2 \wedge v_1 \neq v_3 \wedge v_2 \neq v_3).
$$

> **Theorem (Infinite models from arbitrarily large finite models).** If a set $\Sigma$ of sentences has arbitrarily large finite
> models, then it has an infinite model.

> **Proof.** Consider $\Sigma \cup \{\lambda_2, \lambda_3, \dots\}$. Any finite
> subset mentions only finitely many of the $\lambda_k$, so it is satisfied by any
> model of $\Sigma$ with enough elements — one exists because $\Sigma$ has
> arbitrarily large finite models. By compactness the entire set has a model, and
> that model satisfies every $\lambda_k$, so it is infinite. $\square$

The theorem rules out subtle finite/infinite dividing lines. No equation of
group theory can be true in every finite group and false in every infinite one:
if it held in arbitrarily large finite groups it would hold in an infinite group
too.

> **Worked example (No identity separates finite from infinite groups).**
> Suppose an equation $\varepsilon$ in the language of groups held in every
> finite group. Collect the group axioms with $\varepsilon$ into
> $$
> \Sigma = \{\text{associativity},\ \text{identity},\ \text{inverses},\ \varepsilon\}.
> $$
> The cyclic groups $\mathbb{Z}/n\mathbb{Z}$ are finite groups, so each models
> $\Sigma$, and they have $n$ elements for every $n$: $\Sigma$ has arbitrarily
> large finite models. By the infinite-model theorem $\Sigma$ has an infinite
> model, an infinite group in which $\varepsilon$ holds. So $\varepsilon$ cannot
> hold in every finite group yet fail in every infinite one.

### Elementary classes

The infinite-model theorem is best phrased through the notion of an elementary class. A class
$K$ of structures is **$\mathrm{EC}$** if $K = \Mod \tau$ for a single sentence
$\tau$, and **$\mathrm{EC}_{\Delta}$** if $K = \Mod \Sigma$ for a set $\Sigma$ of
sentences.

> **Corollary (Finiteness and infinitude are not elementary).** For a fixed language, the class of all finite structures
> is not $\mathrm{EC}_{\Delta}$, and the class of all infinite structures is not
> $\mathrm{EC}$.

The infinite structures do form an $\mathrm{EC}_{\Delta}$ class, namely
$\Mod\{\lambda_2, \lambda_3, \dots\}$. But no single sentence captures them: were
$\Mod \tau$ to contain the infinite structures and nothing else, then $\Mod \neg\tau$
would contain the finite ones and nothing else, and by the infinite-model theorem that class is not even
$\mathrm{EC}_{\Delta}$. First-order logic can require infinity (with infinitely
many sentences) but cannot forbid it with a finite axiom, and cannot express
"finite" at all.

This limitation extends to decidability. For a finite structure $\fA$
in a finite language, $\Th \fA$ is decidable: replace $\fA$ by
an isomorphic copy on the universe $\{1, \dots, n\}$, then evaluate any sentence
by a finite tree search, each quantifier triggering a sweep of the $n$ elements.
One might hope the sentences true in every finite structure form a decidable
set. They do not. Trakhtenbrot's theorem (1950) states that
$\{\sigma \mid \sigma \text{ is true in every finite structure}\}$ is not
decidable and not even effectively enumerable, so the enumerability results that
hold for validity over all structures fail when attention is restricted to
finite ones.

## The size of a model

The completeness proof built a model out of syntax. Its size can be read off
the construction. Starting from a consistent set $\Gamma$ in a countable
language, one adjoins countably many new constant symbols and takes the universe
of the term model to be equivalence classes of terms. A countable language has
countably many terms, so the term model is countable.[^ls]

> **Theorem (Löwenheim–Skolem, downward).**
> (a) A satisfiable set of formulas in a countable language is satisfiable in
> some countable structure.
> (b) A set of sentences in a countable language that has any model has a
> countable model.

> **Proof.** By soundness, satisfiability implies consistency; by the completeness
> construction, a consistent set in a countable language is satisfied in a
> countable term model. $\square$

Applied with $\Gamma = \Th \fA$, this gives a countable structure
elementarily equivalent to any structure for a countable language. If
$\fB \models \Th \fA$ then $\fA \equiv \fB$,
since every sentence true in $\fA$ lies in $\Th \fA$ and so
holds in $\fB$, and the same runs through negations. The real field
$(\mathbb{R}; 0, 1, +, \cdot)$ is uncountable, yet some countable field satisfies
exactly the same first-order sentences; the field of real algebraic numbers is
one such.

> **Worked example (A countable field with the first-order theory of $\mathbb{R}$).**
> The real field $(\mathbb{R}; 0, 1, +, \cdot)$ is uncountable, but its language
> has finitely many parameters, hence is countable. The set $\Th(\mathbb{R}; 0,
> 1, +, \cdot)$ is satisfiable, so by the downward theorem it has a countable
> model $\fB$. Since $\fB \models \Th(\mathbb{R}; 0, 1, +, \cdot)$, every
> sentence true in $\mathbb{R}$ holds in $\fB$, and every sentence false in
> $\mathbb{R}$ has its negation in the theory and so fails in $\fB$; therefore
> $\fB \equiv (\mathbb{R}; 0, 1, +, \cdot)$. The field of real algebraic numbers
> realizes such a $\fB$: countable, and a model of exactly the first-order
> sentences true of the reals.

$$
% caption: The downward theorem extracts, from any model of a countable
% language, a countable model in which exactly the same sentences hold.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[draw=black, fill=black!5] (0,0) ellipse (2.6 and 1.9);
  \node[align=center] at (0,1.35) {model of any size};
  \draw[draw=acc, thick, fill=acc!12] (0.1,-0.35) ellipse (1.35 and 0.85);
  \node[acc, align=center, font=\scriptsize] at (0.1,-0.35) {countable\\submodel};
  \node[align=center, font=\scriptsize] at (6.0,0) {same f\/irst-order\\sentences true\\in both};
  \draw[->, acc, thick] (2.7,-0.2) -- (4.4,-0.2);
\end{tikzpicture}
$$

### Skolem's paradox

Take a consistent set $A_{ST}$ of axioms for set theory. It has a model, so by
the downward theorem it has a countable model $\fS$. Among the
consequences of $A_{ST}$ is a sentence asserting the existence of uncountably
many sets. That sentence holds in the countable $\fS$. The apparent
conflict, "Skolem's paradox," dissolves on inspection. Within $\fS$
there is no element coding a bijection between the naturals and the universe.
The uncountability sentence asserts precisely that no such internal bijection
exists. That a genuine bijection exists outside $\fS$, in the
ambient set theory, is no contradiction, because it is not an element of the
model.

## Larger models and nonstandard arithmetic

Compactness runs the other way as well: it manufactures elements that no
standard model contains. Consider the standard structure of arithmetic

$$
\fN = (\mathbb{N}; 0, S, <, +, \cdot).
$$

Add a fresh constant symbol $c$ and the sentences

$$
\Sigma = \{\, 0 < c, \; S0 < c, \; SS0 < c, \; \dots \,\},
$$

each saying that $c$ exceeds a particular standard numeral. Any finite subset of
$\Sigma \cup \Th \fN$ mentions finitely many of these, so it is
satisfied in $\fN$ with $c$ interpreted as a large enough natural
number. By compactness the whole set has a model, and by the downward theorem a
countable model $\fM$. Restricting $\fM$ to the original
language gives $\fM_0 \equiv \fN$: it satisfies every sentence
of $\Th \fN$, hence exactly the same sentences as $\fN$. Yet it
is not isomorphic to $\fN$, because the element interpreting $c$ is
larger than every standard numeral.

$$
% caption: Adjoining a constant $c$ forced above every numeral produces an
% element beyond all standard naturals, giving a model of true arithmetic not
% isomorphic to the standard one.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[thick] (-0.3,0) -- (7.6,0);
  \foreach \x/\n in {0.4/0, 1.4/1, 2.4/2, 3.4/3, 4.4/4} {
    \fill (\x,0) circle (1.6pt);
    \node[below, font=\scriptsize] at (\x,-0.1) {\n};
  }
  \foreach \x in {5.2,5.5,5.8} \fill (\x,0) circle (0.8pt);
  \fill[acc] (6.9,0) circle (2.2pt);
  \node[acc, below, font=\scriptsize] at (6.9,-0.1) {c};
  \draw[acc, thick] (0.4,0.45) -- (0.4,0.62) -- (4.4,0.62) -- (4.4,0.45);
  \node[font=\scriptsize] at (2.4,0.95) {standard numerals};
  \node[acc, align=center, font=\scriptsize] at (6.9,0.9) {beyond every\\standard numeral};
\end{tikzpicture}
$$

The element interpreting $c$ is a nonstandard, "infinite" natural number. Every
first-order sentence true of $\mathbb{N}$ remains true of $\fM_0$, so no
first-order property distinguishes the two structures; the difference lives
entirely in the isomorphism type, which first-order logic cannot detect. The same
construction on $(\mathbb{N}, <)$ shows that "there is no infinite descending
chain" is not first-order expressible: a nonstandard model has descending chains
below its infinite elements yet agrees with $\mathbb{N}$ on every sentence.

> **Worked example (A finite subset of $\Sigma \cup \Th \fN$ is satisfiable).**
> The construction rests on satisfying each finite subset in the standard
> $\fN$. Take the finite subset
> $$
> \{\, 0 < c, \; S0 < c, \; SS0 < c \,\} \cup \Delta_0,
> $$
> where $\Delta_0$ is any finite part of $\Th \fN$. Interpret $c$ as $3$ inside
> $\fN$. Then
> $$
> 0 < 3, \qquad S0 = 1 < 3, \qquad SS0 = 2 < 3
> $$
> all hold, and $\Delta_0 \subseteq \Th \fN$ holds because $\fN$ is its own
> model. A subset naming numerals up to $S^k 0$ is satisfied by taking $c = k+1$,
> since $S^k 0 = k < k+1$. Every finite subset is therefore satisfiable, so by
> compactness the whole set has a model; the downward theorem makes it countable,
> and its element interpreting $c$ exceeds every $S^n 0$.

### Upward Löwenheim–Skolem

The nonstandard construction generalizes to any cardinality. The upward part is
due to Tarski, giving the combined theorem its "LST" label.[^lst]

> **Theorem (LST).** Let $\Sigma$ be a set of formulas in a language of
> cardinality $\lambda$, and suppose $\Sigma$ is satisfiable in some infinite
> structure. Then for every cardinal $\kappa \geq \lambda$ there is a structure
> of cardinality $\kappa$ in which $\Sigma$ is satisfiable.

> **Proof.** Let $\fA$ be an infinite model of $\Sigma$. Adjoin a set $C$
> of $\kappa$ new constant symbols and the sentences $\Delta = \{c_1 \neq c_2 \mid
> c_1, c_2 \text{ distinct in } C\}$. Any finite subset of $\Sigma \cup \Delta$
> names finitely many new constants, and since $\fA$ is infinite it has
> room to interpret them as distinct elements. By compactness $\Sigma \cup \Delta$
> is satisfiable, hence by the downward construction it is satisfiable in a
> structure $\fB$ of cardinality at most that of the expanded language, which is
> $\kappa$. But $\fB$ interprets $\kappa$ distinct constants, so its cardinality
> is at least $\kappa$; hence exactly $\kappa$. Restrict to the original language.
> $\square$

$$
% caption: The upward theorem adjoins $\kappa$ distinct new constants and uses
% compactness to inflate any infinite model to one of cardinality $\kappa$.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[draw=black, fill=black!5] (0,0) circle (1.1);
  \node[align=center, font=\scriptsize] at (0,0) {inf\/inite\\model};
  \draw[->, acc, thick] (1.4,0) -- (3.3,0);
  \node[align=center, font=\scriptsize] at (2.35,0.55) {adjoin distinct};
  \node[align=center, font=\scriptsize] at (2.35,-0.5) {new constants};
  \draw[draw=acc, thick, fill=acc!10] (5.4,0) circle (1.9);
  \node[acc, align=center, font=\scriptsize] at (5.4,0) {model of any\\larger size};
\end{tikzpicture}
$$

> **Corollary (Löwenheim–Skolem–Tarski).** (a) A set of sentences in a countable language with some
> infinite model has models of every infinite cardinality. (b) Every infinite
> structure for a countable language is elementarily equivalent to a structure
> of each infinite cardinality.

## The failure of first-order categoricity

Call a set $\Sigma$ of sentences **categorical** if any two of its models are
isomorphic. The Löwenheim–Skolem–Tarski theorem forces a verdict: a set of first-order sentences with
an infinite model is never categorical, because it has non-isomorphic models of
different cardinalities. In particular no set of first-order sentences has
exactly the structures isomorphic to $(\mathbb{N}; 0, S, +, \cdot)$ as its
models. The natural numbers are not first-order categorical.

$$
% caption: An infinite model spawns models of every larger cardinality, so no
% first-order theory with an infinite model can pin its models to one
% isomorphism type.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[draw, circle, minimum size=7mm] (a) at (0,0) {};
  \node[font=\scriptsize, below=1pt of a] {countable};
  \node[draw=acc, thick, circle, minimum size=12mm] (b) at (3,0) {};
  \node[acc, font=\scriptsize, below=1pt of b] {uncountable};
  \node[draw=acc, thick, circle, minimum size=18mm] (c) at (6.4,0) {};
  \node[acc, font=\scriptsize, below=1pt of c] {larger still};
  \draw[->, acc, thick] (a) -- (b);
  \draw[->, acc, thick] (b) -- (c);
  \node[align=center, font=\scriptsize] at (3.2,1.6) {all elementarily equivalent, none isomorphic};
\end{tikzpicture}
$$

Categoricity remains only in restricted forms. A theory can be
_categorical in a cardinality_ — all its models of a fixed size isomorphic —
even though it has non-isomorphic models across sizes. This weaker notion,
$\kappa$-categoricity, still forces completeness through the
[Łoś–Vaught test](/logic/models-and-theories/theories-elementary-classes-and-categoricity).
Full categoricity returns only in
[second-order logic](/logic/second-order-logic/second-order-languages), where the
induction axiom quantifies over subsets and pins $\mathbb{N}$ to a single
isomorphism type, at the cost of compactness and completeness.

| Question about size | First-order answer | Mechanism |
| --- | --- | --- |
| Force models infinite? | yes, with infinitely many sentences | $\{\lambda_2, \lambda_3, \dots\}$ |
| Force models finite by one sentence? | no | the infinite-model theorem |
| Express "finite"? | no | not $\mathrm{EC}_{\Delta}$ |
| Shrink a model to countable? | yes | downward Löwenheim–Skolem |
| Grow an infinite model? | yes, to any $\kappa \geq \lambda$ | upward (LST) |
| Pin the naturals up to isomorphism? | no | the Löwenheim–Skolem–Tarski theorem |

The recurring technique in every construction is the same: write down the
sentences describing the structure wanted, argue that each finite subset is
satisfiable in a structure already at hand, and let compactness supply the
rest.

[^ls]: Enderton, §2.6 — Löwenheim–Skolem theorem (Löwenheim 1915, Skolem 1920) and its statement for countable and for cardinality-$\lambda$ languages.
[^lst]: Enderton, §2.6 — the upward "LST" theorem (upward part due to Tarski) and Corollary 26F on models of every infinite cardinality.
[^cat]: Enderton, §2.6 — the compactness theorem for first-order logic (from completeness), Theorem 26A on arbitrarily large finite models, Corollary 26B on elementary classes, and the non-categoricity of first-order theories with infinite models.