Ordinal Arithmetic and the First Uncountable Ordinal

Let $G$ be a class function: a rule, given by a formula in the language of set theory, that assigns a set $G(h)$ to every function $h$ whose domain is an ordinal (Ordinal (von Neumann)). Then there is a class function $F$, given by a formula and defined at every ordinal, such that

$F(\beta )=G(F\upharpoonright \beta )\text{for every ordinal }\beta ,$

and $F$ is the only one: any class function $F^{\mathrm{\prime }}$ defined at every ordinal and satisfying $F^{\mathrm{\prime }}(\beta )=G(F^{\mathrm{\prime }}\upharpoonright \beta )$ for every ordinal $\beta$ agrees with $F$ at every ordinal. Here $F\upharpoonright \beta$ is the restriction of $F$ to the set $\beta$ of ordinals below $\beta$, which is a set even though $F$ is not.

Like Transfinite recursion, this is a theorem schema of ZF: one theorem for each formula defining $G$. It uses Replacement, inherited from that theorem, and it uses no form of the Axiom of Choice.

Why the published theorem does not already say this. Transfinite recursion is stated for a well-order $(W,<)$, that is for a set, and it delivers one function whose domain is that set. An operation such as $\alpha +\beta$ has to be defined at every ordinal $\beta$, and the ordinals are not a set (Burali-Forti: there is no set of all ordinals), so no single instance of the published theorem defines it. What is proved below is exactly the bridge: the instances at the individual ordinals cohere, and the coherence is supplied by the published theorem's own uniqueness clause. No new recursion principle is introduced.

What is spent. Replacement, through Transfinite recursion, and Separation, at step 6.1. No choice principle appears anywhere, for the same reason as in the published theorem: at every stage the object used is the unique function with a given domain, never one selected from many.

Three cases, not two. The lemma says nothing about how $G$ is given. In practice $G$ is defined by the three-way split of Successor and limit ordinals — a value at $0$, a rule at a successor, a rule at a limit — and that split is exhaustive and exclusive for every ordinal. Writing "successor or limit" and forgetting $0$ is the standard way to define an operation that is undefined at $0$.

Why the restriction is a set. Step 4.1 is not bookkeeping. $F$ is a proper class, so "$F\upharpoonright \beta$" needs an argument, and the argument is that it coincides with the restriction of the set function $F_{{\beta }^{+}}$. Without it, $G(F\upharpoonright \beta )$ would not even be an application of $G$ to a set.

The naming. Some texts state this as "transfinite recursion on the class of ordinals" and prove it directly by a least-counterexample argument. The route taken here spends nothing new: it reuses the published theorem at each ordinal and glues, and the glue is that theorem's uniqueness clause.

Fix an ordinal $\alpha$ (Ordinal (von Neumann)). There is exactly one class function $\beta \mapsto {\mathrm{s}}_{\alpha }(\beta )$, defined at every ordinal $\beta$, satisfying the three clauses

${\mathrm{s}}_{\alpha }(0)=\alpha ,{\mathrm{s}}_{\alpha }({\beta }^{+})=({\mathrm{s}}_{\alpha }(\beta ){)}^{+},{\mathrm{s}}_{\alpha }(\lambda )=\bigcup \{{\mathrm{s}}_{\alpha }(\beta ):\beta \in \lambda \}(\lambda \text{ a limit ordinal}),$

and every value ${\mathrm{s}}_{\alpha }(\beta )$ is an ordinal.

The three clauses are exhaustive and mutually exclusive, because every ordinal is exactly one of $0$, a successor, or a limit (Successor and limit ordinals). The union in the third clause is the least upper bound of the earlier values (Basic closure properties of ordinals, claim (e)), so the limit clause reads "take the supremum of what has been built so far".

This is the well-definedness obligation discharged before ordinal addition is written down; the operation itself is named in the definition that follows. The proof is a theorem of ZF and uses no choice principle.

Why a bridge lemma is used and not Transfinite recursion directly. The published recursion theorem is stated for a well-order, that is for a set, and delivers a function whose domain is that set. What is needed here is a rule defined at every ordinal, and the ordinals are not a set. Transfinite recursion along the ordinals: a class rule determines exactly one operation defined at every ordinal is exactly that bridge, and it is proved from the published theorem's uniqueness clause.

Three cases, and the one that is usually forgotten. Writing the recursion with a successor clause and a limit clause only leaves the operation undefined at $0$, since $0$ is neither. The published Successor and limit ordinals states the three-way split in the form used at step 1.2, and it is cited rather than assumed.

The same argument serves multiplication and exponentiation. Only the three clauses of $G$ change. The two corollaries later on this page repeat this proof with different clauses, and the exponentiation case additionally restricts the limit clause to $0<\beta <\lambda$; see Ordinal exponentiation exists and is unique, with the limit clause taken over $0<\beta <\lambda$ so that $0^{\lambda }=0$ for why that restriction is not optional.

Let $\alpha$ and $\beta$ be ordinals (Ordinal (von Neumann)). The sum $\alpha +\beta$ is defined by recursion on $\beta$, in the three cases of Successor and limit ordinals:

$\alpha +0=\alpha ,\alpha +{\beta }^{+}=(\alpha +\beta {)}^{+},\alpha +\lambda =\bigcup \{\alpha +\beta :\beta \in \lambda \}(\lambda \text{ a limit ordinal})\mathrm{.}$

That exactly one operation satisfies these three clauses, and that all its values are ordinals, is Ordinal addition exists and is unique: the clauses at $0$, at a successor and at a limit determine one operation, and its values are ordinals, proved immediately above. The union in the limit clause is the least upper bound of the values already produced (claim (e) of Basic closure properties of ordinals), so it may be written $\sup$ and the clause read as "at a limit, take the supremum".

Notation. We write $1=0^{+}$, $2=1^{+}$, and so on for the finite ordinals, and $\sup$ for $\bigcup$ applied to a set of ordinals. The successor operation is now a special case of addition:

$\alpha +1=\alpha +0^{+}=(\alpha +0{)}^{+}={\alpha }^{+},$

so from here on $\alpha +1$ and ${\alpha }^{+}$ denote the same ordinal, and both notations are used, whichever reads better.

• The recursion is on the right argument only. The left argument $\alpha$ is a parameter, frozen before the recursion starts. This asymmetry is not an artefact of the presentation: ordinal addition is genuinely asymmetric, and the asymmetry is exactly what FALSE: ordinal addition is commutative and FALSE: $\beta <\gamma$ implies $\beta +\alpha <\gamma +\alpha$ exhibit later on this page.

• What the clauses say concretely. $\alpha +\beta$ is "$\alpha$, and then $\beta$ more steps". $\alpha +\beta$ is the order type of $\alpha$ followed by $\beta$ turns that picture into a theorem: $\alpha +\beta$ is the order type of a copy of $\alpha$ followed by a copy of $\beta$. The order-type description is usually the one to compute with; the recursion is the one that makes the definition legitimate.

• The first interesting value. $\omega$ is the least limit ordinal ($\omega$ is the least limit ordinal), and it is the least ordinal at which the third clause fires at all: below $\omega$ every ordinal is $0$ or a successor, so below $\omega$ this recursion is literally the Peano recursion for addition on $\mathbb{N}$. That the two agree there is On $\omega$ the ordinal $+$ and $\cdot$ are the Peano operations: $\omega$ is closed under ordinal $+$, $\cdot$ and exponentiation, and for naturals $m,n$ the ordinal $m+n$ and $m\cdot n$ are the natural-number sum and product, and it is a theorem, not a convention.

• Suprema need no completeness axiom. The limit clause takes the union of a set of ordinals, which is an ordinal and is their least upper bound, by claim (e) of Basic closure properties of ordinals and the remark following it. Nothing resembling the least upper bound property of $\mathbb{R}$ is assumed; it is a closure property of the ordinals themselves.

• Left addition of a limit is a limit. For a limit $\lambda$, the values $\alpha +\beta$ for $\beta \in \lambda$ are strictly increasing and their supremum is not attained, so $\alpha +\lambda$ is again a limit ordinal. This is recorded as a clause of Monotonicity of ordinal $+$ and $\cdot$: strictly increasing and continuous in the right argument, weakly increasing in the left, with left cancellation, and the identities $0+\beta =\beta$ and $1\cdot \beta =\beta$, where it is proved.

Fix an ordinal $\alpha$ (Ordinal (von Neumann)). There is exactly one class function $\beta \mapsto {\mathrm{p}}_{\alpha }(\beta )$, defined at every ordinal $\beta$, satisfying the three clauses

${\mathrm{p}}_{\alpha }(0)=0,{\mathrm{p}}_{\alpha }({\beta }^{+})={\mathrm{p}}_{\alpha }(\beta )+\alpha ,{\mathrm{p}}_{\alpha }(\lambda )=\bigcup \{{\mathrm{p}}_{\alpha }(\beta ):\beta \in \lambda \}(\lambda \text{ a limit ordinal}),$

where $+$ is ordinal addition (Ordinal addition $\alpha +\beta$), and every value ${\mathrm{p}}_{\alpha }(\beta )$ is an ordinal.

The three clauses are exhaustive and mutually exclusive because every ordinal is exactly one of $0$, a successor, or a limit (Successor and limit ordinals). This is the well-definedness obligation discharged before ordinal multiplication is written down; the operation itself is named in the definition that follows. The proof is a theorem of ZF and uses no choice principle.

The successor clause adds $\alpha$ on the right. ${\mathrm{p}}_{\alpha }({\beta }^{+})={\mathrm{p}}_{\alpha }(\beta )+\alpha$, not $\alpha +{\mathrm{p}}_{\alpha }(\beta )$. Since ordinal addition is not commutative, this is a genuine choice of convention, and it is the one that makes $\alpha \cdot \beta$ come out as "$\beta$ copies of $\alpha$" rather than "$\alpha$ copies of $\beta$" ($\alpha \cdot \beta$ is the order type of $\alpha \times \beta$ ordered by last differences, that is $\beta$ copies of $\alpha$).

Nothing here uses a property of $+$. The proof needs only that $\mu +\alpha$ is an ordinal, which is the content of Ordinal addition exists and is unique: the clauses at $0$, at a successor and at a limit determine one operation, and its values are ordinals. Associativity, monotonicity and the rest are proved later and are not presupposed.

Let $\alpha$ and $\beta$ be ordinals (Ordinal (von Neumann)). The product $\alpha \cdot \beta$, also written $\alpha \beta$, is defined by recursion on $\beta$, in the three cases of Successor and limit ordinals:

$\alpha \cdot 0=0,\alpha \cdot {\beta }^{+}=\alpha \cdot \beta +\alpha ,\alpha \cdot \lambda =\bigcup \{\alpha \cdot \beta :\beta \in \lambda \}(\lambda \text{ a limit ordinal}),$

with $+$ the ordinal addition of Ordinal addition $\alpha +\beta$. That exactly one operation satisfies these three clauses, and that all its values are ordinals, is Ordinal multiplication exists and is unique, and its values are ordinals, proved immediately above. The union in the limit clause is the least upper bound of the values already produced (claim (e) of Basic closure properties of ordinals).

The convention, stated where it is made. The successor clause appends a copy of $\alpha$ on the right, so $\alpha \cdot \beta$ is "$\beta$ copies of $\alpha$", laid end to end in the order given by $\beta$. Made precise, this is $\alpha \cdot \beta$ is the order type of $\alpha \times \beta$ ordered by last differences, that is $\beta$ copies of $\alpha$: $\alpha \cdot \beta$ is the order type of $\alpha \times \beta$ ordered by last differences, that is, by comparing the $\beta$-coordinate first and using the $\alpha$-coordinate only to break a tie.

Both conventions occur in the literature and they give genuinely different operations, since multiplication is not commutative. Under the one adopted here $\omega \cdot 2=\omega +\omega$ while $2\cdot \omega =\omega$; under the opposite convention those two values are exchanged. This library always uses the convention above, which is the one of Jech and of the Wikipedia article cited below.

• Why $\alpha \cdot 0=0$ and not $1$. The empty concatenation of copies of $\alpha$ is empty. The multiplicative unit appears one clause later: $\alpha \cdot 1=\alpha \cdot 0^{+}=\alpha \cdot 0+\alpha =0+\alpha$, and $0+\alpha =\alpha$ is proved in Monotonicity of ordinal $+$ and $\cdot$: strictly increasing and continuous in the right argument, weakly increasing in the left, with left cancellation, and the identities $0+\beta =\beta$ and $1\cdot \beta =\beta$, so $\alpha \cdot 1=\alpha$.

• The limit clause is a supremum, and it is where the product loses commutativity. $2\cdot \omega =\sup \{2\cdot n:n\in \omega \}$, and each $2\cdot n$ is a finite ordinal, so the supremum is $\omega$; whereas $\omega \cdot 2=\omega \cdot 1+\omega =\omega +\omega$, which is strictly larger. Both computations are carried out in FALSE: ordinal multiplication is commutative.

• Notation. $\alpha \beta$ abbreviates $\alpha \cdot \beta$, and the product binds tighter than the sum, so $\alpha \beta +\gamma$ means $(\alpha \cdot \beta )+\gamma$. Ordinal expressions in this library are always written with that convention.

• Agreement with the natural numbers. Below $\omega$ the limit clause never fires, and the two remaining clauses are literally the Peano clauses for multiplication on $\mathbb{N}$. That the ordinal product of two natural numbers is their natural-number product is On $\omega$ the ordinal $+$ and $\cdot$ are the Peano operations: $\omega$ is closed under ordinal $+$, $\cdot$ and exponentiation, and for naturals $m,n$ the ordinal $m+n$ and $m\cdot n$ are the natural-number sum and product.

Fix an ordinal $\alpha$ (Ordinal (von Neumann)). There is exactly one class function $\beta \mapsto {\mathrm{e}}_{\alpha }(\beta )$, defined at every ordinal $\beta$, satisfying the three clauses

${\mathrm{e}}_{\alpha }(0)=1,{\mathrm{e}}_{\alpha }({\beta }^{+})={\mathrm{e}}_{\alpha }(\beta )\cdot \alpha ,{\mathrm{e}}_{\alpha }(\lambda )=\bigcup \{{\mathrm{e}}_{\alpha }(\beta ):\beta \in \lambda \text{ and }\beta \mathrm{\ne }0\}(\lambda \text{ a limit ordinal}),$

with $\cdot$ the ordinal multiplication of Ordinal multiplication $\alpha \cdot \beta$, and every value ${\mathrm{e}}_{\alpha }(\beta )$ is an ordinal.

The limit clause runs over $0<\beta <\lambda$, and that restriction is not cosmetic. With the unrestricted clause ${\mathrm{e}}_{\alpha }(\lambda )=\bigcup \{{\mathrm{e}}_{\alpha }(\beta ):\beta \in \lambda \}$ the value ${\mathrm{e}}_0(0)=1$ would be one of the sets united, so ${\mathrm{e}}_0(\omega )$ would come out $\ge 1$ and in fact equal to $1$, whereas $0$ raised to a limit must be $0$. With the restriction above the single formula is correct for every $\alpha$, including $\alpha =0$, and no case split on $\alpha$ is needed. For $\alpha \ge 1$ the restriction changes nothing, since then ${\mathrm{e}}_{\alpha }(0)=1\le \alpha ={\mathrm{e}}_{\alpha }(1)$ and $1\in \lambda$.

This is the well-definedness obligation discharged before ordinal exponentiation is written down; the operation itself is named in the definition that follows. The proof is a theorem of ZF and uses no choice principle.

The value at $\alpha =0$, worked out, and what the naive clause breaks. By the clauses, ${\mathrm{e}}_0(0)=1$ and ${\mathrm{e}}_0(1)={\mathrm{e}}_0(0)\cdot 0=1\cdot 0=0$, and then ${\mathrm{e}}_0(\beta )=0$ for every $\beta >0$; at a limit $\lambda$ the restricted union is $\bigcup \{0\}=0$, as it should be. Had the union run over all $\beta \in \lambda$ it would have contained ${\mathrm{e}}_0(0)=1$, giving ${\mathrm{e}}_0(\omega )=\bigcup \{1,0\}=1$. That is not merely unattractive: it falsifies the exponent law ${\alpha }^{\beta +\gamma }={\alpha }^{\beta }\cdot {\alpha }^{\gamma }$ of ${\alpha }^{\beta +\gamma }={\alpha }^{\beta }\cdot {\alpha }^{\gamma }$ and $({\alpha }^{\beta }{)}^{\gamma }={\alpha }^{\beta \cdot \gamma }$; and for $\alpha >1$ exponentiation is strictly increasing with $\beta \le {\alpha }^{\beta }$ at $\alpha =0$, $\beta =1$, $\gamma =\omega$, since $1+\omega =\omega$ makes the left side $0^{\omega }=1$ while the right side is $0^1\cdot 0^{\omega }=0\cdot 1=0$. Many texts avoid the issue by splitting the definition into a case $\alpha =0$ and a case $\alpha >0$; the restricted clause is the same definition without the split.

The convention $0^0=1$. The clause ${\mathrm{e}}_{\alpha }(0)=1$ applies to every $\alpha$, so $0^0=1$ here. This is the convention that makes the successor clause uniform, and it is the one used in Ordinal exponentiation ${\alpha }^{\beta }$, with the conventions ${\alpha }^0=1$ and $0^0=1$ and everywhere below.

This is ordinal, not cardinal, exponentiation. The two operations share the notation ${\alpha }^{\beta }$ and disagree already at $2^{\omega }$, which is $\omega$ here. Ordinal ${\alpha }^{\beta }$ and cardinal ${\kappa }^{\lambda }$ are different operations that share one notation sets out the difference; FALSE: the ordinal $2^{\omega }$ is uncountable computes the value.

Let $\alpha$ and $\beta$ be ordinals (Ordinal (von Neumann)). The power ${\alpha }^{\beta }$ is defined by recursion on $\beta$, in the three cases of Successor and limit ordinals:

${\alpha }^0=1,{\alpha }^{{\beta }^{+}}={\alpha }^{\beta }\cdot \alpha ,{\alpha }^{\lambda }=\bigcup \{{\alpha }^{\beta }:0<\beta <\lambda \}(\lambda \text{ a limit ordinal}),$

with $\cdot$ the ordinal multiplication of Ordinal multiplication $\alpha \cdot \beta$. That exactly one operation satisfies these three clauses, and that all its values are ordinals, is Ordinal exponentiation exists and is unique, with the limit clause taken over $0<\beta <\lambda$ so that $0^{\lambda }=0$, proved immediately above.

The first clause applies to every $\alpha$, so in particular $0^0=1$.

• The limit clause ranges over $0<\beta <\lambda$, not over $\beta <\lambda$, and the restriction is load bearing. The unrestricted union would include the value ${\alpha }^0=1$, and at $\alpha =0$ that single stray term flips the answer: it would make $0^{\omega }=1$ instead of $0$. With the restriction, one formula is correct for every $\alpha$ at once and no case split on $\alpha$ is needed. Ordinal exponentiation exists and is unique, with the limit clause taken over $0<\beta <\lambda$ so that $0^{\lambda }=0$ carries the details of that restriction; ${\alpha }^{\beta +\gamma }={\alpha }^{\beta }\cdot {\alpha }^{\gamma }$ and $({\alpha }^{\beta }{)}^{\gamma }={\alpha }^{\beta \cdot \gamma }$; and for $\alpha >1$ exponentiation is strictly increasing with $\beta \le {\alpha }^{\beta }$ proves the exponent law that the unrestricted clause would falsify. For $\alpha \ge 1$ the two clauses agree, because then ${\alpha }^0=1\le \alpha ={\alpha }^1$ and $1<\lambda$, so dropping the term at $\beta =0$ does not lower the supremum.

• ${\alpha }^1=\alpha$. Indeed ${\alpha }^1={\alpha }^{0^{+}}={\alpha }^0\cdot \alpha =1\cdot \alpha$, and $1\cdot \alpha =\alpha$ is proved in Monotonicity of ordinal $+$ and $\cdot$: strictly increasing and continuous in the right argument, weakly increasing in the left, with left cancellation, and the identities $0+\beta =\beta$ and $1\cdot \beta =\beta$.

• This is not cardinal exponentiation. The ordinal $2^{\omega }$ is $\omega$, computed in FALSE: the ordinal $2^{\omega }$ is uncountable; the cardinal power of $2$ by the size of $\mathbb{N}$ is the size of $\mathcal{P}(\mathbb{N})$, which is uncountable. The two operations share one notation and are not the same function. Ordinal ${\alpha }^{\beta }$ and cardinal ${\kappa }^{\lambda }$ are different operations that share one notation is the standing warning, and cardinal exponentiation is not defined at this point in the reading order; it is introduced later, on Cardinal Arithmetic, Cofinality and the Alephs.

• Notation and precedence. ${\alpha }^{\beta }\cdot \gamma$ means $({\alpha }^{\beta })\cdot \gamma$, and ${\alpha }^{\beta }+\gamma$ means $({\alpha }^{\beta })+\gamma$; powers bind tightest, then products, then sums. The Cantor normal form of Cantor normal form: every nonzero ordinal is ${\omega }^{{\beta }_0}\cdot c_0+\cdots +{\omega }^{{\beta }_{k-1}}\cdot c_{k-1}$ with ${\beta }_0>\cdots >{\beta }_{k-1}$ and each $c_i$ a nonzero natural number, in exactly one way is written with that convention throughout.

• The base is a parameter, the exponent is what the recursion runs on. As with Ordinal addition $\alpha +\beta$ and Ordinal multiplication $\alpha \cdot \beta$, the recursion is on the right argument, and the operation is correspondingly asymmetric: $\alpha \mapsto {\alpha }^{\beta }$ and $\beta \mapsto {\alpha }^{\beta }$ behave quite differently, and only the second is continuous at limits.

Let $(A,{<}_A)$ and $(B,{<}_B)$ be well-orders (Well-order and well-ordered set) with order types $\alpha =\mathrm{o}\mathrm{t}(A)$ and $\beta =\mathrm{o}\mathrm{t}(B)$ (Every well-order has a unique order type). Their ordered sum $A\oplus B$ is the set $(\{0\}\times A)\cup (\{1\}\times B)$ with

$(i,x)<(j,y):⟺i\in j,\text{ or }(i=j=0\text{ and }x{<}_{A}y),\text{ or }(i=j=1\text{ and }x{<}_{B}y),$

that is, a copy of $A$ with a copy of $B$ placed entirely above it. Then:

(a) $A\oplus B$ is a well-order and $\mathrm{o}\mathrm{t}(A\oplus B)=\alpha +\beta$ (Ordinal addition $\alpha +\beta$). In particular, taking $A=\alpha$ and $B=\beta$ with their membership orders, $\alpha +\beta$ is the order type of a copy of $\alpha$ followed by a copy of $\beta$.

(b) If $(W,<)$ is a well-order and $I\subseteq W$ is an initial segment (Initial segment of a well-order), then, with $I$ and $W\setminus I$ carrying the order inherited from $W$,

$\mathrm{o}\mathrm{t}(W)=\mathrm{o}\mathrm{t}(I)+\mathrm{o}\mathrm{t}(W\setminus I)\mathrm{.}$

No choice principle is used; the whole argument runs on Every well-order has a unique order type, which is itself choice free.