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 (finitely axiomatized schema). 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+2AAF	Elementary	Substructure
κ	U+03BA	Kappa	Cardinal
ℵ₀	U+2135	Aleph-null	Countable
\|M\|	—	Cardinality	Size of M

Metatheory. Lindström: FOL maximal with compactness + L-S. Abstract model theory. Absoluteness questions. Morley categoricity.

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

Limitations. Skolem paradox philosophically puzzling. Categorical theories impossible (infinite). Non-constructive in general.