\documentclass{amsart}
\usepackage{amssymb}
\usepackage{amsmath}


\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}



\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exer}{Exercise}


\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{fact}[thm]{Fact}
\newtheorem{hyp}[thm]{Hypothesis}

\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\res}{\restriction}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\cof}{\operatorname{cof}}
\newcommand{\on}{\text{ON}}
\newcommand{\ac}{\text{AC}}

\begin{document}
\begin{center}
\bf Examples of Ordinal Arithmetic
\end{center}
\bigskip


We'll use frequently the exercise that $\omega^\alpha + 
\omega^\beta =\omega^\beta$ if $\alpha < \beta$. 

\begin{lem}
$(\omega^{\alpha_0} \cdot k_0 + \omega^{\alpha_1} \cdot k_1 + \cdots 
\omega^{\alpha_n} \cdot k_n) \cdot \beta =
(\omega^{\alpha_0} \cdot k_0 \cdot \beta) $, if $\beta$ is 
a limit and $=(\omega^{\alpha_0} \cdot k_0 \cdot \beta)+ (\omega^{\alpha_1}
\cdot k_1 + \dots + \omega^{\alpha_n} \cdot k_n)$ 
if $\beta$ is a successor ($T$ stands
for ``tail.'')
\end{lem}


\begin{proof}
By induction on $\beta$. For $\beta=0$ it is trivial (provided we consider $0$
a limit ordinal!; it is also trivial for $\beta=1$ if you prefer
to start there). Let $\alpha$ denote $\omega^{\alpha_0} \cdot k_0 + 
\omega^{\alpha_1} \cdot k_1 + \cdots 
\omega^{\alpha_n} \cdot k_n$.  Let $T$ (for ``tail'') denote 
$\omega^{\alpha_1}
\cdot k_1 + \dots + \omega^{\alpha_n} \cdot k_n$. 

Case I.) $\beta$ is a successor, say $\beta=\gamma+1$. 
Then $\alpha \cdot \beta= \alpha \cdot 
(\gamma +1)= \alpha \cdot \gamma + \alpha = 
(\omega^{\alpha_0} \cdot k_0\cdot \gamma) +?T + 
(\omega^{\alpha_0} \cdot k_0 + 
\omega^{\alpha_1} \cdot k_1 + \cdots 
\omega^{\alpha_n} \cdot k_n)$ where $?T$ denotes $T$ if $\gamma$ is a 
successor and denotes $0$ if $\gamma$ is a limit. From the exercise 
$T+ \omega^{\alpha_0} \cdot k_0= \omega^{\alpha_0}\cdot k_0$, so in either
case this
becomes $= \omega^{\alpha_0} \cdot k_0 \cdot \gamma + 
\omega^{\alpha_0}\cdot k_0 + T = 
\omega^{\alpha_0} \cdot k_0\cdot (\gamma +1) + T= 
\omega^{\alpha_0+1} \cdot k_0 \cdot \beta +T$ which is what is claimed. 

Case II.) $\beta$ is a limit. 
Then $$\alpha \cdot \beta= \alpha \cdot (\sup_{\beta' < \beta} \beta)=
\sup_{\beta' < \beta} \alpha \cdot \beta' = 
\sup_{\beta' < \beta} (\omega^{\alpha_0} \cdot k_0 \cdot \beta' +T),$$ 
where we have assumed without loss of generality that $\beta'$ is a 
successor ordinal (every limit is a limit of successors). Now
$\omega^{\alpha_0} \cdot k_0 \cdot \beta' +T <
\omega^{\alpha_0} \cdot k_0 \cdot \beta' +T + \omega^{\alpha_0}\cdot k_0=
\omega^{\alpha_0} \cdot k_0 \cdot \beta' +\omega^{\alpha_0}\cdot k_0=
\omega^{\alpha_0} \cdot k_0 \cdot (\beta' +1)$. Since $\beta' +1 < \beta$
whenever $\beta'< \beta$ (as $\beta$ is a limit) the supremum is
bounded by
$\sup_{\beta' < \beta} (\omega^{\alpha_0} \cdot k_0 \cdot (\beta'+1))=
\omega^{\alpha_0} \cdot k_0 \cdot \beta$. Clearly this is also a lower 
bound for the supremum, and we are done. 
\end{proof}



Using this lemma, ordinal multiplication is now straightforward. For
example, here is the example we did in class:

\begin{equation*}
\begin{split}
&(\omega^{\omega^2 +\omega} \cdot 3 + \omega^2 \cdot 3 +11) 
\cdot (\omega^{\omega^2} \cdot 2 + \omega^{\omega} \cdot 2 +17)
\\ & \quad = \omega^{\omega^2+\omega} \cdot 3 \cdot 
(\omega^{\omega^2} \cdot 2 + \omega^{\omega} \cdot 2 +17) 
+ \omega^{2} \cdot 3 +11 \\
& \quad = \omega^{\omega^2+\omega} \cdot (\omega^{\omega^2} \cdot 2 + 
\omega^{\omega} \cdot 2 +51)+ \omega^2 \cdot 3 +11 \\
& \quad = \omega^{\omega^2 \cdot 2}\cdot 2 + 
\omega^{\omega^2 +\omega \cdot 2} \cdot 2
+ \omega^{\omega^2 +\omega} \cdot 51 +\omega^2 \cdot 3 +11
\end{split}
\end{equation*}
which is now in Cantor normal form. 



Now let's turn to exponentiation. To warm up, let's first compute 
$\alpha ^m$ where $m \in \omega$. 

\begin{lem}
$(\omega^{\alpha_0} \cdot k_0 + 
\omega^{\alpha_1} \cdot k_1 + \cdots 
\omega^{\alpha_n} \cdot k_n)^m= 
\omega^{\alpha_0 \cdot m} \cdot k_0 + \omega^{\alpha_0 \cdot (m-1) +\alpha_1}
\cdot k_1 +\cdots + \omega^{\alpha_0\cdot (m-1) + \alpha_{n-1}} \cdot k_{n-1}
+ \begin{cases} \omega^{\alpha_0 \cdot(m-1) + \alpha_n} \cdot k_n & \text{ if }
\alpha_n >0 \\ \alpha^{m-1} \cdot k_n & \text{ if } \alpha_n=0
\end{cases}$
\end{lem}
Note that if $\alpha_n=0$ (i.e., $\alpha$ is a successor ordinal), 
then the last term requires us to recursively compute $\alpha^{m-1}$. 




\begin{proof}
First assume that $\alpha_n >0$, 
so $\alpha$ is a limit. Since $\alpha^m= \alpha^{m-1} \cdot \alpha$,
and $\alpha$ is a limit ordinal, 
applying the multiplication rule $m-1$ times gives 
\begin{equation*}
\begin{split}
\alpha^m=& \alpha^{m-1} \cdot \alpha=
(\omega^{\alpha_0} \cdot k_0)^{m-1} \cdot \alpha=
(\omega^{\alpha_0} \cdot k_0)^{m-1} \cdot (\omega^{\alpha_0} \cdot k_0+ \cdots
+ \omega^{\alpha_n} \cdot k_n) =
\\ &
\omega^{\alpha_0 \cdot m} \cdot k_0 +\omega^{\alpha_0 \cdot (m-1) +\alpha_1}
\cdot k_1+\dots + \omega^{\alpha_0\cdot (m-1) + \alpha_n} \cdot k_n
\end{split}
\end{equation*}


Next assume that $\alpha_0=0$, so that last term is $k_n$ and hence
$\alpha$ is a successor ordinal. 
Let $H=\omega^{\alpha_0} \cdot k_0 + \cdot + \omega^{\alpha_{n-1}} \cdot
k_{n-1}$ ($H$ stands for ``head''). Then $\alpha^m= \alpha^{m-1} \cdot (H+ k_n)
=\alpha^{m-1} \cdot H + \alpha^{m-1} \cdot k_n$. Since $H$ is a limit
ordinal, the first term, using the multiplication lemma, becomes 
$(\omega^{\alpha_0} \cdot k_0 ))^{m-1} \cdot H= 
\omega^{\alpha_0 \cdot m} \cdot k_0 +\omega^{\alpha_0 \cdot (m-1) +\alpha_1}
\cdot k_1+\dots + \omega^{\alpha_0\cdot (m-1) + \alpha_{n-1}} \cdot k_{n-1}$
and the result follows.
\end{proof}


{\bf Example}. 
Let's compute $(\omega^{\omega^2 + \omega} \cdot 3 + \omega^\omega
\cdot 7 + 2)^3$. Let $\alpha$ denote 
$\omega^{\omega^2 + \omega} \cdot 3 + \omega^\omega
\cdot 7 + 2$.
Using the previous lemma we have:

\begin{equation*}
\begin{split}
& (\omega^{\omega^2 + \omega} \cdot 3 + \omega^\omega
\cdot 7 + 2)^3= \omega^{(\omega^2 + \omega) \cdot 3} \cdot 3 +
\omega^{(\omega^2 + \omega) \cdot 2 + \omega} \cdot 7 + \alpha^2 \cdot 2
\\ & \quad =
\omega^{\omega^2 \cdot 3 + \omega} \cdot 3 + \omega^{\omega^2 \cdot 2 + \omega
\cdot 2} \cdot 7 + \alpha^2 \cdot 2 
\\ & \quad = 
\omega^{\omega^2 \cdot 3 + \omega} \cdot 3 + \omega^{\omega^2 \cdot 2 + 
\omega \cdot 2} \cdot 7 + \omega^{(\omega^2 + \omega) \cdot 2} \cdot 3 \cdot 2
+ \omega^{\omega^2 + \omega + \omega} \cdot 7 \cdot 2 + \alpha \cdot 4
\\ & \quad 
=\omega^{\omega^2 \cdot 3 + \omega} \cdot 3 + \omega^{\omega^2 \cdot 2 + 
\omega \cdot 2} \cdot 7 +\omega^{ \omega^2 \cdot 2 + \omega} \cdot 6 + 
\omega^{\omega^2 + \omega \cdot 2} \cdot 14 + \alpha \cdot 4
\\ & \quad 
=\omega^{\omega^2 \cdot 3 + \omega} \cdot 3 + \omega^{\omega^2 \cdot 2 + 
\omega \cdot 2} \cdot 7 +\omega^{ \omega^2 \cdot 2 + \omega} \cdot 6 + 
\omega^{\omega^2 + \omega \cdot 2} \cdot 14
+\omega^{\omega^2 + \omega} \cdot 12 + \omega^\omega \cdot 28 + 8
\end{split}
\end{equation*}




Computing $\alpha^\beta$ when $\beta$ is a limit ordinal is easier. 

\begin{lem}
If $\beta$ is a limit, then $(\omega^{\alpha_0} \cdot k_0 + \dots + 
\omega^{\alpha_n} \cdot k_n )^ \beta= 
\omega^{\alpha_0 \cdot \beta}$. 
\end{lem}

\begin{proof}
We prove this by induction on $\beta$. For $\beta = \omega$, note that 
$(\omega^{\alpha_0} \cdot k_0 + \dots + 
\omega^{\alpha_n} \cdot k_n )^m$ lies between 
$\omega^{\alpha_0 \cdot m}$ and 
$(\omega^{\alpha_0} \cdot (k_0+1) )^m =\omega^{\alpha_0 \cdot m}
\cdot (k_0+1)< \omega^{\alpha_0 \cdot m +1}$, and both of these sup up to 
$\omega^{\alpha_0 \cdot \omega}$. 

If $\beta $ is a limit of limit ordinals, then using induction we have
$$(\alpha)^\beta= \sup_{\overset{\beta'< \beta}{\beta' \text{ limit}}} 
\omega^{\beta'}=\sup_{\overset{\beta'< \beta}{\beta' \text{ limit}}} 
\omega^{\alpha_0 \cdot \beta'} =\omega^{\alpha_0 \cdot \beta}
$$

If $\beta$ is not a limit of limit ordinals, then $\beta=\beta' + \omega$
for some limit ordinal $\beta'$. Then 
$$\alpha^\beta= \alpha^{\beta' + \omega}= \alpha^{\beta'} \cdot 
\alpha^\omega = \omega^{\alpha_0 \cdot \beta'} \cdot \omega^{\alpha_0 \cdot 
\omega}= \omega^{ \alpha_0 \cdot \beta' + \alpha_) \cdot \omega}=
\omega^{\alpha_0 \cdot(\beta'+\omega)}=\omega^{\alpha_0 \cdot \beta}.$$
\end{proof}


Since every ordinal $\beta$ is of the form $\lambda +m$ for some limit
ordinal $\lambda$, we now have complete rules for ordinal exponentiation. 


{\bf Example}. We compute $\alpha^\beta$ where 
$\alpha=\omega^{\omega^2 + \omega} \cdot 3 + \omega^\omega
\cdot 7 + 2$ (as in the above example) and $\beta= \omega^3+3$. 

\begin{equation*}
\begin{split}
& \alpha^\beta=  \alpha^{\omega^3} \cdot \alpha^3=
\omega^{(\omega^2 + \omega) \cdot \omega^2} \cdot \alpha^3=
\omega^{\omega^4} \cdot  \alpha^3 = \\ & 
\omega^{\omega^4+\omega^2 \cdot 3 + \omega} \cdot 3 + 
\omega^{\omega^4+\omega^2 \cdot 2 + 
\omega \cdot 2} \cdot 7 +
\omega^{ \omega^4+ \omega^2 \cdot 2 + \omega} \cdot 6 + 
\omega^{\omega^4+ \omega^2 + \omega \cdot 2} \cdot 14\\ & \quad 
+\omega^{\omega^4+ \omega^2 + \omega} \cdot 12 + 
\omega^{\omega^4+\omega} \cdot 28 + \omega^4 \cdot 8
\end{split}
\end{equation*}






\end{document}