Set Theory

Ordinal Arithmetic

Reading preferences

Optional display controls need JavaScript. All reading content and navigation work without it.

Introduction

In chapter “Ordinals”, we developed a theory of ordinal numbers. We saw in chapter “Stages and Ranks” that we can think of the ordinals as a spine around which the remainder of the hierarchy is constructed. But that is not the only role for the ordinals. There is also the task of performing ordinal arithmetic.

We already gestured at this, back in section “The General Idea of an Ordinal” in chapter “Ordinals”, when we spoke of ω\omegasource, ω+1\omega+1source and ω+ω\omega+\omegasource. At the time, we spoke informally; the time has come to spell it out properly. However, we should mention that there is not much philosophy in this chapter; just technical developments, coupled with a (mildly) interesting observation that we can do the same thing in two different ways.

Ordinal Addition

Suppose we want to add α\alphasource and β\betasource. We can simply put a copy of β\betasource immediately after a copy of α\alphasource. (We need to take copies, since we know from proposition five in chapter “Ordinals” that either α⊆β\alpha \subseteq \betasource or β⊆α\beta \subseteq \alphasource.) The intuitive effect of this is to run through an α\alphasource-sequence of steps, and then to run through a β\betasource-sequence. The resulting sequence will be well-ordered; so by theorem five in chapter “Ordinals” it is isomorphic to a (unique) ordinal. That ordinal can be regarded as the sum of α\alphasource and β\betasource.

That is the intuitive idea behind ordinal addition. To define it rigorously, we start with the idea of taking copies of sets. The idea here is to use arbitrary tags, 00source and 11source, to keep track of which object came from where:

Definition one in this chapter

The disjoint sum of AAsource and BBsource is A⊔B=(A×{0})∪(B×{1})A \disjointsum B = (A\times \{0\}) \cup (B \times \{1\})source.

We next define an ordering on pairs of ordinals:

Definition two in this chapter

For any ordinals α1,α2,β1,β2\alpha_1, \alpha_2, \beta_1, \beta_2source, say that:

⟨α1,α2⟩∢⟨β1,β2⟩ iff either α2∈β2or both α2=β2 and α1∈β1\tuple{\alpha_1, \alpha_2} \rlexless \tuple{\beta_1, \beta_2}\text{ iff }& \text{either $\alpha_2 \in \beta_2$}\\ & \text{or both $\alpha_2 = \beta_2$ and $\alpha_1 \in \beta_1$}source

This is a reverse lexicographic ordering, since you order by the second element, then by the first. Now recall that we wanted to define α+β\alpha \ordplus \betasource as the order type of a copy of α\alphasource followed by a copy of β\betasource. To achieve that, we say:

Definition three in this chapter

For any ordinals α\alphasource, β\betasource, their sum is α+β=ord(α⊔β,∢)\alpha \ordplus \beta = \ordtype{\alpha \disjointsum \beta, \rlexless}source.

noindent Note that we slightly abused notation here; strictly we should write “{⟨x,y⟩∈α⊔β:x∢y}\Setabs{\tuple{x,y}\in \alpha\disjointsum\beta}{x \rlexless y}source” in place of “∢\rlexlesssource”. For brevity, though, we will continue to abuse notation in this way in what follows.

The following result, together with theorem five in chapter “Ordinals”, confirms that our definition is well-formed:

Lemma one in this chapter

⟨α⊔β,∢⟩\tuple{\alpha \disjointsum \beta, \rlexless}source is a well-order, for any ordinals α\alphasource and β\betasource.

Proof

Obviously ∢\rlexlesssource is connected on α⊔β\alpha \disjointsum \betasource. To show it is well-founded, fix a non-empty X⊆α⊔βX \subseteq \alpha \disjointsum \betasource. Let YYsource be the subset of XXsource whose second coordinate is as small as possible, i.e.\ Y={⟨γ,i⟩∈X:(∀⟨δ,j⟩∈X)i≤j}Y = \Setabs{\tuple{\gamma, i} \in X}{(\forall \tuple{\delta, j} \in X)i \leq j}source. Now choose the element of YYsource with smallest first coordinate.

noindent So we have a nice, explicit definition of ordinal addition. Here is an unsurprising fact (recall that 1={0}1 = \{0\}source, by definition of the natural numbers and omega in chapter “Steps towards Z”):

Proposition one in this chapter

α+1=α+\alpha \ordplus 1 = \ordsucc{\alpha}source, for any ordinal α\alphasource.

Proof

Consider the isomorphism ffsource from α+=α∪{α}\ordsucc{\alpha} = \alpha \cup \{\alpha\}source to α⊔1=(α×{0})⊔({0}×{1})\alpha\disjointsum1 = (\alpha \times \{0\}) \disjointsum (\{0\} \times \{1\})source given by f(γ)=⟨γ,0⟩f(\gamma) = \tuple{\gamma, 0}source for γ∈α\gamma \in \alphasource, and f(α)=⟨0,1⟩f(\alpha) = \tuple{0, 1}source.

noindent Moreover, it is easy to show that addition obeys certain recursive conditions:

Lemma two in this chapter

For any ordinals α,β\alpha, \betasource, we have:

α+0=αα+(β+1)=(α+β)+1α+β=lsubδ<β(α+δ)if β is a limit ordinal\alpha\ordplus 0 &= \alpha\\ \alpha \ordplus (\beta\ordplus 1) &= (\alpha \ordplus \beta) \ordplus 1\\ \alpha \ordplus \beta &= \supstrict_{\delta < \beta}(\alpha \ordplus \delta) && \text{if $\beta $ is a limit ordinal}source

Proof

We check case-by-case; first:

α+0=ord((α×{0})∪(0×{1}),∢)=ord((α×{0})∪{0},∢)=αα+(β+1)=ord((α×{0})∪(β+×{1}),∢)=ord((α×{0})∪(β×{1}),∢)+1=(α+β)+1\alpha \ordplus 0 & = \ordtype{(\alpha \times \{0\}) \cup (0 \times \{1\}), \rlexless} \\ &= \ordtype{(\alpha \times \{0\}) \cup \{0\}, \rlexless}\\ &= \alpha\\ \alpha \ordplus (\beta \ordplus 1) &= \ordtype{(\alpha\times \{0\}) \cup (\ordsucc{\beta}\times \{1\}), \rlexless} \\ &= \ordtype{(\alpha\times \{0\}) \cup (\beta \times \{1\}), \rlexless} \ordplus 1\\ &= (\alpha \ordplus \beta) \ordplus 1source

Now let β≠∅\beta \neq \emptysetsource be a limit. If δ<β\delta < \betasource then also δ+1<β\delta\ordplus 1 < \betasource, so α+δ\alpha \ordplus \deltasource is a proper initial segment of α+β\alpha \ordplus \betasource. So α+β\alpha \ordplus \betasource is a strict upper bound on X={α+δ:δ<β}X = \Setabs{\alpha \ordplus \delta}{\delta < \beta}source. Moreover, if α≤γ<α+β\alpha \leq \gamma < \alpha \ordplus \betasource, then clearly γ=α+δ\gamma = \alpha \ordplus \deltasource for some δ<β\delta < \betasource. So α+β=lsubδ<β(α+δ)\alpha \ordplus \beta = \supstrict_{\delta< \beta}(\alpha\ordplus \delta)source.

But here is a striking fact. To define ordinal addition, we could instead have simply used the Transfinite Recursion Theorem, and laid down the recursion equations, exactly as given in lemma two in chapter “Ordinal Arithmetic” (though using “β+\ordsucc{\beta}source” rather than “β+1\beta \ordplus 1source”).

There are, then, two different ways to define operations on the ordinals. We can define them synthetically, by explicitly constructing a well-ordered set and considering its order type. Or we can define them recursively, just by laying down the recursion equations. Done correctly, though, the outcome is identical. For theorem five in chapter “Ordinals” guarantees that these recursion equations pin down unique ordinals.

In many ways, ordinal arithmetic behaves just like addition of the natural numbers. For example, we can prove the following:

Lemma three in this chapter

If α,β,γ\alpha, \beta, \gammasource are ordinals, then:

  1. if β<γ\beta < \gammasource, then α+β<α+γ\alpha \ordplus \beta < \alpha \ordplus \gammasource

  2. if α+β=α+γ\alpha \ordplus \beta = \alpha\ordplus \gammasource, then β=γ\beta = \gammasource

  3. α+(β+γ)=(α+β)+γ\alpha \ordplus (\beta \ordplus \gamma) = (\alpha \ordplus \beta) \ordplus \gammasource, i.e., addition is associative

  4. If α≤β\alpha \leq \betasource, then α+γ≤β+γ\alpha \ordplus \gamma \leq \beta \ordplus \gammasource

Proof

We prove item 3 of lemma three in chapter “Ordinal Arithmetic”, leaving the rest as an exercise. The proof is by Simple Transfinite Induction on γ\gammasource, using lemma two in chapter “Ordinal Arithmetic”. When γ=0\gamma = 0source:

(α+β)+0=α+β=α+(β+0)(\alpha \ordplus \beta) \ordplus 0 = \alpha \ordplus \beta = \alpha \ordplus (\beta \ordplus 0)source

When γ=δ+1\gamma = \delta\ordplus 1source, suppose for induction that (α+β)+δ=α+(β+δ)(\alpha \ordplus \beta) \ordplus \delta = \alpha \ordplus (\beta \ordplus \delta)source; now using lemma two in chapter “Ordinal Arithmetic” three times:

(α+β)+(δ+1)=((α+β)+δ)+1=(α+(β+δ))+1=α+((β+δ)+1)=α+(β+(δ+1))(\alpha \ordplus \beta) \ordplus (\delta \ordplus 1) & = ((\alpha \ordplus \beta) \ordplus \delta)\ordplus 1\\ & = (\alpha \ordplus (\beta \ordplus \delta)) \ordplus 1\\ & = \alpha \ordplus ((\beta \ordplus \delta)\ordplus 1)\\ & = \alpha \ordplus (\beta \ordplus (\delta\ordplus 1))source

When γ\gammasource is a limit ordinal, suppose for induction that if δ∈γ\delta \in \gammasource then (α+β)+δ=α+(β+δ)(\alpha \ordplus \beta) \ordplus \delta = \alpha \ordplus (\beta \ordplus \delta)source; now:

(α+β)+γ=lsubδ<γ((α+β)+δ)=lsubδ<γ(α+(β+δ))=α+lsubδ<γ(β+δ)=α+(β+γ)(\alpha \ordplus \beta) \ordplus \gamma & = \supstrict_{\delta < \gamma}((\alpha \ordplus \beta) \ordplus \delta) \\ &= \supstrict_{\delta < \gamma}(\alpha \ordplus (\beta \ordplus \delta))\\ &= \alpha \ordplus \supstrict_{\delta < \gamma}(\beta \ordplus \delta)\\ & = \alpha \ordplus (\beta \ordplus \gamma)source

Exercise one in this chapter

Prove the remainder of lemma three in chapter “Ordinal Arithmetic”.

In these ways, ordinal addition should be very familiar. But, there is a crucial way in which ordinal addition is not like addition on the natural numbers.

Proposition two in this chapter

Ordinal addition is not commutative; 1+ω=ω<ω+11 \ordplus \omega = \omega < \omega \ordplus 1source.

Proof

Note that 1+ω=lsubn<ω(1+n)=ω∈ω∪{ω}=ω+=ω+11 \ordplus \omega = \supstrict_{n < \omega} (1 \ordplus n) = \omega \in \omega \cup \{\omega\} = \ordsucc{\omega} = \omega \ordplus 1source.

noindent Whilst this may initially come as a surprise, it shouldn't. On the one hand, when you consider 1+ω1 \ordplus \omegasource, you are thinking about the order type you get by putting an extra element before all the natural numbers. Reasoning as we did with Hilbert's Hotel in section “Hilbert's Hotel” in chapter “Infinite Sets”, intuitively, this extra first element shouldn't make any difference to the overall order type. On the other hand, when you consider ω+1\omega \ordplus 1source, you are thinking about the order type you get by putting an extra element after all the natural numbers. And that's a radically different beast!

Using Ordinal Addition

Using addition on the ordinals, we can explicitly calculate the ranks of various sets, in the sense of definition seven in chapter “Stages and Ranks”:

Lemma four in this chapter

If rank(A)=α\setrank{A} = \alphasource and rank(B)=β\setrank{B} = \betasource, then:

  1. rank(℘(A))=α+1\setrank{\Pow{A}} = \alpha\ordplus 1source

  2. rank({A,B})=max(α,β)+1\setrank{\{A, B\}} = \max(\alpha, \beta) \ordplus 1source

  3. rank(A∪B)=max(α,β)\setrank{A \cup B} = \max(\alpha, \beta)source

  4. rank(⟨A,B⟩)=max(α,β)+2\setrank{\tuple{A,B}} = \max(\alpha, \beta) \ordplus 2source

  5. rank(A×B)≤max(α,β)+2\setrank{A \times B} \leq \max(\alpha, \beta) \ordplus 2source

  6. rank(⋃A)=α\setrank{\bigcup A} = \alphasource when α\alphasource is empty or a limit; rank(⋃A)=γ\setrank{\bigcup A} = \gammasource when α=γ+1\alpha = \gamma\ordplus 1source

Proof

Throughout, we invoke proposition five in chapter “Stages and Ranks” repeatedly.

item 1 of lemma four in chapter “Ordinal Arithmetic”. If x⊆Ax \subseteq Asource then rank(x)≤rank(A)\setrank{x} \leq \setrank{A}source. So rank(℘(A))≤α+1\setrank{\Pow{A}} \leq \alpha \ordplus 1source. Since A∈℘(A)A \in \Pow{A}source in particular, rank(℘(A))=α+1\setrank{\Pow{A}} = \alpha \ordplus 1source.

item 2 of lemma four in chapter “Ordinal Arithmetic”. By proposition five in chapter “Stages and Ranks”

item 3 of lemma four in chapter “Ordinal Arithmetic”. By proposition five in chapter “Stages and Ranks”.

item 4 of lemma four in chapter “Ordinal Arithmetic”. By item 2 of lemma four in chapter “Ordinal Arithmetic”, twice.

item 5 of lemma four in chapter “Ordinal Arithmetic”. Note that A×B⊆℘(℘(A∪B))A \times B \subseteq \Pow{\Pow{A \cup B}}source, and invoke item 4 of lemma four in chapter “Ordinal Arithmetic”.

item 6 of lemma four in chapter “Ordinal Arithmetic”. If α=γ+1\alpha = \gamma\ordplus 1source, there is some c∈Ac \in Asource with rank(c)=γ\setrank{c} = \gammasource, and no element of AAsource has higher rank; so rank(⋃A)=γ\setrank{\bigcup A} = \gammasource. If α\alphasource is a limit ordinal, then AAsource has elements with rank arbitrarily close to (but strictly less than) α\alphasource, so that ⋃A\bigcup Asource also has elements with rank arbitrarily close to (but strictly less than) α\alphasource, so that rank(⋃A)=α\setrank{\bigcup A} = \alphasource.

noindent We leave it as an exercise to show why item 5 of lemma four in chapter “Ordinal Arithmetic” involves an inequality.

Exercise two in this chapter

Produce sets AAsource and BBsource such that rank(A×B)=max(rank(A),rank(B))\setrank{A \times B}= \max(\setrank{A}, \setrank{B})source. Produce sets AAsource and BBsource such that rank(A×B)max(rank(A),rank(B))+2\setrank{A \times B}\max(\setrank{A}, \setrank{B}) \ordplus 2source. Are any other ranks possible?

We are also now in a position to show that several reasonable notions of what it might mean to describe an ordinal as “finite” or “infinite” coincide:

Lemma five in this chapter

For any ordinal α\alphasource, the following are equivalent:

  1. α∉ω\alpha\notin \omegasource, i.e., α\alphasource is not a natural number

  2. ω≤α\omega \leq \alphasource

  3. 1+α=α1 \ordplus \alpha = \alphasource

  4. α≈α+1\alpha \approx \alpha\ordplus 1source, i.e., α\alphasource and α+1\alpha\ordplus 1source are equinumerous

  5. α\alphasource is Dedekind infinite

noindent So we have five provably equivalent ways to understand what it takes for an ordinal to be (in)finite.

Proof

item 1 of lemma five in chapter “Ordinal Arithmetic” ⇒\Rightarrowsource item 2 of lemma five in chapter “Ordinal Arithmetic”. By Trichotomy.

item 2 of lemma five in chapter “Ordinal Arithmetic” ⇒\Rightarrowsource item 3 of lemma five in chapter “Ordinal Arithmetic”. Fix α≥ω\alpha \geq \omegasource. By Transfinite Induction, there is some least ordinal γ\gammasource (possibly 00source) such that there is a limit ordinal β\betasource with α=β+γ\alpha = \beta \ordplus \gammasource. Now:

1+α=1+(β+γ)=(1+β)+γ=lsubδ<β(1+δ)+γ=β+γ=α.1 \ordplus \alpha = 1 \ordplus (\beta \ordplus \gamma) = (1 \ordplus \beta) \ordplus \gamma = \supstrict_{\delta < \beta} (1 \ordplus \delta) \ordplus \gamma = \beta \ordplus \gamma = \alpha.source

item 3 of lemma five in chapter “Ordinal Arithmetic” ⇒\Rightarrowsource item 4 of lemma five in chapter “Ordinal Arithmetic”. There is clearly a bijection f:(α⊔1)→(1⊔α)f \colon (\alpha \disjointsum 1) \to (1 \disjointsum \alpha)source. If 1+α=α1 \ordplus \alpha = \alphasource, there is an isomorphism g:(1⊔α)→αg \colon (1 \disjointsum \alpha) \to \alphasource. Now consider g∘f\comp{f}{g}source.

item 4 of lemma five in chapter “Ordinal Arithmetic” ⇒\Rightarrowsource item 5 of lemma five in chapter “Ordinal Arithmetic”. If α≈α+1\alpha \approx \alpha \ordplus 1source, there is a bijection f:(α⊔1)→αf \colon (\alpha \disjointsum 1) \to \alphasource. Define g(γ)=f(γ,0)g(\gamma) = f(\gamma, 0)source for each γ<α\gamma < \alphasource; this injection witnesses that α\alphasource is Dedekind infinite, since f(0,1)∈α∖ran(g)f(0,1) \in \alpha \setminus \ran{g}source.

item 5 of lemma five in chapter “Ordinal Arithmetic” ⇒\Rightarrowsource item 1 of lemma five in chapter “Ordinal Arithmetic”. This is proposition that natural numbers are not Dedekind infinite in chapter “Steps towards Z”.

Ordinal Multiplication

We now turn to ordinal multiplication, and we approach this much like ordinal addition. So, suppose we want to multiply α\alphasource by β\betasource. To do this, you might imagine a rectangular grid, with width α\alphasource and height β\betasource; the product of α\alphasource and β\betasource is now the result of moving along each row, then moving through the next rowldots until you have moved through the entire grid. Otherwise put, the product of α\alphasource and β\betasource arises by replacing each element in β\betasource with a copy of α\alphasource.

To make this formal, we simply use the reverse lexicographic ordering on the Cartesian product of α\alphasource and β\betasource:

Definition four in this chapter

For any ordinals α,β\alpha, \betasource, their product α·β=ord(α×β,∢)\alpha \ordtimes \beta = \ordtype{\alpha \times \beta, \rlexless}source.

noindent We must again confirm that this is a well-formed definition:

Lemma six in this chapter

⟨α×β,∢⟩\tuple{\alpha \times \beta, \rlexless}source is a well-order, for any ordinals α\alphasource and β\betasource.

Proof

Exactly as for lemma one in chapter “Ordinal Arithmetic”.

noindent And it is not hard to prove that multiplication behaves thus:

Lemma seven in this chapter

For any ordinals α,β\alpha, \betasource:

α·0=0α·(β+1)=(α·β)+αα·β=lsubδ<β(α·δ)when β is a limit ordinal.\alpha \ordtimes 0 &= 0\\ \alpha \ordtimes (\beta \ordplus 1) &= (\alpha \ordtimes \beta) \ordplus \alpha\\ \alpha \ordtimes \beta &= \supstrict_{\delta < \beta}(\alpha \ordtimes \delta) && \text{when $\beta$ is a limit ordinal}.source

Proof

Left as an exercise.

Indeed, just as in the case of addition, we could have defined ordinal multiplication via these recursion equations, rather than offering a direct definition. Equally, as with addition, certain behaviour is familiar:

Lemma eight in this chapter

If α,β,γ\alpha, \beta, \gammasource are ordinals, then:

  1. if α≠0\alpha \neq 0source and β<γ\beta < \gammasource, then α·β<α·γ\alpha \ordtimes \beta < \alpha \ordtimes \gammasource;

  2. if α≠0\alpha \neq 0source and α·β=α·γ\alpha \ordtimes \beta = \alpha\ordtimes\gammasource, then β=γ\beta = \gammasource;

  3. α·(β·γ)=(α·β)·γ\alpha \ordtimes (\beta \ordtimes \gamma) = (\alpha \ordtimes \beta) \ordtimes \gammasource;

  4. If α≤β\alpha \leq \betasource, then α·γ≤β·γ\alpha \ordtimes \gamma \leq \beta \ordtimes \gammasource;

  5. α·(β+γ)=(α·β)+(α·γ)\alpha \ordtimes (\beta \ordplus \gamma) = (\alpha \ordtimes \beta )\ordplus (\alpha\ordtimes \gamma)source.

Proof

Left as an exercise.

You can prove (or look up) other results, to your heart's content. But, given proposition two in chapter “Ordinal Arithmetic”, the following should not come as a surprise:

Proposition three in this chapter

Ordinal multiplication is not commutative: 2·ω=ω<ω·22 \ordtimes \omega = \omega < \omega \ordtimes 2source

Proof

2·ω=lsubn<ω(2·n)=ω∈lsubn<ω(ω+n)=ω+ω=ω·22 \ordtimes \omega = \supstrict_{n < \omega}(2\ordtimes n) = \omega \in \supstrict_{n < \omega}(\omega \ordplus n) = \omega \ordplus \omega = \omega \ordtimes 2source.

noindent Again, the intuitive rationale is quite straightforward. To compute 2·ω2 \ordtimes \omegasource, you replace each natural number with two entities. You would get the same order type if you simply inserted all the “half” numbers into the natural numbers, i.e., you considered the natural ordering on {n2:n∈ω}\Setabs{\nicefrac{n}{2}}{n \in \omega}source. And, put like that, the order type is plainly the same as that of ω\omegasource itself. But, to compute ω·2\omega \ordtimes 2source, you place down two copies of ω\omegasource, one after the other.

Exercise three in this chapter

Prove lemma six in chapter “Ordinal Arithmetic”, lemma seven in chapter “Ordinal Arithmetic”, and lemma eight in chapter “Ordinal Arithmetic”

Ordinal Exponentiation

We now move to ordinal exponentiation. Sadly, there is no nice synthetic definition for ordinal exponentiation.

Sure, there are explicit synthetic definitions. Here is one. Let finfun(α,β)\text{finfun}(\alpha,\beta)source be the set of all functions f:α→βf \colon \alpha \to \betasource such that {γ∈α:f(γ)≠0}\Setabs{\gamma \in \alpha}{f(\gamma) \neq 0}source is equinumerous with some natural number. Define a well-ordering on finfun(α,β)\text{finfun}(\alpha,\beta)source by f⊏gf \sqsubset gsource iff f≠gf \neq gsource and f(γ0)<g(γ0)f(\gamma_0) < g(\gamma_0)source, where γ0=max{γ∈α:f(γ)≠g(γ)}\gamma_0 = \text{max}\Setabs{\gamma \in \alpha}{f(\gamma) \neq g(\gamma)}source. Then we can define α(β)\ordexpo{\alpha}{\beta}source as ord(finfun(α,β),⊏)\ordtype{\text{finfun}(\alpha, \beta), \sqsubset}source. Potter employs this explicit definition, and then immediately explains:

The choice of this ordering is determined purely by our desire to obtain a definition of ordinal exponentiation which obeys the appropriate recursive conditionldots, and it is much harder to picture than either the ordered sum or the ordered product. (Michael Potter, 2004, p. 199)

Quite. We explained addition as “a copy of α\alphasource followed by a copy of β\betasource”, and multiplication as “a β\betasource-sequence of copies of α\alphasource”. But we have nothing pithy to say about finfun(α,γ)\text{finfun}(\alpha, \gamma)source. So instead, we'll offer the definition of ordinal exponentiation just by transfinite recursion, i.e.:

Definition five in this chapter

α(0)=1α(β+1)=α(β)·αα(β)=⋃δ<βα(δ)when β is a limit ordinal\ordexpo{\alpha}{0} &= 1\\ \ordexpo{\alpha}{\beta\ordplus 1} &=\ordexpo{\alpha}{\beta} \ordtimes \alpha\\ \ordexpo{\alpha}{\beta} &= \bigcup_{\delta < \beta}\ordexpo{\alpha}{\delta}& & \text{when $\beta$ is a limit ordinal}source

If we were working as set theorists, we might want to explore some of the properties of ordinal exponentiation. But we have nothing much more to add, except to note the unsurprising fact that ordinal exponentiation does not commute. Thus 2(ω)=⋃δ<ω2(δ)=ω\ordexpo{2}{\omega} = \bigcup_{\delta < \omega}\ordexpo{2}{\delta} = \omegasource, whereas ω(2)=ω·ω\ordexpo{\omega}{2} = \omega \ordtimes \omegasource. But then, we should not expect exponentiation to commute, since it does not commute with natural numbers: 2(3)=8<9=3(2)\ordexpo{2}{3} = 8 < 9 = \ordexpo{3}{2}source.

Exercise four in this chapter

Using Transfinite Induction, prove that, if we define α(β)=ord(finfun(α,β),⊏)\ordexpo{\alpha}{\beta} = \ordtype{\text{finfun}(\alpha, \beta), \sqsubset}source, we obtain the recursion equations of definition five in chapter “Ordinal Arithmetic”.