Set Theory

Ordinal Arithmetic

content/set-theory/ord-arithmetic/ord-arithmetic.tex

% Part: set-theory% Chapter: ord-arithmetic\documentclass[../../../include/open-logic-chapter]{subfiles}\begin{document}\olchapter{sth}{ord-arithmetic}{Ordinal Arithmetic}\olimport{introduction}\olimport{addition}\olimport{using-addition}\olimport{multiplication}\olimport{exponentiation}\OLEndChapterHook\end{document}

content/set-theory/ord-arithmetic/introduction.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{ord-arithmetic}{intro}\olsection{Introduction}In \olref[ordinals][]{chap}, we developed a theory of ordinal numbers.We saw in \olref[spine][]{chap} that we can think of the ordinals as aspine around which the remainder of the hierarchy is constructed. Butthat is not the only role for the ordinals. There is also the task ofperforming ordinal arithmetic. We already gestured at this, back in\olref[ordinals][idea]{sec}, when we spoke of $\omega$,$\omega+1$ and $\omega+\omega$. At the time, we spoke informally; thetime has come to spell it out properly. However, we should mentionthat there is not much philosophy in this chapter; just technicaldevelopments, coupled with a (mildly) interesting observation that wecan do the same thing in two different ways.\end{document}

content/set-theory/ord-arithmetic/addition.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{ord-arithmetic}{add}\olsection{Ordinal Addition}Suppose we want to add $\alpha$ and $\beta$. We can simply put a{copy} of $\beta$ immediately after a copy of $\alpha$. (We need totake \emph{copies}, since we know from\olref[ordinals][basic]{ordinalsaresubsets} that either $\alpha\subseteq \beta$ or $\beta \subseteq \alpha$.) The intuitive effect ofthis is to run through an $\alpha$-sequence of steps, \emph{and then}to run through a $\beta$-sequence. The resulting sequence will bewell-ordered; so by\olref[ordinals][ordtype]{thmOrdinalRepresentation} it is isomorphicto a (unique) ordinal. That ordinal can be regarded as the \emph{sum}of $\alpha$ and $\beta$. That is the intuitive idea behind ordinal addition. To define itrigorously, we start with the idea of taking \emph{copies} of sets.The idea here is to use arbitrary tags, $0$ and $1$, to keep track ofwhich object came from where:\begin{defn}\ollabel{defdissum}The \emph{disjoint sum} of $A$ and $B$ is $A \disjointsum B = (A\times\{0\}) \cup (B \times \{1\})$.\end{defn}We next define an ordering on pairs of ordinals:\begin{defn}For any ordinals $\alpha_1, \alpha_2, \beta_1, \beta_2$, say that:\begin{align*}	\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$}\end{align*} \end{defn}This is a \emph{reverse lexicographic} ordering, since you order bythe second element, then by the first. Now recall that we wanted todefine $\alpha \ordplus \beta$ as the order type of a copy of $\alpha$followed by a copy of $\beta$. To achieve that, we say:\begin{defn}\ollabel{defordplus}For any ordinals $\alpha$, $\beta$, their sum is $\alpha \ordplus\beta = \ordtype{\alpha \disjointsum \beta, \rlexless}$.\end{defn}\noindentNote that we slightly abused notation here; strictly we should write ``$\Setabs{\tuple{x,y}\in \alpha\disjointsum\beta}{x \rlexless y}$'' in place of ``$\rlexless$''. For brevity, though, we will continue to abuse notation in this way in what follows. The following result, together with\olref[ordinals][ordtype]{thmOrdinalRepresentation}, confirms that ourdefinition is well-formed:\begin{lem}\ollabel{ordsumlessiswo} $\tuple{\alpha \disjointsum \beta, \rlexless}$ is a well-order, forany ordinals $\alpha$ and $\beta$.\end{lem}\begin{proof}Obviously $\rlexless$ is connected on $\alpha \disjointsum \beta$. Toshow it is well-founded, fix a non-empty $X \subseteq \alpha\disjointsum \beta$. Let $Y$ be the subset of $X$ whose second coordinate is as small as possible, i.e.\ $Y = \Setabs{\tuple{\gamma, i} \in X}{(\forall \tuple{\delta, j} \in X)i \leq j}$. Now choose the element of $Y$ with smallest first coordinate. \end{proof}\noindent So we have a nice, explicit definition of ordinal addition. Here isan unsurprising fact (recall that  $1 = \{0\}$, by\olref[z][infinity-again]{defnomega}):\begin{prop}$\alpha \ordplus  1 = \ordsucc{\alpha}$, for any ordinal $\alpha$.\end{prop}\begin{proof}Consider the isomorphism $f$ from $\ordsucc{\alpha} = \alpha \cup\{\alpha\}$ to $\alpha\disjointsum1 = (\alpha \times \{0\})\disjointsum (\{0\} \times \{1\})$ given by $f(\gamma) =\tuple{\gamma, 0}$ for $\gamma \in \alpha$, and $f(\alpha) = \tuple{0,1}$.\end{proof}\noindentMoreover, it is easy to show that addition obeys certain recursiveconditions:\begin{lem}\ollabel{ordadditionrecursion}For any ordinals $\alpha, \beta$, we have:\begin{align*}	\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}\end{align*}\end{lem}\begin{proof}We check case-by-case; first:\begin{align*}	\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 (\ordtype{\beta \ordplus  1}\times \{1\}), \rlexless} \\	&= \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  1\end{align*}Now let $\beta \neq \emptyset$ be a limit. If $\delta < \beta$ thenalso $\delta\ordplus 1 < \beta$, so $\alpha \ordplus  \delta$ is aproper initial segment of $\alpha \ordplus  \beta$. So $\alpha\ordplus  \beta$ is a strict upper bound on $X = \Setabs{\alpha\ordplus  \delta}{\delta < \beta}$. Moreover, if $\alpha \leq \gamma <\alpha \ordplus  \beta$, then clearly $\gamma = \alpha \ordplus\delta$ for some $\delta < \beta$. So $\alpha \ordplus  \beta =\supstrict_{\delta< \beta}(\alpha\ordplus \delta)$.\end{proof}But here is a striking fact. To define ordinal addition, we could\emph{instead} have simply used the Transfinite Recursion Theorem, andlaid down the recursion equations, exactly as given in\olref{ordadditionrecursion} (though using ``$\ordsucc{\beta}$''rather than ``$\beta \ordplus 1$'').There are, then, two different ways to define operations on theordinals. We can define them \emph{synthetically}, by explicitlyconstructing a well-ordered set and considering its order type. Or wecan define them \emph{recursively}, just by laying down the recursionequations. Done correctly, though, the outcome is identical. For\olref[ordinals][ordtype]{thmOrdinalRepresentation} guaranteesthat these recursion equations pin down \emph{unique} ordinals.In many ways, ordinal arithmetic behaves just like addition of thenatural numbers. For example, we can prove the following:\begin{lem}\ollabel{ordinaladditionisnice}If $\alpha, \beta, \gamma$ are ordinals, then:\begin{enumerate}	\item\ollabel{ordaddition1} if $\beta < \gamma$, then $\alpha	\ordplus  \beta < \alpha \ordplus  \gamma$	\item\ollabel{ordaddition2} if $\alpha \ordplus  \beta =	\alpha\ordplus \gamma$, then $\beta = \gamma$	\item\ollabel{ordaddition3}  $\alpha \ordplus  (\beta \ordplus	\gamma) = (\alpha \ordplus  \beta) \ordplus  \gamma$, i.e.,	addition is associative	\item\ollabel{ordaddition4}  If $\alpha \leq \beta$, then $\alpha	\ordplus  \gamma \leq \beta \ordplus \gamma$\end{enumerate}\end{lem}\begin{proof}We prove \olref{ordaddition3}, leaving the rest as an exercise. Theproof is by Simple Transfinite Induction on $\gamma$, using\olref{ordadditionrecursion}. When $\gamma = 0$:\[(\alpha \ordplus  \beta) \ordplus  0 = \alpha \ordplus  \beta  = \alpha \ordplus  (\beta \ordplus  0)\]When $\gamma = \delta\ordplus 1$, suppose for induction that $(\alpha\ordplus  \beta) \ordplus  \delta = \alpha \ordplus  (\beta \ordplus\delta)$; now using \olref{ordadditionrecursion} three times:\begin{align*}	(\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))\end{align*}	When $\gamma$ is a limit ordinal, suppose for induction that if$\delta \in \gamma$ then $(\alpha \ordplus  \beta) \ordplus  \delta =\alpha \ordplus  (\beta \ordplus  \delta)$; now:\begin{align*}	(\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)\end{align*}\end{proof}\begin{prob}Prove the remainder of\olref[sth][ord-arithmetic][add]{ordinaladditionisnice}.\end{prob}In these ways, ordinal addition should be very familiar. But, there is a crucial way in which ordinal addition is \emph{not} like addition on the natural numbers.\begin{prop}\ollabel{ordsumnotcommute}Ordinal addition is {not} commutative; $1 \ordplus  \omega = \omega <\omega \ordplus  1$.\end{prop}\begin{proof}Note that $1 \ordplus  \omega = \supstrict_{n < \omega} (1 \ordplus n)= \omega \in \omega \cup \{\omega\} = \ordsucc{\omega} = \omega\ordplus  1$.\end{proof}\noindent Whilst this may initially come as a surprise, \emph{it shouldn't}. Onthe one hand, when you consider $1 \ordplus  \omega$, you are thinkingabout the order type you get by putting an extra element \emph{before}all the natural numbers. Reasoning as we did with Hilbert's Hotel in\olref[sfr][infinite][hilbert]{sec}, intuitively, this extra firstelement shouldn't make any difference to the overall order type. Onthe other hand, when you consider $\omega \ordplus  1$, you arethinking about the order type you get by putting an extra element\emph{after} all the natural numbers. And that's a radically differentbeast!\end{document}

content/set-theory/ord-arithmetic/using-addition.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{ord-arithmetic}{using-addition}\olsection{Using Ordinal Addition}Using addition on the ordinals, we can explicitly calculate the ranksof various sets, in the sense of \olref[spine][rank]{defnsetrank}:\begin{lem}\ollabel{rankcomputation}If $\setrank{A} = \alpha$ and $\setrank{B} = \beta$, then:\begin{enumerate}	\item\ollabel{exrankpow} $\setrank{\Pow{A}} = \alpha\ordplus 1$	\item\ollabel{exrankpair} $\setrank{\{A, B\}} = \max(\alpha,	\beta) \ordplus 1$	\item\ollabel{exrankcup} $\setrank{A \cup B} = \max(\alpha,	\beta)$	\item\ollabel{exranktuple} $\setrank{\tuple{A,B}} = \max(\alpha,	\beta) \ordplus  2$	\item\ollabel{exranktimes} $\setrank{A \times B} \leq \max(\alpha,	\beta) \ordplus  2$	\item\ollabel{exrankunion} $\setrank{\bigcup A} = \alpha$ when	$\alpha$ is empty or a limit; $\setrank{\bigcup A} = \gamma$ when	$\alpha = \gamma\ordplus 1$\end{enumerate}\end{lem}\begin{proof}Throughout, we invoke \olref[spine][rank]{ranksupstrict}repeatedly.\emph{\olref{exrankpow}.} If $x \subseteq A$ then $\setrank{x} \leq\setrank{A}$. So $\setrank{\Pow{A}} \leq \alpha \ordplus  1$. Since $A\in \Pow{A}$ in particular, $\setrank{\Pow{A}} = \alpha \ordplus  1$.\emph{\olref{exrankpair}.} By \olref[spine][rank]{ranksupstrict}\emph{\olref{exrankcup}.} By \olref[spine][rank]{ranksupstrict}.\emph{\olref{exranktuple}.} By \olref{exrankpair}, twice.\emph{\olref{exranktimes}.} Note that $A \times B \subseteq\Pow{\Pow{A \cup B}}$, and invoke \olref{exranktuple}. \emph{\olref{exrankunion}.} If $\alpha = \gamma\ordplus 1$, there issome $c \in A$ with $\setrank{c} = \gamma$, and no !!{element} of $A$has higher rank; so $\setrank{\bigcup A} = \gamma$. If $\alpha$ is alimit ordinal, then $A$ has !!{element}s with rank arbitrarily closeto (but strictly less than) $\alpha$, so that $\bigcup A$ also has!!{element}s with rank arbitrarily close to (but strictly less than)$\alpha$, so that $\setrank{\bigcup A} = \alpha$.\end{proof}\noindentWe leave it as an exercise to show why \olref{exranktimes} involves an\emph{in}equality.\begin{prob}Produce sets $A$ and $B$ such that $\setrank{A \times B}=\max(\setrank{A}, \setrank{B})$. Produce sets $A$ and $B$ such that$\setrank{A \times B}\max(\setrank{A}, \setrank{B}) \ordplus  2$. Areany other ranks possible?\end{prob}We are also now in a position to show that several reasonable notionsof what it might mean to describe an ordinal as ``finite'' or ``infinite'' coincide:\begin{lem}\ollabel{ordinfinitycharacter}For any ordinal $\alpha$, the following are equivalent:\begin{enumerate}	\item\ollabel{ord:notinomega} $\alpha\notin \omega$, i.e.,	$\alpha$ is not a natural number	\item\ollabel{ord:omegaplus} $\omega \leq \alpha$ 	\item\ollabel{ord:oneplus} $1 \ordplus  \alpha = \alpha$ 	%\alpha \approx \alpha \ordplus 1$	\item\ollabel{ord:plusone} $\alpha \approx \alpha\ordplus 1$,	i.e., $\alpha$ and $\alpha\ordplus 1$ are equinumerous	\item\ollabel{ord:infinite} $\alpha$ is Dedekind infinite		\end{enumerate}\end{lem}\noindentSo we have five provably equivalent ways to understand what it takes for an ordinal to be (in)finite.\begin{proof}\emph{\olref{ord:notinomega} $\Rightarrow$ \olref{ord:omegaplus}.} ByTrichotomy. \emph{\olref{ord:omegaplus} $\Rightarrow$ \olref{ord:oneplus}.} Fix$\alpha \geq \omega$. By Transfinite Induction, there is some leastordinal $\gamma$ (possibly $0$) such that there is a limit ordinal$\beta$ with $\alpha = \beta \ordplus \gamma$. Now:\[	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.\]\emph{\olref{ord:oneplus} $\Rightarrow$ \olref{ord:plusone}.} There isclearly !!a{bijection} $f \colon (\alpha \disjointsum 1) \to (1\disjointsum \alpha)$. If $1 \ordplus \alpha = \alpha$, there is anisomorphism $g \colon (1 \disjointsum \alpha) \to \alpha$. Nowconsider $\comp{f}{g}$.\emph{\olref{ord:plusone} $\Rightarrow$ \olref{ord:infinite}.} If$\alpha \approx \alpha \ordplus 1$, there is !!a{bijection} $f \colon(\alpha \disjointsum 1) \to \alpha$. Define $g(\gamma) = f(\gamma, 0)$for each $\gamma < \alpha$; this !!{injection} witnesses that $\alpha$is Dedekind infinite, since $f(0,1) \in \alpha \setminus \ran{g}$. \emph{\olref{ord:infinite} $\Rightarrow$ \olref{ord:notinomega}.} Thisis \olref[z][infinity-again]{naturalnumbersarentinfinite}.\end{proof}\end{document}

content/set-theory/ord-arithmetic/multiplication.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{ord-arithmetic}{mult}\olsection{Ordinal Multiplication}We now turn to ordinal multiplication, and we approach this much likeordinal addition. So, suppose we want to multiply $\alpha$ by~$\beta$.To do this, you might imagine a rectangular grid, with width $\alpha$and height $\beta$; the product of $\alpha$ and $\beta$ is now theresult of moving along each row, then moving through the nextrow\ldots until you have moved through the entire grid. Otherwise put,the product of $\alpha$ and $\beta$ arises by replacing \emph{each}element in $\beta$ with a copy of $\alpha$.  To make this formal, we simply use the reverse lexicographic orderingon the Cartesian product of $\alpha$ and $\beta$:\begin{defn}For any ordinals $\alpha, \beta$, their product $\alpha \ordtimes \beta = \ordtype{\alpha \times \beta, \rlexless}$.\end{defn}\noindentWe must again confirm that this is a well-formed definition:\begin{lem}\ollabel{ordtimeslessiswo}$\tuple{\alpha \times \beta, \rlexless}$ is a well-order, for anyordinals $\alpha$ and $\beta$.\end{lem}\begin{proof}Exactly as for \olref[add]{ordsumlessiswo}.\end{proof}\noindentAnd it is not hard to prove that multiplication behaves thus:\begin{lem}\ollabel{ordtimesrecursion}For any ordinals $\alpha, \beta$:\begin{align*}	\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}.\end{align*}\end{lem}\begin{proof}Left as an exercise.\end{proof}Indeed, just as in the case of addition, we could have defined ordinalmultiplication via these recursion equations, rather than offering adirect definition. Equally, as with addition, certain behaviour isfamiliar:\begin{lem}\ollabel{ordinalmultiplicationisnice}If $\alpha, \beta, \gamma$ are ordinals, then:\begin{enumerate}	\item\ollabel{ordtimes1} if $\alpha \neq 0$ and $\beta < \gamma$,	then $\alpha \ordtimes \beta < \alpha \ordtimes \gamma$;	\item\ollabel{ordtimes2} if $\alpha \neq 0$ and $\alpha \ordtimes	\beta = \alpha\ordtimes\gamma$, then $\beta = \gamma$;	\item\ollabel{ordtimes3}  $\alpha \ordtimes (\beta \ordtimes	\gamma) = (\alpha \ordtimes \beta) \ordtimes \gamma$;	\item\ollabel{ordtimes4}  If $\alpha \leq \beta$, then $\alpha	\ordtimes \gamma \leq \beta \ordtimes \gamma$;	\item\ollabel{ordtimes5}  $\alpha \ordtimes (\beta \ordplus	\gamma) = (\alpha \ordtimes \beta )\ordplus (\alpha\ordtimes	\gamma)$.\end{enumerate}\end{lem}\begin{proof}Left as an exercise.\end{proof}You can prove (or look up) other results, to your heart's content.But, given\olref[ord-arithmetic][add]{ordsumnotcommute}, thefollowing should not come as a surprise:\begin{prop}Ordinal multiplication is not commutative: $2 \ordtimes \omega  =\omega < \omega \ordtimes 2$\end{prop}\begin{proof}$2 \ordtimes \omega = \supstrict_{n < \omega}(2\ordtimes  n) = \omega \in \supstrict_{n < \omega}(\omega \ordplus n) = \omega \ordplus \omega = \omega \ordtimes 2$.\end{proof}\noindent Again, the intuitive rationale is quite straightforward. To compute $2\ordtimes \omega$, 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 thenatural ordering on $\Setabs{\nicefrac{n}{2}}{n \in \omega}$. And, putlike that, the order type is plainly the same as that of $\omega$itself. But, to compute $\omega \ordtimes 2$, you place down twocopies of $\omega$, one after the other. \begin{prob}Prove\olref[sth][ord-arithmetic][mult]{ordtimeslessiswo},\olref[sth][ord-arithmetic][mult]{ordtimesrecursion},and\olref[sth][ord-arithmetic][mult]{ordinalmultiplicationisnice}\end{prob}\end{document}

content/set-theory/ord-arithmetic/exponentiation.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{ord-arithmetic}{expo}\olsection{Ordinal Exponentiation}We now move to ordinal exponentiation. Sadly, there is no \emph{nice}synthetic definition for ordinal exponentiation.Sure, there \emph{are} explicit synthetic definitions. Here is one.Let $\text{finfun}(\alpha,\beta)$ be the set of all functions $f\colon \alpha \to \beta$ such that $\Setabs{\gamma \in\alpha}{f(\gamma) \neq 0}$ is equinumerous with some natural number.Define a well-ordering on $\text{finfun}(\alpha,\beta)$ by $f\sqsubset g$ iff $f \neq g$ and $f(\gamma_0) < g(\gamma_0)$, where$\gamma_0 = \text{max}\Setabs{\gamma \in \alpha}{f(\gamma) \neqg(\gamma)}$. Then we can define $\ordexpo{\alpha}{\beta}$ as$\ordtype{\text{finfun}(\alpha, \beta), \sqsubset}$. Potter employsthis explicit definition, and then immediately explains:\begin{quote}	The choice of this ordering is determined purely by our desire to	obtain a definition of ordinal exponentiation which obeys the	appropriate recursive condition\ldots, and it is much harder to	picture than either the ordered sum or the ordered product.	\citep[p.~199]{Potter2004}\end{quote}Quite. We explained addition as ``a copy of $\alpha$ followed by acopy of $\beta$'', and multiplication as ``a $\beta$-sequence ofcopies of $\alpha$''. But we have nothing pithy to say about$\text{finfun}(\alpha, \gamma)$. So instead, we'll offer thedefinition of ordinal exponentiation just \emph{by} transfiniterecursion, i.e.:\begin{defn}\ollabel{ordexporecursion}\begin{align*}	\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}\end{align*}\end{defn}If we were working \emph{as} set theorists, we might want to exploresome of the properties of ordinal exponentiation. But we have nothingmuch more to add, except to note the unsurprising fact that ordinalexponentiation does not commute. Thus $\ordexpo{2}{\omega} =\bigcup_{\delta < \omega}\ordexpo{2}{\delta} = \omega$, whereas$\ordexpo{\omega}{2} = \omega \ordtimes \omega$. But then, we shouldnot \emph{expect} exponentiation to commute, since it does not commutewith natural numbers: $\ordexpo{2}{3} = 8 < 9 = \ordexpo{3}{2}$. \begin{prob}Using Transfinite Induction, prove that, if we define$\ordexpo{\alpha}{\beta} = \ordtype{\text{finfun}(\alpha, \beta),\sqsubset}$, we obtain the recursion equations of\olref[sth][ord-arithmetic][expo]{ordexporecursion}.\end{prob}\end{document}