Skip to content

5.2 Lowenheim Skolem Theorems

Downward and upward Lowenheim Skolem theorems and their consequences for model sizes in first order logic.

logic model theory lowenheim skolem cardinality

The Lowenheim Skolem theorems describe how the size of models of a first order theory can be changed without affecting truth of sentences, and they show that if a theory has any infinite model, then it has models of many different infinite sizes, which reveals an important limitation of first order logic in controlling cardinality.

Definition 5.10 (Cardinality of a Structure)

Let M\mathcal{M} be a structure with underlying set MM.

The cardinality of M\mathcal{M} is defined as the cardinality of MM, which is the number of elements in the domain of the structure.

A structure is finite if its domain is finite, and it is infinite if its domain is infinite.

Definition 5.11 (Countable Structures)

A structure is countable if its domain is finite or countably infinite, that is, if its elements can be listed as:

a0,a1,a2,… a_0, a_1, a_2, \dots

A language is countable if it has only countably many symbols, which is the case for most languages used in mathematics.

Theorem 5.12 (Downward Lowenheim Skolem Theorem)

Let L\mathcal{L} be a countable language, and let Γ\Gamma be a set of L\mathcal{L}-sentences.

If Γ\Gamma has an infinite model, then Γ\Gamma has a countable model.

More generally, if Γ\Gamma has a model of cardinality κ\kappa, then for every infinite cardinal λ\lambda with:

ℵ0≤λ≤κ \aleph_0 \leq \lambda \leq \kappa

there is a model of Γ\Gamma of cardinality λ\lambda.

This theorem says that large infinite models can always be reduced to smaller infinite models without losing satisfaction of the theory.

Proof Idea

The proof constructs a smaller model by selecting a subset of the original domain that is closed under the functions and relations required to interpret the language.

Starting from a given model, one builds a countable substructure by repeatedly adding elements that are required to witness existential statements, ensuring that all formulas that were true in the original structure remain true in the smaller one.

The construction proceeds step by step, adding only countably many elements, so that the resulting structure is countable.

Theorem 5.13 (Upward Lowenheim Skolem Theorem)

Let Γ\Gamma be a set of sentences in a first order language L\mathcal{L}.

If Γ\Gamma has an infinite model of cardinality κ\kappa, then for every infinite cardinal λ≥κ\lambda \geq \kappa, there exists a model of Γ\Gamma of cardinality λ\lambda.

This theorem says that once a theory has one infinite model, it has arbitrarily large models.

Proof Idea

The proof uses compactness.

Extend the language by adding new constant symbols:

cαfor α<λ c_\alpha \quad \text{for } \alpha < \lambda

Add sentences stating that these constants are all distinct:

cα≠cβfor α≠β c_\alpha \neq c_\beta \quad \text{for } \alpha \neq \beta

Call the resulting theory Γ′\Gamma'.

Every finite subset of Γ′\Gamma' mentions only finitely many constants, so it can be satisfied in a sufficiently large model of Γ\Gamma.

By compactness, Γ′\Gamma' has a model, and in that model there are at least λ\lambda distinct elements.

Thus there exists a model of Γ\Gamma of cardinality at least λ\lambda, and by taking an appropriate substructure one obtains a model of exactly that size.

Corollary 5.14 (No Control of Infinite Cardinality)

If a first order theory has an infinite model, then it has models of arbitrarily large infinite cardinalities.

Therefore first order logic cannot distinguish between different infinite sizes.

Example 5.15

Consider the theory of dense linear orders without endpoints.

This theory has a countable model, namely the rational numbers.

By the upward Lowenheim Skolem theorem, it also has models of every infinite cardinality, including uncountable ones.

Thus the same theory describes structures of many different sizes.

Skolem Paradox

The Lowenheim Skolem theorems lead to an apparent paradox when applied to set theory.

Set theory proves the existence of uncountable sets, yet by the downward Lowenheim Skolem theorem, there exists a countable model of set theory.

This seems contradictory, since the model is countable but believes that some sets are uncountable.

The resolution is that countability is a property of the domain from an external point of view, while inside the model there is no bijection between certain sets and the natural numbers, so those sets are uncountable within the model.

Thus there is no contradiction, only a difference between internal and external perspectives.

Corollary 5.16 (Noncategoricity)

A theory is categorical in a given cardinality if all its models of that size are isomorphic.

The Lowenheim Skolem theorems show that most first order theories with infinite models are not categorical across all infinite cardinalities, since they admit models of many different sizes.

This demonstrates a limitation of first order logic as a tool for uniquely characterizing mathematical structures.

Conceptual Meaning

The Lowenheim Skolem theorems show that first order logic has limited expressive power when it comes to controlling the size of models.

While it can describe structural properties of models, it cannot enforce a specific infinite cardinality.

This reinforces the idea that first order logic is well suited for local properties, but not for global size constraints, and it highlights the importance of model theoretic methods in understanding the behavior of formal theories.