Löwenheim-Skolem Theorem

Origin. Löwenheim (1915), Skolem (1920). Countable models exist for satisfiable first-order theories. Upward version: arbitrarily large models. Paradox: set theory has countable models.

Models. Downward: if Γ has infinite model, has countable model. Upward: if Γ has infinite model, has models of every cardinality ≥|Γ|. Size not first-order definable.

Formalism.

Downward Löwenheim-Skolem: If Γ has an infinite model M, then Γ has a countable model N. If M infinite and A ⊆ M, there exists elementary N ⪯ M with A ⊆ N and |N| ≤ |A| + |L| + ℵ₀.

Upward Löwenheim-Skolem: If Γ has infinite model, then for all κ ≥ |Γ| + ℵ₀, Γ has a model of cardinality κ.

Proof techniques: Downward: Skolem functions + closure. Upward: add constants + compactness.

Skolem paradox: ZFC is countable (countably many axioms, given by schemas). If ZFC consistent, has countable model. Inside model: "uncountable" sets exist! Resolution: "uncountable" is relative to model.

Elementary substructure: M ⪯ N: M subset of N, same FOL truths. Tarski-Vaught test.

Corollaries: No first-order categorical theory of infinite structures. Finite model property failures. Nonstandard models.

Symbols.

Symbol	Unicode	Name	Meaning
Γ	U+0393	Gamma	A set of sentences: the theory
κ	U+03BA	Kappa	A cardinal: the size of the model produced
ω	U+03C9	Omega	The first infinite ordinal, indexing L_ω₁ω
₀	U+2080	Subscript zero	Index in ℵ₀
₁	U+2081	Subscript one	Index in ω₁, in L_ω₁ω
ℕ	U+2115	Double-struck N	The naturals, not fixed up to isomorphism
ℝ	U+211D	Double-struck R	The reals, likewise
ℵ	U+2135	Aleph	Cardinal notation
≤	U+2264	Less than or equal	The bound on the elementary submodel
≥	U+2265	Greater than or equal	The condition on κ in the upward theorem
⊆	U+2286	Subset of or equal to	A ⊆ M: the set the submodel must contain
⪯	U+2AAF	Precedes above single-line equals	Elementary substructure: N ⪯ M
ℵ₀	—	Aleph-null	The first infinite cardinal
\|M\|	—	Cardinality	The number of elements of M
M, N	—	Structures	A model and its elementary sub- or extension
A	—	Parameter set	The subset the submodel is required to contain
L	—	Language	Its cardinality enters the bound
L_ω₁ω	—	Infinitary logic	Keeps the downward theorem, loses the upward one
ZFC	—	Zermelo–Fraenkel with Choice	The theory of the Skolem paradox
Tarski-Vaught	—	Tarski-Vaught test	The criterion for being an elementary substructure

Metatheory. Löwenheim (1915) proved the downward theorem for a single sentence; Skolem (1920) extended it to countable sets of sentences with what became Skolem functions, and Tarski and Vaught (1957) put it in its modern form — every infinite structure has an elementary substructure of cardinality at most |A| + |L| + ℵ₀ containing any prescribed subset A, verified by the Tarski-Vaught test. The upward direction is a compactness argument: adjoin κ new constants together with axioms saying they are pairwise distinct. Together the two mean that no first-order theory with an infinite model constrains the cardinality of its models, so absolute categoricity is impossible and only categoricity in a cardinal survives — which is what Morley (1965) classified, proving that categoricity in one uncountable cardinal forces it in all of them. Lindström (1969) showed the property is definitive rather than incidental: the downward theorem together with compactness characterizes first-order logic among regular abstract logics. The downward proof chooses Skolem functions and so uses choice; for countable languages dependent choice suffices.

Applies to. Model theory foundations. Nonstandard analysis. Set theory paradoxes. Infinite combinatorics.

Limitations. The theorem is a limitation more than it has limitations: it says first-order logic cannot control the size of its models, and the rest follows. No first-order theory with an infinite model is categorical, so ℕ, ℝ, and the cumulative hierarchy are none of them describable up to isomorphism; nonstandard models of arithmetic and of analysis exist for that reason and cannot be excluded by adding axioms. Skolem's own conclusion was that set-theoretic notions are relative: a countable model of ZFC contains a set it takes to be uncountable, because the bijection witnessing countability is not in the model. Nor does the pair of directions survive outside first-order logic — L_ω₁ω keeps the downward theorem and loses the upward one, and second-order logic under standard semantics loses both. And the models are asserted rather than exhibited, since the downward proof selects Skolem functions by choice.