The Löwenheim-Skolem Theorem: Shrinking and Stretching Models

What the theorem actually claims

Fix a first-order language L (its signature of function, relation, and constant symbols) of cardinality |L|, and let κ = |L| + ℵ₀. The theorem comes in two halves.

• Downward (Löwenheim-Skolem-Tarski): If M is an L-structure and A ⊆ M is any subset, then M has an elementary substructure N with A ⊆ N and |N| ≤ |A| + κ. In particular, any infinite structure in a countable language has a countable elementary substructure.
• Upward: If M is an infinite L-structure and λ ≥ |M| + κ is any cardinal, then M has an elementary extension N with |N| = λ.

The crucial word is elementary. N ≼ M means N ⊆ M and for every first-order formula φ(x̄) and every tuple ā from N, M ⊨ φ(ā) if and only if N ⊨ φ(ā). So N and M satisfy exactly the same first-order statements about shared elements — not merely the same sentences, but the same formulas with parameters. The two models are logically indistinguishable from inside first-order logic, yet can differ wildly in size.

The picture: logic is blind to cardinality

Here is the vivid takeaway. First-order logic can express "there exist at least n distinct things" for each finite n, so it can force a model to be infinite. But it has no sentence, or even infinite set of sentences, that says "there are exactly ℵ₀ things" versus "there are exactly ℵ₁ things." The machinery — finite formulas, finite quantifier strings, a fixed countable stock of variables — can only ever reach out and name countably many elements at a time.

So imagine the real ordered field ℝ, uncountable and complete. The downward theorem hands you a countable subfield that is an elementary substructure: it satisfies every first-order truth about ℝ, including all the field and order axioms and every first-order consequence. From the inside, its inhabitants would "believe" they live in the full real line. Symmetrically, the upward theorem lets you stretch ℕ into elementary extensions of size ℵ₁, ℵ₇, or ℵ_ω — models teeming with 'infinite natural numbers' that still satisfy every first-order theorem of arithmetic.

The mechanism: Skolem functions and the Tarski-Vaught test

The engine of the downward theorem is the Tarski-Vaught test: a substructure N ⊆ M is elementary iff for every formula φ(x, ȳ) and every tuple b̄ from N, whenever M ⊨ ∃x φ(x, b̄) there already exists a witness a ∈ N with M ⊨ φ(a, b̄). In words: N is elementary exactly when it is closed under witnesses to existential formulas.

Skolem hull construction. For each formula φ(x, ȳ) pick (using choice) a Skolem function f_φ that, given b̄, outputs some witness a in M whenever one exists. Start with your set A₀ = A. Close it under all Skolem functions: A₁ = A₀ ∪ {f_φ(b̄) : all φ, all b̄ from A₀}, then A₂, and so on. Because there are only |L| + ℵ₀ formulas and each step adds at most |Aₙ| + κ new elements, the union N = ⋃ₙ Aₙ has size ≤ |A| + κ and is closed under witnesses. By Tarski-Vaught, N ≼ M. The upward direction instead uses compactness: adjoin λ new constant symbols cᵢ with axioms cᵢ ≠ cⱼ; every finite subset is satisfiable in M, so by compactness the whole set has a model, which must have ≥ λ elements — then apply downward to trim it to exactly λ.

Worked example and the canonical special case

Skolem's paradox. The sharpest illustration lives inside set theory itself. Zermelo-Fraenkel set theory ZFC is a first-order theory in the countable language {∈}. Assuming ZFC is consistent, it has a model; by the downward theorem it has a countable model 𝔐. But ZFC proves the existence of uncountable sets — indeed it proves Cantor's theorem, that ℝ is uncountable. How can a countable universe contain an 'uncountable' set?

The resolution is a lesson in relativization. 'x is uncountable' means there is no bijection from ω onto x. Inside 𝔐 there really is a set r that 𝔐 believes is uncountable — because no bijection between ω and r exists as an element of 𝔐. Viewed from outside, r has only countably many elements and such a bijection exists in the real world; it simply is not a member of the model. 'Countable' is not absolute: it depends on which bijections your model happens to contain. The paradox is only apparent — a mismatch between internal and external viewpoints, exactly what elementary equivalence permits.

Why the hypotheses matter — and what breaks

Every hypothesis earns its place:

• First-order is essential. In second-order logic (quantifying over all subsets) you can categorically axiomatize ℕ up to isomorphism and characterize ℝ as the unique complete ordered field — both fail Löwenheim-Skolem. The theorem is really a signature of first-order logic's expressive weakness; Lindström's theorem makes this exact: first-order logic is the strongest logic satisfying both compactness and downward Löwenheim-Skolem.
• Infinite model needed for upward. Finite structures obviously can't be stretched: the theory of a 3-element set has no model of size 5. And a theory can pin down each finite cardinality individually.
• Choice. The Skolem-function construction uses the axiom of choice; over ZF, the full theorem is equivalent to a choice principle (the ultrafilter/Boolean-prime-ideal or dependent-choice level, depending on the version).

A key corollary: no first-order theory with an infinite model is categorical (it always has non-isomorphic models). Categoricity survives only relative to a fixed cardinality — the subject of Morley's categoricity theorem.

Significance: what it unlocks

Löwenheim-Skolem is one of the two pillars of classical model theory, alongside the compactness theorem — and indeed the upward half is essentially a compactness argument. Its consequences ripple outward:

• Non-standard models. The upward theorem manufactures models of arithmetic and analysis with 'infinite' and 'infinitesimal' elements, the launching pad for Abraham Robinson's non-standard analysis, where infinitesimals are rigorous first-class objects.
• Categoricity theory. Because absolute categoricity is impossible, the right question becomes κ-categoricity (unique model of size κ up to isomorphism). Vaught's test, the Łoś-Vaught test for completeness, and ultimately Morley's theorem (κ-categorical for one uncountable κ ⇒ for all) grow directly from this soil.
• Foundations. Skolem's paradox reshaped how logicians think about 'absolute' notions like countability and set existence, feeding into forcing and independence proofs.

It is, in short, the theorem that tells you first-order logic trades the ability to control size for the compactness and completeness that make model theory tractable — a bargain at the heart of the whole subject.

Downward vs. upward Löwenheim-Skolem, and what each requires and delivers

	Downward LS	Upward LS
Hypothesis	Structure M with |M| ≥ |L| + ℵ₀, subset A ⊆ M	Infinite structure M, cardinal λ ≥ |M| + |L|
Conclusion	Elementary substructure N ≼ M with A ⊆ N and |N| = |A| + |L| + ℵ₀	Elementary extension M ≼ N with |N| = λ
Main tool	Skolem functions / Tarski-Vaught test	Compactness theorem (add λ new constants)
Direction of size	Shrinks: makes models smaller (down to |L| + ℵ₀)	Stretches: makes models larger (arbitrarily big)
Needs infinite model?	Only nontrivial when M is infinite	Yes — requires an infinite base model
Fails for	Second-order logic; finite structures	Second-order logic; keeps no upper cardinal bound