In 1915, Leopold Löwenheim proved a startling result about first-order formulas, later generalized by Thoralf Skolem in 1920: if a first-order theory has an infinite model of any cardinality, it must possess a model of every infinite cardinality. The Löwenheim-Skolem Theorems fundamentally shattered the belief that first-order axiomatic systems could uniquely pin down the absolute size of mathematical universes, precipitating the infamous “Skolem Paradox” at the heart of axiomatic set theory.
1. Elementary Submodels & The Tarski-Vaught Criterion
To state the Löwenheim-Skolem theorems rigorously, we must introduce the notion of an elementary submodel. Given structures $mathcal{A}$ and $mathcal{B}$ with $mathcal{A} subseteq mathcal{B}$:
$mathcal{A}$ is a substructure if operations and relations in $mathcal{A}$ are restrictions of those in $mathcal{B}$. However, truth can easily fail to transfer. For example, $mathbb{Z} subseteq mathbb{Q}$, but the sentence $exists x (2x = 1)$ is false in $mathbb{Z}$ and true in $mathbb{Q}$.
Definition: Elementary Submodel ($mathcal{A} prec mathcal{B}$)
$mathcal{A}$ is an elementary submodel of $mathcal{B}$ (written $mathcal{A} prec mathcal{B}$) if for every formula $phi(x_1, dots, x_n)$ and every tuple of parameters $a_1, dots, a_n in A$:
[
mathcal{A} vDash phi(a_1, dots, a_n) iff mathcal{B} vDash phi(a_1, dots, a_n)
]
How do we verify this infinite condition? Tarski and Vaught (1957) provided the definitive algebraic test:
The Tarski-Vaught Criterion
$mathcal{A} prec mathcal{B}$ if and only if for every formula $phi(x, y)$ and every parameter $b in A$, if $mathcal{B} vDash exists x , phi(x, b)$, then there exists an element $a in A$ such that $mathcal{B} vDash phi(a, b)$.
An elementary submodel must contain internal witnesses for all existential claims satisfied in the larger superstructure.
2. Downward Löwenheim-Skolem Theorem
Downward Löwenheim-Skolem Theorem
Let $mathcal{B}$ be an infinite structure in a language $mathcal{L}$, and let $S subseteq B$ be a subset. Then there exists an elementary submodel $mathcal{A} prec mathcal{B}$ such that $S subseteq A$ and:
[
|A| = max(|S|, |mathcal{L}|, aleph_0)
]
Proof Sketch (Skolem Functions): For each formula $phi(x, y)$, choose a Skolem function $f_phi: B^n to B$ selecting a witness whenever $exists x , phi(x, y)$ holds. Close the set $S$ under the countably many Skolem functions by forming $A = bigcup_{n=0}^infty S_n$, where $S_0 = S$ and $S_{n+1} = S_n cup { f_phi(vec{a}) mid vec{a} in S_n }$. Because $|mathcal{L}|$ is at most countable, each step adds at most $|S| cdot aleph_0$ elements. By construction, $A$ satisfies the Tarski-Vaught criterion, yielding $mathcal{A} prec mathcal{B}$ of cardinality $|S| + aleph_0$. $blacksquare$
3. Upward Löwenheim-Skolem Theorem
Upward Löwenheim-Skolem Theorem
Let $mathcal{A}$ be an infinite structure in a language $mathcal{L}$, and let $kappa$ be any cardinal such that $kappa ge max(|A|, |mathcal{L}|)$. Then there exists an elementary extension $mathcal{B} succ mathcal{A}$ such that $|B| = kappa$.
Proof: Add $kappa$ distinct new constant symbols ${c_alpha mid alpha < kappa}$ to the elementary diagram of $mathcal{A}$. By Compactness, any finite subset mentions only finitely many $c_alpha$, which can be assigned distinct elements of $A$. Hence a model of size $kappa$ exists. $blacksquare$
4. Skolem’s Paradox: The Relativity of Set Theory
The most shocking philosophical earthquake generated by the Downward Löwenheim-Skolem Theorem concerns Zermelo-Fraenkel Set Theory ($text{ZFC}$):
- $text{ZFC}$ is formulated in a finite first-order language containing only one relation symbol ($in$). Thus $|mathcal{L}| = aleph_0$.
- $text{ZFC}$ proves Cantor’s Theorem: the power set of natural numbers $mathcal{P}(mathbb{N})$ is uncountable. That is, $text{ZFC} vdash text{“There exists no bijection between } omega text{ and } mathcal{P}(omega)text{“}$.
- If $text{ZFC}$ is consistent, it has a model $mathcal{M} vDash text{ZFC}$.
- By the Downward Löwenheim-Skolem Theorem, $text{ZFC}$ must have a COUNTABLE model $mathcal{M}_{text{countable}}$!
How can a model containing only a countable number of elements satisfy the theorem that uncountable sets exist? This is Skolem’s Paradox.
The Resolution: Uncountability is an internal, relational property, not an absolute one. In $mathcal{M}_{text{countable}}$, the set representing real numbers is indeed countable from the outside: an external observer can construct a bijection $f: mathbb{N} to mathcal{P}^mathcal{M}(omega)$. However, the function $f$ is not an element of the model $mathcal{M}_{text{countable}}$! From within the model, no bijection exists. Hence, $mathcal{M}_{text{countable}}$ correctly judges the set to be uncountable.
The Löwenheim-Skolem Theorems establish that concepts like “countable” and “uncountable” are not absolute properties of mathematical objects, but relative perspectives dictated by the expressive scope of the observer’s model.
