Ordinals & Cardinals

Ordinal and cardinal numbers are the two fundamental tools set theory provides for extending the notion of “number” into the infinite. Ordinals generalize the idea of position in a sequence — first, second, third — far beyond the finite, while cardinals generalize the idea of size, answering the question “how many elements does a set have?” even when the answer is infinite. Developed primarily by Georg Cantor in the 1870s and 1880s and later placed on rigorous foundations by John von Neumann, these concepts reveal that infinity is not a single, monolithic idea but a richly structured hierarchy, with distinct arithmetics that behave in surprising and often counter-intuitive ways.

Ordinal Numbers and Transfinite Induction

The finite ordinals are simply the natural numbers: $0, 1, 2, 3, \ldots$, each representing the “order type” of a finite well-ordered set. The number $3$, for instance, is the order type of any set with three elements arranged in a definite sequence. But Cantor realized that well-ordered sets need not be finite, and that their order types extend far beyond the natural numbers. The first infinite ordinal, $\omega$, is the order type of the natural numbers themselves — the entire sequence $0, 1, 2, 3, \ldots$ viewed as a completed totality.

An ordinal number, in the modern formulation due to von Neumann, is defined as a transitive set that is well-ordered by the membership relation $\in$. A set $\alpha$ is transitive if every element of $\alpha$ is also a subset of $\alpha$. Under this definition, the ordinals begin as $0 = \emptyset$, $1 = \{0\} = \{\emptyset\}$, $2 = \{0, 1\} = \{\emptyset, \{\emptyset\}\}$, and in general each finite ordinal $n$ is the set of all smaller ordinals $\{0, 1, \ldots, n-1\}$. The first infinite ordinal is $\omega = \{0, 1, 2, 3, \ldots\}$, which is exactly the set of all finite ordinals. This elegant construction, in which every ordinal is literally the set of all ordinals below it, was introduced by von Neumann in 1923 and has become the standard definition in ZFC set theory, as described in The ZFC Axioms.

Ordinals come in two varieties beyond $0$. A successor ordinal is obtained by appending a single new element to an existing ordinal: the successor of $\alpha$ is $\alpha + 1 = \alpha \cup \{\alpha\}$. For example, $\omega + 1 = \omega \cup \{\omega\}$ is the well-ordered set consisting of all finite ordinals followed by $\omega$ itself. A limit ordinal is an ordinal that is not $0$ and not a successor — it is the supremum of all ordinals below it. The ordinal $\omega$ is the simplest limit ordinal; others include $\omega \cdot 2$, $\omega^2$, $\omega^\omega$, and vastly larger ones. The ordinal sequence stretches out into a breathtaking hierarchy:

$0, 1, 2, \ldots, \omega, \omega+1, \omega+2, \ldots, \omega \cdot 2, \ldots, \omega^2, \ldots, \omega^\omega, \ldots, \varepsilon_0, \ldots$

This sequence never terminates. For any collection of ordinals, there is always a larger one — the ordinals form a proper class, not a set.

The power of ordinals lies in transfinite induction and transfinite recursion, which extend the familiar principles of mathematical induction beyond the finite. Transfinite induction states: if a property $P$ holds for $0$, transfers from any ordinal $\alpha$ to its successor $\alpha + 1$, and holds at every limit ordinal $\lambda$ whenever it holds for all $\beta < \lambda$, then $P$ holds for every ordinal. This three-case structure — base case, successor case, limit case — is the backbone of virtually every construction in transfinite set theory. Transfinite recursion is the corresponding construction principle: it allows us to define a function on all ordinals by specifying its value at $0$, explaining how to compute it at $\alpha + 1$ from its value at $\alpha$, and defining it at limit ordinals as the supremum (or some other operation) over all previous values. The recursion theorem guarantees that such a definition always produces a unique, well-defined function. Cantor, Hausdorff, and later von Neumann all relied on these principles to build the hierarchies — such as the cumulative hierarchy $V_\alpha$ of sets — that structure modern set theory.

Cardinal Numbers and Cardinal Arithmetic

While ordinals measure order type, cardinal numbers measure size. Two sets have the same cardinality when there exists a bijection between them, and a cardinal number is, informally, the equivalence class of all sets of a given size. In ZFC, we make this precise using ordinals: a cardinal is defined as an ordinal $\kappa$ that is not equinumerous with (i.e., cannot be put in bijection with) any smaller ordinal. Such ordinals are called initial ordinals. Every finite ordinal is a cardinal, but among infinite ordinals, only certain ones qualify. The ordinal $\omega$ is a cardinal — it is the smallest infinite cardinal, usually denoted $\aleph_0$ — but $\omega + 1$, $\omega + 2$, and $\omega \cdot 2$ are all ordinals of the same cardinality as $\omega$ and therefore are not cardinals.

The arithmetic of infinite cardinals is dramatically different from both finite arithmetic and ordinal arithmetic. For infinite cardinals $\kappa$ and $\lambda$, addition and multiplication are both absorbing: the larger operand swallows the smaller. Specifically, if at least one of $\kappa, \lambda$ is infinite, then:

$\kappa + \lambda = \kappa \cdot \lambda = \max(\kappa, \lambda)$

This means, for instance, that $\aleph_0 + \aleph_0 = \aleph_0$ and $\aleph_0 \cdot \aleph_0 = \aleph_0$ — the set of integers has the same cardinality as the set of pairs of integers. More generally, $\aleph_1 + \aleph_0 = \aleph_1$ and $\aleph_\alpha \cdot \aleph_\alpha = \aleph_\alpha$ for every ordinal $\alpha$. These identities, first established by Cantor and given a complete proof by Felix Hausdorff and later by others using the Axiom of Choice, show that infinite cardinal addition and multiplication carry essentially no information beyond the ordering of the cardinals themselves.

Cardinal exponentiation, by contrast, is where the true complexity emerges. Cantor’s theorem states that for every cardinal $\kappa$, the power set of a set of cardinality $\kappa$ has strictly greater cardinality:

$2^\kappa > \kappa$

This is the engine that drives the entire cardinal hierarchy upward. The proof is a generalization of Cantor’s diagonal argument: given any function $f: X \to \mathcal{P}(X)$, the set $D = \{x \in X : x \notin f(x)\}$ cannot be in the range of $f$, so $f$ is not surjective. The result $2^{\aleph_0} > \aleph_0$ tells us that the real numbers (whose cardinality is $2^{\aleph_0}$) form a strictly larger set than the natural numbers — the uncountability of the continuum. But the exact value of $2^{\aleph_0}$ is famously undetermined by the ZFC axioms, a situation explored in depth in The Continuum Hypothesis.

An important structural notion for infinite cardinals is cofinality. The cofinality of a cardinal $\kappa$, written $\mathrm{cf}(\kappa)$, is the smallest ordinal $\delta$ such that there exists a cofinal increasing sequence of length $\delta$ converging to $\kappa$. A cardinal is regular if $\mathrm{cf}(\kappa) = \kappa$, and singular if $\mathrm{cf}(\kappa) < \kappa$. For example, $\aleph_0$ is regular (no finite sequence is cofinal in $\omega$), and $\aleph_1$ is regular, but $\aleph_\omega = \sup\{\aleph_0, \aleph_1, \aleph_2, \ldots\}$ is singular with $\mathrm{cf}(\aleph_\omega) = \omega$. Cofinality plays a decisive role in cardinal exponentiation: König’s theorem states that $\kappa^{\mathrm{cf}(\kappa)} > \kappa$, which in particular implies that $\mathrm{cf}(2^\kappa) > \kappa$ — the cofinality of a power cardinal is always strictly greater than the base.

Ordinal Arithmetic and Normal Forms

Ordinal arithmetic — addition, multiplication, and exponentiation — extends the familiar finite operations into the transfinite, but the resulting arithmetic is far more delicate than its cardinal counterpart. The crucial difference is that ordinal arithmetic is not commutative.

Ordinal addition is defined by transfinite recursion: $\alpha + 0 = \alpha$, $\alpha + (\beta + 1) = (\alpha + \beta) + 1$, and for limit ordinals $\lambda$, $\alpha + \lambda = \sup\{\alpha + \beta : \beta < \lambda\}$. The operation corresponds to placing one well-order after another. It is associative, but the failure of commutativity is dramatic. Consider the sum $1 + \omega$: placing a single element before the natural numbers gives a well-order isomorphic to $\omega$ itself, since the new element simply becomes a “new first element” of a copy of the natural numbers. But $\omega + 1$ places a single element after all the natural numbers, producing a strictly larger ordinal. Therefore:

$1 + \omega = \omega \neq \omega + 1$

Ordinal multiplication is similarly non-commutative. The product $\alpha \cdot \beta$ is defined as the order type of $\beta \times \alpha$ under the reverse lexicographic order (where the second coordinate varies faster). Then $2 \cdot \omega$ — two copies of $\omega$ placed in sequence — turns out to be $\omega$ again, because the combined sequence $0, 1, 2, \ldots, 0', 1', 2', \ldots$ has the same order type as the natural numbers. But $\omega \cdot 2$ is $\omega$ followed by another copy of $\omega$, which is the strictly larger ordinal $\omega + \omega$:

$2 \cdot \omega = \omega \neq \omega \cdot 2 = \omega + \omega$

Ordinal exponentiation is defined recursively as well: $\alpha^0 = 1$, $\alpha^{\beta+1} = \alpha^\beta \cdot \alpha$, and $\alpha^\lambda = \sup\{\alpha^\beta : \beta < \lambda\}$ for limit $\lambda$. The operation grows extremely fast. Already $\omega^\omega$ is a large countable ordinal, and the tower $\omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}}$ leads to a remarkable ordinal called $\varepsilon_0$.

The Cantor Normal Form theorem states that every ordinal $\alpha > 0$ can be written uniquely in the form:

$\alpha = \omega^{\beta_1} \cdot c_1 + \omega^{\beta_2} \cdot c_2 + \cdots + \omega^{\beta_k} \cdot c_k$

where $\beta_1 > \beta_2 > \cdots > \beta_k$ are ordinals and $c_1, c_2, \ldots, c_k$ are positive finite integers. This is the ordinal analogue of positional notation: every ordinal has a unique “base-$\omega$ expansion.” For finite ordinals, the Cantor normal form is simply $\omega^0 \cdot n = n$. For $\omega^2 + \omega \cdot 3 + 7$, the exponents are $2, 1, 0$ and the coefficients are $1, 3, 7$.

The epsilon numbers are ordinals $\varepsilon$ satisfying $\omega^\varepsilon = \varepsilon$ — they are the fixed points of the function $\alpha \mapsto \omega^\alpha$. The smallest such ordinal, $\varepsilon_0$, is the limit of the sequence $\omega, \omega^\omega, \omega^{\omega^\omega}, \ldots$ — an exponential tower of $\omega$s of every finite height. These fixed points were studied extensively by Cantor, and they arise naturally in proof theory: Gentzen’s celebrated 1936 result showed that $\varepsilon_0$ measures the proof-theoretic strength of Peano arithmetic, the standard axiomatization of the natural numbers. The Veblen hierarchy of normal functions $\varphi_\alpha$ enumerates further fixed points, producing ordinals of ever-increasing complexity.

Alephs and the Cardinal Hierarchy

The aleph numbers $\aleph_\alpha$, indexed by ordinals, form the complete enumeration of all infinite cardinals. They are defined by transfinite recursion: $\aleph_0 = \omega$ (the smallest infinite cardinal), $\aleph_{\alpha+1}$ is the smallest cardinal greater than $\aleph_\alpha$ (its existence guaranteed by Hartogs’ theorem, which produces for any set a well-ordered set that cannot be injected into it), and for limit ordinals $\lambda$, $\aleph_\lambda = \sup\{\aleph_\beta : \beta < \lambda\}$. This gives the ascending chain:

$\aleph_0 < \aleph_1 < \aleph_2 < \cdots < \aleph_\omega < \aleph_{\omega+1} < \cdots$

Every infinite cardinal is some $\aleph_\alpha$. The identification of which familiar sets have which alephs is one of the fundamental questions of set theory: $|\mathbb{N}| = \aleph_0$ is elementary, but determining whether $|\mathbb{R}| = \aleph_1$ is precisely the Continuum Hypothesis.

Running alongside the alephs is a second hierarchy: the beth numbers $\beth_\alpha$, which track iterated power sets. They are defined by $\beth_0 = \aleph_0$, $\beth_{\alpha+1} = 2^{\beth_\alpha}$, and $\beth_\lambda = \sup\{\beth_\beta : \beta < \lambda\}$ for limit $\lambda$. By Cantor’s theorem, each beth number is strictly larger than the previous one: $\beth_0 < \beth_1 < \beth_2 < \cdots$. Since $\beth_1 = 2^{\aleph_0}$ is the cardinality of the continuum and $\beth_2 = 2^{2^{\aleph_0}}$ is the cardinality of the set of all functions from $\mathbb{R}$ to $\mathbb{R}$, the beth numbers grow very rapidly.

The relationship between the alephs and the beths is controlled by the Generalized Continuum Hypothesis (GCH), which asserts that $2^{\aleph_\alpha} = \aleph_{\alpha+1}$ for every ordinal $\alpha$ — in other words, that $\beth_\alpha = \aleph_\alpha$ for all $\alpha$. Without GCH, we know only that $\beth_\alpha \geq \aleph_\alpha$, and the gap can in principle be enormous: it is consistent with ZFC that $2^{\aleph_0} = \aleph_2$, or $\aleph_{\omega_1}$, or many other values, subject only to the constraint from König’s theorem that $\mathrm{cf}(2^{\aleph_0}) > \aleph_0$. The intricate independence results surrounding these questions are the subject of The Continuum Hypothesis.

Among the alephs, the distinction between regular and singular cardinals organizes the hierarchy into two fundamentally different kinds. Successor cardinals $\aleph_{\alpha+1}$ are always regular. Limit cardinals such as $\aleph_\omega$ are typically singular — $\aleph_\omega$ is the supremum of the countable sequence $\aleph_0, \aleph_1, \aleph_2, \ldots$ and therefore has cofinality $\omega$. A weakly inaccessible cardinal is an uncountable regular limit cardinal — a cardinal so large that it cannot be reached by the successor operation or by taking suprema of smaller sets of smaller cardinals. The existence of such cardinals cannot be proved in ZFC, and they mark the boundary between “ordinary” set theory and the theory of large cardinals explored in Large Cardinals.

König’s theorem, proved by Julius König in 1905, provides the most powerful general constraint on cardinal exponentiation. In its full generality, it states that if $\kappa_i < \lambda_i$ for all $i$ in some index set $I$, then:

$\sum_{i \in I} \kappa_i < \prod_{i \in I} \lambda_i$

A key corollary is that no cardinal can be expressed as a sum of fewer than $\mathrm{cf}(\kappa)$ cardinals, each smaller than $\kappa$. Combined with Hausdorff’s formula and the Easton theorem (which shows that the function $\kappa \mapsto 2^\kappa$ on regular cardinals can be essentially arbitrary, subject only to monotonicity and König’s cofinality constraint), these results paint a picture in which cardinal arithmetic is tightly controlled by cofinality but otherwise remarkably unconstrained by the ZFC axioms. Shelah’s pcf theory (possible cofinalities theory), developed in the 1990s, provided deep new results about cardinal arithmetic for singular cardinals, showing that even without GCH there are surprising structural constraints — for instance, if $\aleph_\omega$ is a strong limit cardinal, then $2^{\aleph_\omega} < \aleph_{\omega_4}$. These results demonstrate that the interplay between ordinals and cardinals, far from being a settled subject, remains one of the most active frontiers of modern set theory.