Löwenheim–Skolem Theorem — Mathematics Knowledge System

Overview

The Löwenheim–Skolem theorem describes how little control first-order logic has over the cardinality (size) of the models of a theory. The downward form says that if a countable first-order theory has an infinite model, it has a model of every infinite cardinality up to and including ℵ₀ (countably infinite) — in particular, it has a countable model, even if the theory was designed with an uncountable structure in mind. The upward form says that if a theory has an infinite model, it has models of every infinite cardinality larger than that model too. Together, downward and upward Löwenheim–Skolem show that no first-order theory with an infinite model can pin down a unique infinite cardinality for its models — this is the technical content behind Skolem's paradox: Zermelo–Fraenkel set theory (ZFC) proves the existence of uncountable sets, yet if ZFC is consistent it has a countable model (by downward Löwenheim–Skolem applied to ZFC itself), meaning a model that is 'from the outside' countable nonetheless satisfies, from the inside, the sentence asserting the existence of uncountable sets. This is not a contradiction — it reflects that 'countable' and 'uncountable' are relative to which bijections exist, and a countable model of ZFC may simply lack the bijection (from inside the model) that would witness its universe or some subset of it as countable, even though such a bijection exists outside the model looking in.

Intuition

Think of a first-order theory as a set of rules written in a language with only countably many symbols and sentences — no matter how big a model you feed those rules, the rules themselves can only 'see' and constrain countably much information at a time. Downward Löwenheim–Skolem exploits this: given any (possibly huge) model, one can extract a countable 'sub-model' that still satisfies exactly the same first-order sentences, essentially by repeatedly adding just enough witnesses to satisfy every existential statement the theory could ever demand, and closing off after only countably many rounds (a Skolem hull construction). Upward Löwenheim–Skolem runs the compactness-theorem trick in reverse: if the theory has an infinite model, first-order logic simply cannot add enough extra sentences to forbid a bigger one from existing — you can always force in more distinct elements by adding new constants and inequality sentences between them (the same compactness technique used to build infinite models from arbitrarily-large-finite ones). Skolem's paradox is the resulting apparent tension: ZFC internally proves 'there exists an uncountable set' as a sentence, yet ZFC — being a countable first-order theory with an infinite model — must, by downward Löwenheim–Skolem, also have a countable model; that model still satisfies the ZFC sentence asserting uncountability, but simply doesn't contain, as one of its own elements, the specific bijection that would demonstrate countability of the relevant set from an outside vantage point.

Formal Definition

Definition

For a first-order theory (or countable set of sentences) T in a countable language, with an infinite model:

T \text{ has an infinite model} \implies \forall\, \kappa \ge \aleph_0,\ T \text{ has a model of cardinality } \kappa \text{, for } \kappa \ge |T|

Löwenheim–Skolem (combined form)

T \text{ has an infinite model} \implies T \text{ has a countable model} \quad (\kappa = \aleph_0)

Downward Löwenheim–Skolem

T \text{ has an infinite model } \mathcal{M} \implies \forall\, \kappa \ge |\mathcal{M}|,\ T \text{ has a model of size } \kappa

Upward Löwenheim–Skolem

Worked Examples

ZFC is a first-order theory in a countable language (finitely many symbols: ∈, =, logical connectives). If ZFC is consistent, it has a model.
$\text{ZFC consistent} \implies \text{ZFC has a model } \mathcal{M}$
By downward Löwenheim–Skolem, ZFC then also has a COUNTABLE model M₀, since ZFC (as a countable set of axioms) has an infinite model.
$\implies \exists\, \mathcal{M}_0 \models \text{ZFC},\ |\mathcal{M}_0| = \aleph_0$
But ZFC proves the sentence 'there exists an uncountable set' (e.g. asserting the power set of ω is uncountable), so M₀ ⊨ 'ℙ(ω) is uncountable' — even though M₀ itself, viewed from outside, has only countably many elements total.
$\mathcal{M}_0 \models \ulcorner \mathcal{P}(\omega) \text{ is uncountable} \urcorner$

Answer: No contradiction: 'uncountable' inside M₀ only means 'M₀ contains no bijection between that set and ω' — M₀ can simply be missing the very bijection that an outside observer (with access to the full countable enumeration of M₀'s elements) can see exists. Countability is not absolute; it depends on which functions are available as objects inside the model.

Practice Problems

Difficulty 6/10

Does the downward Löwenheim–Skolem theorem imply that the real numbers ℝ (as an ordered field) have a countable elementary substructure satisfying exactly the same first-order sentences as ℝ?

Difficulty 7/10

Why can't first-order logic categorically axiomatize 'the natural numbers, and nothing else' (i.e., have Peano arithmetic's models all be isomorphic to ℕ)?

Difficulty 8/10

Explain precisely why Skolem's paradox does not contradict Cantor's theorem that the power set of any set is strictly larger in cardinality.

Quiz

Summary

Downward Löwenheim–Skolem: a countable first-order theory with an infinite model has a countable model, no matter how large the original model.
Upward Löwenheim–Skolem: a theory with an infinite model has models of every larger infinite cardinality too, provable via the compactness theorem.
Together they show first-order logic cannot pin down the cardinality of infinite models, which produces Skolem's paradox for ZFC — resolved by noting countability is relative to which bijections exist inside vs. outside a model.

References

WebsiteWikipedia — Löwenheim–Skolem theorem
WebsiteWikipedia — Skolem's paradox