Löwenheim–Skolem Theorem

The Löwenheim–Skolem theorem is a fundamental result in model theory concerning the sizes of structures satisfying first-order logic theories. In its familiar countable-language form, it states that a theory with an infinite model has models of every infinite cardinality, including a countably infinite model. Its stronger structural formulations provide elementary substructures and elementary extensions: smaller or larger structures that preserve the truth of first-order formulas. The downward and upward versions together show that first-order theories cannot uniquely characterize an infinite structure across all cardinalities. (people.maths.ox.ac.uk)

Logical setting

A first-order language, or signature, specifies constant, function, and relation symbols. A structure interprets these symbols on a nonempty domain; a theory is a set of sentences in that language. A structure is a model of a theory when it satisfies every sentence of the theory. The size of a model means the cardinality of its domain. (thecatbus.github.io)

An elementary substructure $N$ of a structure $M$, written $N\preccurlyeq M$, is a substructure such that, for every first-order formula $\varphi(\bar x)$ and every finite tuple $\bar a$ from $N$,

Thus truth is preserved even for formulas containing parameters from the smaller structure. Equivalently, $M$ is an elementary extension of $N$. This is stronger than merely satisfying the same sentences, and much stronger than being an ordinary substructure. (math.libretexts.org)

Downward and upward forms

Let $L$ be a first-order language and $M$ an infinite $L$-structure. Write $|L|$ for the number of nonlogical symbols and $\aleph_0$ for the cardinality of the natural numbers.

Downward Löwenheim–Skolem theorem. For every subset $A\subseteq M$, there is an elementary substructure $N\preccurlyeq M$ containing $A$ with

More precisely, whenever

one can choose such an $N$ with $|N|=\kappa$. (people.maths.ox.ac.uk)

Upward Löwenheim–Skolem theorem. For every cardinal

there is an elementary extension $N\succcurlyeq M$ with $|N|=\kappa$. Consequently, if an $L$-theory has an infinite model, it has a model of every infinite cardinality at least $|L|$. (people.maths.ox.ac.uk)

For a finite or countably infinite language, the downward theorem therefore gives a countably infinite elementary substructure of every infinite structure. No assumption that the theory is computably axiomatized is needed: the relevant bound concerns the language and the available formulas. (thecatbus.github.io)

Ideas behind the proofs

The downward proof preserves witnesses to existential formulas. Begin with a chosen set of elements. Whenever

for parameters already included, add one element witnessing that statement. Include interpretations of constants and close under the language’s functions. Repeat this process through countably many stages and take the union. Every finite tuple in the union appears at some stage, so every required existential witness appears at a later stage. The Tarski–Vaught test then establishes elementarity. (math.libretexts.org)

The cardinal bound follows because there are at most $\max\{|L|,\aleph_0\}$ formulas, each uses finitely many parameters, and each stage adds only the corresponding witnesses and function values. Starting with $\kappa$ elements, where $\kappa$ is infinite and at least $|L|$, therefore produces exactly $\kappa$ elements. (thecatbus.github.io)

The upward proof uses the compactness theorem. Add $\kappa$ new constants and sentences requiring distinct constants to name distinct elements. Every finite subset is satisfiable in an infinite model, so compactness yields a model with at least $\kappa$ elements. The downward theorem reduces its size to exactly $\kappa$. To obtain an elementary extension, include the elementary diagram of the original structure: all sentences true in it after adding names for its elements. (math.libretexts.org)

Skolem’s paradox

An important application concerns Zermelo–Fraenkel set theory and its extension with the axiom of choice, ZFC. These are first-order theories in a countable language. If ZFC is consistent, Gödel’s completeness theorem gives a model, and Löwenheim–Skolem gives a countable model. Yet the model satisfies Cantor’s theorem and therefore asserts the existence of uncountable sets. This apparent conflict is called Skolem’s paradox. (plato.stanford.edu)

There is no contradiction. An internally uncountable set has only countably many members when viewed from outside a countable model. However, an external enumeration need not be represented by any function belonging to that model. The model’s assertion of uncountability excludes suitable enumerating functions within its own universe, not every function available externally. Moreover, its membership relation need not be ordinary membership restricted to a transitive collection of sets. (plato.stanford.edu)

The application is conditional: the theorem does not itself prove that ZFC is consistent or that it has a model. (people.maths.ox.ac.uk)

Expressive limitations

Models of different cardinalities cannot be isomorphic. Hence no first-order theory with an infinite model can have exactly one model up to isomorphism across all sizes. This does not prevent categoricity in a specified cardinality, meaning uniqueness among models of that particular size. The distinction separates unrestricted uniqueness from cardinal-specific classification. (thecatbus.github.io)

The theorem is specific to first-order logic and does not hold generally for second-order logic under full semantics. Second-order quantifiers range over all subsets or relations of the appropriate kind, permitting sentences that characterize countable domains or require uncountable ones. Such sentences directly obstruct the corresponding upward or downward conclusions. (builds.openlogicproject.org)

Together with completeness and compactness, Löwenheim–Skolem identifies a characteristic combination of strengths and limitations of first-order logic: robust model-existence results coexist with an inability to fix the size of an infinite domain. (builds.openlogicproject.org)

Historical development

Leopold Löwenheim established the original result in 1915 in the framework of the calculus of relatives. Thoralf Skolem supplied a simpler proof in 1920 and a different proof in 1922, refining the methods for constructing small models. Skolem’s 1922 discussion of axiomatized set theory also introduced the apparent paradox concerning countable models and internally uncountable sets. The modern terminology of elementary substructures expresses these results more precisely than the original formulations. (richardzach.org)

References

1. Mathematical Logic II, Section 6: Elementary Extensionspeople.maths.ox.ac.uk
2. 4: Substructures and the Löwenheim-Skolem Theoremsmath.libretexts.org
3. Model Theory: Theorems of Löwenheim and Skolemthecatbus.github.io
4. Skolem’s Paradoxplato.stanford.edu
5. Open Logic Textbuilds.openlogicproject.org
6. The Development of Mathematical Logicrichardzach.org