Ordinals, Cardinals, and Transfinite Arithmetic

An ordinal is the order type of a well-ordered set; canonically (von Neumann) it is a transitive set well-ordered by $\in$, so each ordinal is the set of all smaller ordinals. A cardinal is an ordinal not equinumerous with any smaller ordinal — the canonical "least" representative of a class of equinumerous sets. The theory matters because it furnishes the backbone of transfinite induction and recursion, the measuring stick for sizes of infinite sets, and the index set for nearly every hierarchy in logic, topology, and analysis. The surprising fact: $\omega +1\ne 1+\omega$ and $2^{{\aleph }_0}$ cannot be pinned down by the standard axioms — its value is independent of ZFC (the Continuum Hypothesis).

The Core Insight

Counting answers two different questions that fuse in the finite but split in the infinite: "which position?" (ordinal) and "how many?" (cardinal). A well-ordering imposes a rigid skeleton (ordinal), while a mere bijection forgets all structure (cardinal). The entire transfinite edifice is the disciplined study of this split: ordinals are built by succession and taking limits (suprema), cardinals are the ordinals that genuinely "jump up" in size, and arithmetic on each obeys laws that look familiar but break commutativity (ordinals) or collapse to trivialities (cardinals under Choice).

Formal Statement

Well-Ordering and Order Type

A well-ordering of a set $A$ is a linear order $<$ such that every nonempty $S\subseteq A$ has a least element. Two ordered sets are order-isomorphic ($\cong$) if there is an order-preserving bijection between them. The order type is the isomorphism class. An ordinal is the canonical representative:

Here every element of an ordinal is itself an ordinal, and $\alpha <\beta ⟺\alpha \in \beta ⟺\alpha ⊊\beta$. The first few:

Successor, Limit, and the Ordinal Hierarchy

An ordinal $\alpha$ is a successor if $\alpha ={\beta }^{+}=\beta \cup \{\beta \}$ for some $\beta$, a limit if $\alpha \ne 0$ and $\alpha =\sup \{\beta :\beta <\alpha \}=\bigcup \alpha$, and $0$ otherwise. Every ordinal is exactly one of these three. The class $\mathrm{Ord}$ of all ordinals is itself well-ordered by $\in$ but is a proper class (the Burali-Forti paradox), not a set.

Cardinals and Cardinality

Two sets are equinumerous, $A\approx B$, iff a bijection exists. A cardinal is an initial ordinal:

Under the Axiom of Choice every set $A$ is well-orderable, so $|A|$ is the least ordinal equinumerous with $A$. Infinite cardinals are enumerated by the aleph function:

Cantor's Theorem and the Cardinal Hierarchy

For every set $A$, $|A|<|\mathcal{P}(A)|$. Hence there is no greatest cardinal, and the powerset operation yields the beth hierarchy:

Transfinite Arithmetic — Ordinals

Ordinal operations are defined by transfinite recursion, with limits handled by suprema:

Transfinite Arithmetic — Cardinals

For cardinals $\kappa ,\lambda$ with at least one infinite, define operations on disjoint unions, products, and function spaces:

Under AC, Hessenberg's theorem collapses additive/multiplicative cardinal arithmetic:

Cantor–Schröder–Bernstein

If there exist injections $A\hookrightarrow B$ and $B\hookrightarrow A$, then $A\approx B$. Consequently $\le$ on cardinals (defined by injectability) is antisymmetric, hence a partial order — and a linear order precisely under AC.

Why It Holds

Transfinite Induction and Recursion

The engine behind every definition above is transfinite induction. We prove its validity and that recursion is well-defined.

1. Induction principle. Let $\Phi$ be a property of ordinals such that: whenever $\Phi (\beta )$ holds for all $\beta <\alpha$, then $\Phi (\alpha )$ holds. Claim: $\Phi (\alpha )$ for all $\alpha$.

1. Suppose not. Then the class $C=\{\alpha :\neg \Phi (\alpha )\}$ is nonempty. Pick any $\gamma \in C$; the set $C\cap {\gamma }^{+}$ is a nonempty set of ordinals.

1. Since $\in$ well-orders $\mathrm{Ord}$, $C\cap {\gamma }^{+}$ has a least element ${\alpha }_0$. By minimality, $\Phi (\beta )$ holds for every $\beta <{\alpha }_0$.

1. By the hypothesis on $\Phi$, this forces $\Phi ({\alpha }_0)$ — contradicting ${\alpha }_0\in C$. Hence $C=\varnothing$. $\square$

1. Recursion. Given a class function $G$, there is a unique $F$ on $\mathrm{Ord}$ with $F(\alpha )=G(F\upharpoonright \alpha )$. Existence: the set of "approximations" (functions agreeing with the recursion on some initial segment) forms a chain whose union is $F$; uniqueness follows by induction (3)–(4) applied to the property "$F_1(\alpha )=F_2(\alpha )$." This legitimizes equations $[6]$.

Non-Commutativity of Ordinal Addition

We show $1+\omega =\omega \ne \omega +1$.

1. $1+\omega ={\sup }_{n<\omega }(1+n)$ by the limit clause of $[6]$. Each $1+n=n+1<\omega$, and these finite ordinals are cofinal in $\omega$, so the supremum is $\omega$.

1. $\omega +1=(\omega +0{)}^{+}={\omega }^{+}=\omega \cup \{\omega \}$ by the successor clause — a new element placed beyond every natural number.

1. Order-theoretically: "$1$ then $\omega$" puts a single point before an $\omega$-sequence, which is still just an $\omega$-sequence (the front point absorbs into the relabeling). But "$\omega$ then $1$" has a maximum element, which $\omega$ lacks; so they cannot be order-isomorphic.

1. Therefore $1+\omega =\omega <\omega +1$, establishing failure of commutativity. (Multiplication likewise fails: $2\cdot \omega =\omega \ne \omega \cdot 2=\omega +\omega$.) $\square$

Georg Cantor | 1845–1918

Cantor created set theory single-handedly between 1874 and 1897, introducing the diagonal argument, the distinction between countable and uncountable, the alephs, and transfinite ordinals. His 1874 paper proving $\mathbb{R}$ uncountable launched the field; his 1891 diagonal method generalized it to $[5]$. He formulated the Continuum Hypothesis and spent years trying (and failing) to prove it — a failure later vindicated as necessary by Gödel and Cohen. Battling rejection from Kronecker and recurring depression, Cantor nonetheless saw his "paradise" (Hilbert's phrase) become the foundation of modern mathematics.

Building Intuition

Think of ordinals as labeled positions in an infinite queue, and cardinals as the crowd size. Counting $0,1,2,\dots$ never reaches a "completed infinity," so we posit a new position $\omega$ standing beyond all of them — then $\omega +1,\omega +2,\dots ,\omega \cdot 2,\dots ,{\omega }^2,\dots ,{\omega }^{\omega },\dots ,{\epsilon }_0$. Crucially, all of these are still countable: you can list them in a single $\omega$-sequence, so they share one cardinal ${\aleph }_0$. The ordinal records how you arrange the queue; the cardinal records only how many people are in it. Addition is "concatenate the queues" — and order matters, because tacking one person onto the end of an endless line creates a last person, while tacking them onto the front changes nothing essential. Cardinal arithmetic, by contrast, is brutally simple: throw two infinite crowds together and you just get the bigger crowd ($[8]$). All the genuine difficulty migrates to exponentiation, $2^{\kappa }$, which is exactly where the axioms stop dictating answers.

The ordinal line up to $\omega^2$: successors as ticks, limits as accumulation points

Worked Examples

Cantor Normal Form arithmetic

1. Ordinal addition concatenates: place $\beta$ after $\alpha$. The leading term of $\beta$ is ${\omega }^2$.
2. Absorption rule: in $\alpha +\beta$, any term of $\alpha$ with exponent strictly less than the leading exponent of $\beta$ is swallowed. Here $\beta$ leads with ${\omega }^2$, equal to $\alpha$'s leading exponent — so we keep $\alpha$'s ${\omega }^2$ terms only if their coefficient adds.
3. The trailing terms $\omega \cdot 5$ and $7$ of $\alpha$ have exponent $<2$, so they vanish: ${\omega }^2\cdot 3+(\omega \cdot 5+7)+{\omega }^2={\omega }^2\cdot 3+{\omega }^2+\cdots ={\omega }^2\cdot 4+\cdots$.
4. Now append the rest of $\beta$: ${\omega }^2\cdot 4+\omega \cdot 2$.

Note $\beta +\alpha ={\omega }^2+\omega \cdot 2+{\omega }^2\cdot 3+\cdots ={\omega }^2\cdot 4+\omega \cdot 5+7\ne \alpha +\beta$ — non-commutativity in action.

Computing a cardinal of function spaces

1. Lower bound: $2^{{\aleph }_0}\le {\aleph }_1^{{\aleph }_0}$ since constant-domain choices already give $2^{{\aleph }_0}$.
2. Upper bound: ${\aleph }_1^{{\aleph }_0}\le (2^{{\aleph }_0}{)}^{{\aleph }_0}=2^{{\aleph }_0\otimes {\aleph }_0}=2^{{\aleph }_0}$, using ${\aleph }_1\le 2^{{\aleph }_0}$ and the exponent law plus $[8]$ (${\aleph }_0\otimes {\aleph }_0={\aleph }_0$).
3. By Cantor–Schröder–Bernstein the two bounds meet.

This holds in ZFC regardless of the value of $2^{{\aleph }_0}$ — a clean fact even though the continuum itself is undecided. (Compare: ${\aleph }_{\omega }^{{\aleph }_0}$ is not settled by ZFC, lying at the heart of Singular Cardinals and PCF Theory.)

Common Misconceptions

Cardinal vs. ordinal exponentiation diverge

Ordinally, $2^{\omega }={\sup }_{n<\omega }{2}^n=\sup \{1,2,4,8,\dots \}=\omega$ — a countable ordinal. Cardinally, $2^{{\aleph }_0}=|\mathcal{P}(\mathbb{N})|$ is uncountable by Cantor's theorem. The same symbols "$2$ raised to (something infinite)" yield $\omega$ in one regime and the continuum in the other, because ordinal exponentiation takes a supremum of order types while cardinal exponentiation counts all functions $\omega \to 2$. This single example demolishes any hope of treating the two arithmetics interchangeably.

Connections

Transfinite arithmetic is the connective tissue of set theory. The well-ordering of $\mathrm{Ord}$ powers Transfinite Induction and Recursion, used to build the Von Neumann Hierarchy $V_{\alpha }$ that stratifies the universe. Cardinal arithmetic feeds directly into Cardinal Invariants of the Continuum and the study of Large Cardinal Axioms, where cardinals like inaccessible and measurable are defined by closure properties of these very operations. The undecidability of $2^{{\aleph }_0}$ links to Forcing and Independence Proofs and the Continuum Hypothesis. Cofinality and singular cardinals open onto Singular Cardinals and PCF Theory. On the structural side, ordinals provide the index calculus for the Borel Hierarchy and Constructible Universe $L$, while the Axiom of Choice is the hinge converting cardinal comparability into a linear order.

Real-World Applications

1. Proof theory / ordinal analysis. The proof-theoretic strength of arithmetic is measured by ${\epsilon }_0={\omega }^{{\omega }^{{\omega }^{\cdots }}}$; Gentzen proved the consistency of Peano Arithmetic via transfinite induction up to ${\epsilon }_0$. Stronger theories get larger ordinals (Bachmann–Howard, Feferman–Schütte ${\Gamma }_0$).
2. Termination of programs and term-rewriting. Assigning ordinal "ranks" that strictly decrease proves termination; the Hydra game (Kirby–Paris) shows a process whose termination requires ordinals up to ${\epsilon }_0$ and is unprovable in PA.
3. Goodstein sequences. These always terminate, but the proof essentially encodes a strictly decreasing ordinal sequence in Cantor normal form — true yet unprovable in PA.
4. Descriptive set theory. The Borel and projective hierarchies are indexed by countable ordinals; ranks of well-founded trees and the analysis of ${\mathbf{\Pi }}_1^1$ sets rely on ${\omega }_1$.
5. Automated theorem proving & ordinal notation systems. Used in proof assistants (e.g. for measuring induction strength) and in defining recursive ordinal notations.
6. Database and game theory. Transfinite game lengths (e.g. determinacy of Gale–Stewart games) and fixed-point iterations in semantics (least fixed points reached by ordinal-indexed iteration) use these tools.
7. Topology. The space ${\omega }_1+1$ (the long line's discrete cousin) and the ordinal space $[0,{\omega }_1)$ supply canonical counterexamples (e.g. a sequentially compact but not compact space).

Historical Development

• 1874 — Cantor proves $\mathbb{R}$ is uncountable while $\mathbb{Q}$ is countable; the birth of transfinite set theory.
• 1878 — Cantor formulates the Continuum Hypothesis: no cardinality strictly between ${\aleph }_0$ and $2^{{\aleph }_0}$.
• 1883 — Cantor's Grundlagen introduces ordinals, the "second number class," and the principle of transfinite generation by succession and limit.
• 1891 — The diagonal argument generalizes uncountability to $|A|<|\mathcal{P}(A)|$ (Cantor's theorem $[5]$).
• 1895–97 — Cantor's Beiträge lay out cardinal and ordinal arithmetic; the symbol $\aleph$ debuts. Burali-Forti notes the paradox of the set of all ordinals (1897).
• 1904 — Zermelo proves the Well-Ordering Theorem from the Axiom of Choice, legitimizing $|A|$ as a cardinal for every set.
• 1908 — Hausdorff develops cofinality and confronts singular/regular cardinals; Hartogs (1915) constructs ${\aleph }_{\alpha +1}$ without Choice.
• 1923 — von Neumann gives the modern definition $[1]$: ordinals as transitive $\in$-well-ordered sets, $\alpha =\{\beta :\beta <\alpha \}$.
• 1938–1963 — Gödel ($L$, $\mathrm{Con}(\mathrm{ZFC}+\mathrm{CH})$, 1938–40) and Cohen (forcing, $\mathrm{Con}(\mathrm{ZFC}+\neg \mathrm{CH})$, 1963) prove CH independent of ZFC. Shelah's PCF theory (1980s–90s) tames singular cardinal arithmetic.

Subtleties & Limits

The deepest unresolved questions cluster around singular cardinal exponentiation and the value of the continuum. While $2^{{\aleph }_0}$ is fully independent (Cohen), the Singular Cardinals Hypothesis (SCH) — roughly, $2^{{\aleph }_{\omega }}$ is as small as König's theorem permits — can fail, but only at the cost of very large cardinals (Magidor, Gitik). Shelah's PCF theory yields the striking ZFC theorem $2^{{\aleph }_{\omega }}<{\aleph }_{{\omega }_4}$ if ${\aleph }_{\omega }$ is a strong limit, yet whether the bound ${\omega }_4$ can be improved to ${\omega }_1$ remains open. Beyond ZFC, the program of finding natural axioms (large cardinals, forcing axioms like PFA, or Woodin's $\Omega$-logic and the Ultimate-$L$ conjecture) that decide the continuum is among the central open enterprises of modern set theory. Whether there is a "correct" value of $2^{{\aleph }_0}$ — or whether the question is irreducibly pluralistic (multiverse view) — is itself debated.

See Also