Löwenheim-Skolem Theorems

The Löwenheim-Skolem theorems address the cardinality of models of first-order theories. They show that first-order logic cannot control the size of its models, a phenomenon known as the "Skolem paradox."

Statements

Theorem4.2Downward Löwenheim-Skolem

Let $\mathcal{M}$ be an $\mathcal{L}$ -structure with $A \subseteq M$ . Then there exists an elementary substructure $\mathcal{N} \preceq \mathcal{M}$ with $A \subseteq N$ and $|N| \leq |A| + |\mathcal{L}| + \aleph_0$ .

Theorem4.3Upward Löwenheim-Skolem

If $T$ is a consistent $\mathcal{L}$ -theory with an infinite model, then for every cardinal $\kappa \geq |\mathcal{L}| + \aleph_0$ , $T$ has a model of cardinality $\kappa$ .

Proof Sketch of Downward LS

Proof

Given $\mathcal{M}$ and $A \subseteq M$ , construct a chain $A = A_0 \subseteq A_1 \subseteq A_2 \subseteq \cdots$ where at each step, for each $\mathcal{L}(A_n)$ -formula $\exists x \, \varphi(x, \bar{a})$ true in $\mathcal{M}$ , add a witness $b \in M$ with $\mathcal{M} \models \varphi(b, \bar{a})$ . Let $N = \bigcup_n A_n$ . Then $|N| \leq |A| + |\mathcal{L}| + \aleph_0$ (adding $\leq |\mathcal{L}| + \aleph_0$ witnesses at each step, $\omega$ steps). The substructure $\mathcal{N}$ with domain $N$ satisfies $\mathcal{N} \preceq \mathcal{M}$ by the Tarski-Vaught test: every existential statement true in $\mathcal{M}$ about elements of $N$ has a witness in $N$ . $\square$

■

Consequences

ExampleSkolem's Paradox

ZFC (if consistent) has a countable model $\mathcal{M}$ by the downward Löwenheim-Skolem theorem. Yet $\mathcal{M} \models$ "there exist uncountable sets." The resolution: "uncountable" in $\mathcal{M}$ means there is no bijection within $\mathcal{M}$ from the set to $\omega^{\mathcal{M}}$ , not that the set is genuinely uncountable from outside.

RemarkCategoricity and Counting Models

A theory $T$ is $\kappa$ -categorical if it has exactly one model (up to isomorphism) of cardinality $\kappa$ . The Löwenheim-Skolem theorems show that a first-order theory with an infinite model cannot be categorical in all cardinalities. Morley's theorem states that if $T$ is $\kappa$ -categorical for some uncountable $\kappa$ , then $T$ is $\kappa$ -categorical for all uncountable $\kappa$ .