\documentclass[a4paper,twoside,11pt,draft]{article}
\title{Ordinals}
\author{Math 320: Set Theory (David Pierce)}
\date{May 12, 2007}
\usepackage{bm}     % bold math
\usepackage{stmaryrd}   % for \shortrightarrow and \binampersand
%\usepackage{txfonts}    % for \omegaup; but this font caused problems
\usepackage{upgreek}     % for \upomega
\usepackage[mathscr]{euscript}
\usepackage{amssymb,amsmath,amsthm}
%\usepackage{amscd}     % commutative diagram
\usepackage{verbatim}  % allows a comment environment:
%\usepackage{parskip}   % paragraphs not indented, but separated by spaces
%\parskip=0.5\baselineskip \advance\parskip by 0pt plus 2pt
%  \parsep = \parskip
%  \itemsep = 0pt % add nothing to \parskip between items
%   \topsep = 0pt % add nothing to \parskip before first item


\usepackage{eco}  % gives old-style numerals

\newcommand{\defn}[1]{\textbf{#1}}   % for words being defined
\newcommand{\defin}[1]{\textbf{#1}}   % for words being defined
\newcommand{\tech}[1]{\textsl{#1}}     % for technical terms

\renewcommand{\phi}{\varphi}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}
\renewcommand{\theenumii}{\roman{enumii}}
\renewcommand{\labelenumii}{\theenumii.}
\renewcommand{\theequation}{\fnsymbol{equation}}

\swapnumbers
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{theorem*}{Theorem}
\newtheorem{thmdefn}[theorem]{Theorem and Definition}
\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem*{lemma}{Lemma}
\newtheorem{lemdefn}[theorem]{Lemma and Definition}
%\newtheorem{fact}[theorem]{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{axiomscheme}[theorem]{Axiom Scheme}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{porism}[theorem]{Porism}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
%\newtheorem{examples}[theorem]{Examples}
%\newtheorem{exercise}[theorem]{Exercise}
%\newtheorem{counter}[theorem]{Counter-Example}
%\newtheorem{non}[theorem]{Non-Example}
\newtheorem{parag}[theorem]{}

\newcommand{\qsep}{\;}                 % follows a quantified variable
\newcommand{\Forall}[1]{\forall{#1}\qsep }
\newcommand{\Exists}[1]{\exists{#1}\qsep }
\newcommand{\existsunique}{\exists!}
\newcommand{\Existsunique}[1]{\exists!\,{#1}\qsep }

\newcommand{\setim}[1][]{''{#1}} % image of set under preceding function 
\newcommand{\setimb}[1]{[\,#1\,]}    % image of set under preceding function 
\newcommand{\conv}[1]{\breve{#1}}       % converse of a relation
\newcommand{\To}{\longrightarrow}
\newcommand{\inv}{^{-1}}                % mult. inverse
\newcommand{\rest}[1]{\restriction{#1}}% restriction of function to #1
\newcommand{\id}[1]{\operatorname{id}_{#1}}
\newcommand{\mapset}[2]{{}^{#1}#2}     % set of functions from #1 to #2

\newcommand{\Iff}{}
\let\Iff\iff
%\renewcommand{\iff}{\leftrightarrow}
\renewcommand{\iff}{\Leftrightarrow}
%\newcommand{\lto}{\to}
\newcommand{\lto}{\Rightarrow}
\renewcommand{\land}{\mathrel{\binampersand}}

%%%%%%%%  sets:

\newcommand{\set}[2]{\{#1\colon #2\}}
\newcommand{\cls}[2]{\{#1\colon #2\}}
\newcommand{\class}[1]{\bm{#1}}
\newcommand{\cA}{\class A}
\newcommand{\cB}{\class B}
\newcommand{\cC}{\class C}
\newcommand{\cD}{\class D}
\newcommand{\cE}{\class E}
\newcommand{\cF}{\class F}
\newcommand{\cG}{\class G}
\newcommand{\cH}{\class H}
\newcommand{\cK}{\class K}
\newcommand{\cM}{\class M}
\newcommand{\cR}{\class R}
\newcommand{\cS}{\class S}
\newcommand{\cT}{\class T}

\newcommand{\universe}{\mathrm{\mathbf V}}
\newcommand{\russell}{\mathrm{\mathbf R}}
\newcommand{\cOm}{\bm{\mathit{\Omega}}}
\newcommand{\on}{\mathbf{ON}}           % the class of ordinals
\newcommand{\cn}{\mathbf{CN}}           % the class of cardinals
\newcommand{\wf}{\mathbf{WF}}           % class of well-founded sets
\newcommand{\rwf}{\mathrm{\mathbf R}}   % R used to define WF
\newcommand{\defr}[2]{\mathbf{D}_{#1}(#2)} % definable n-ary relations
\newcommand{\cu}{\mathbf{L}}            % constructible universe L
\newcommand{\const}{\mathrm{\mathbf L}} % C used to define L


\newcommand{\str}[1]{\mathfrak{#1}}     % structure
%\newcommand{\lang}{\mathcal{L}}        % a language or signature
\newcommand{\End}[1]{\operatorname{End}(#1)} % endomorphisms

% set-theoretic operators:

% nullary:

\renewcommand{\emptyset}{\varnothing}  % [I like the other symbol better]

% unary:

\newcommand{\comp}{^{\mathrm{c}}}      % set-theoretic complement
\newcommand{\pow}[1]{\mathcal{P}(#1)}  % power set

% binary:
\renewcommand{\setminus}{\smallsetminus} % I don't like the standard symbol
\newcommand{\symdiff}{\vartriangle}    % symmetric difference

%%%%%%%%%%%%  Cardinality

\newcommand{\injects}{\preccurlyeq}    % injects in
\newcommand{\pinjects}{\prec}
\newcommand{\equip}{\approx}           % equipollent (is in bijection with)
\newcommand{\nequip}{\not\approx}      % not equipollent
\newcommand{\vscr}[1]{#1'}        % successor ordinal (v for von Neumann)
\newcommand{\ord}[1]{\operatorname{ord}(#1)} % order-type (ordinality)
\newcommand{\supr}[1]{\sup(#1)}        % supremum
%\newcommand{\size}[1]{\lvert#1\rvert}  % cardinality
\newcommand{\card}[1]{\operatorname{card}(#1)} % cardinality
\newcommand{\pl}{^{+}}                 % successor cardinal
\newcommand{\cntm}{\mathfrak c}        % cardinality of the continuum
\newcommand{\pred}[1]{\operatorname{pred}(#1)}
\newcommand{\rank}[1]{\operatorname{rank}(#1)}

%%%%%%%%%%%%%  Functions

\newcommand{\dom}[1]{\operatorname{dom}(#1)} % domain
\newcommand{\ran}[1]{\operatorname{rng}(#1)} % range
\newcommand{\fld}[1]{\operatorname{f{}ld}(#1)} % field
\newcommand{\injection}{\rightarrowtail}
\newcommand{\surjection}{\twoheadrightarrow}
%\newcommand{\bijection}{\rightarrowtail\mkern-17mu\shortrightarrow}
\newcommand{\bijection}{\rightarrowtail\mkern-18mu\twoheadrightarrow}
\newcommand{\supp}[1]{\operatorname{supp}(#1)} % support

%%%%%%%%%%%%%

\newcommand{\included}{\subseteq}      % [the name suggests the meaning here]
\newcommand{\nincluded}{\not\subseteq} % not included
\newcommand{\pincluded}{\subset}       % proper inclusion    
\newcommand{\includes}{\supseteq}

%%%%%%%%%%%%%%%

\newcommand{\axioms}[1]{\mathrm{#1}}   % set-theoretic axiom or set of axioms
\newcommand{\zf}{\axioms{ZF}}          % Zermelo-Frankel axioms
%\newcommand{\ac}{\axioms{AC}}	       % Axiom of Choice
\newcommand{\zfc}{\axioms{ZFC}}        % ZF + AC
%\newcommand{\ch}{\axioms{CH}}          % Continuum Hypothesis
%\newcommand{\pa}{\axioms{PA}}          % first-order Peano arithmetic

%%%%%%%%%%%%%%%%

% Standard structures

\newcommand{\vnn}{\upomega}       % von Neumann natural numbers
\newcommand{\limord}{\lambda}     % limit ordinal

\newcommand{\stnd}[1]{\mathbb{#1}}
%\newcommand{\N}{\stnd{N}}         % natural numbers
\newcommand{\N}{\vnn}         % natural numbers
%\newcommand{\scr}[1]{#1^{+}}           % successor
\newcommand{\scr}[1]{#1'}           % successor
\newcommand{\Zp}{\Z_{+}}          % positive integers
\newcommand{\Z}{\stnd{Z}}         % integers
\newcommand{\Q}{\stnd{Q}}         % rationals
\newcommand{\R}{\stnd{R}}         % reals
\newcommand{\C}{\stnd{C}}         % complex numbers

\theoremstyle{definition}
\newtheorem{problem}{Problem}
%\theoremstyle{remark}
\newtheorem{solution}{}

\begin{document}
\maketitle
\thispagestyle{empty}

%\setcounter{section}{-1}
\section*{Preface}

This is a summary of \tech{ordinals,} as we are studying them.  You should be
able to give proofs by transfinite induction of the basic properties
of ordinal arithmetic 
(addition, multiplication, and exponentiation of ordinals).  If you
omit the limit steps from these proofs, then you have proved the same
properties of \tech{natural numbers,} by ordinary induction.

%\tableofcontents

\section{Introduction}

\begin{parag}
By definition, an \defn{ordinal} (or \defn{ordinal number}) is a
\tech{transitive} 
set that is \tech{well-ordered} by membership ($\in$).  Ordinals are
denoted by $\alpha$, $\beta$, $\gamma$, $\delta$, \dots
\end{parag}

\begin{parag}
The class of ordinals is denoted by $\on$.  This is a transitive class
that is well-ordered 
by membership.  Therefore it is a \tech{proper} class: it is not a set.  On
$\on$, membership is the same as proper inclusion 
($\pincluded$) and may be denoted by $<$.  So each ordinal is the set
of its predecessors in $\on$: that is,
$\alpha=\set{x\in\on}{x<\alpha}$. 
\end{parag}

\begin{parag}
  The class $\on$:
\begin{enumerate}
  \item
contains $\emptyset$, which is also denoted by $0$ and called \defn{zero;}
\item
is closed under the \defn{successor-operation,}
$x\mapsto\scr x$, where $\scr x=x\cup\{x\}$;
\item
contains the union of each of its subsets.
\end{enumerate}
\end{parag}

\begin{parag}
  The union of a subset of $\on$ is also its \defn{supremum} (least
upper bound):
\begin{equation*}
  \bigcup a=\supr a.
\end{equation*}
If $a=\set{\cF(x)}{\phi(x)}$, then $\supr a$ can be written as
$\sup_{\phi(x)}\cF(x)$. 
\end{parag}

\begin{parag}
  There are three kinds of ordinals:
\begin{enumerate}
  \item
zero;
\item
successors, namely, ordinals $\scr{\alpha}$;
\item
\defn{limits} (non-zero non-successors).
\end{enumerate}
The successor of $0$ is $1$; the successor of $1$ is $2$; and so on.
The first limit is $\N$, the set of \defn{natural numbers,} which is
the smallest set containing $0$ and closed under $x\mapsto\scr x$.
\emph{In these notes, $\limord$ will always denote a limit, and $n$
  will always denote a natural number.}  So
$\alpha<\limord\lto\scr\alpha<\limord$, which implies
\begin{equation*}
  \supr{\limord}=\limord.
\end{equation*}
Also, $\supr0=0$, but
$\supr{\scr\alpha}=\alpha$.
\end{parag}

\section{Induction and recursion}

\begin{parag}
  Proof by \defn{transfinite induction} is possible in $\on$: if
$\cC\included\on$, and
\begin{enumerate}
  \item
$0\in\cC$ (the \defn{base step}),
\item
$\alpha\in\cC\lto\scr{\alpha}\in\cC$ (the \defn{successor step}),
\item
$\limord\included\cC\lto\limord\in\cC$ (the \defn{limit step}),
\end{enumerate}
then $\cC=\on$.  (There are also alternative formulations of this procedure.)
\end{parag}

\begin{parag}
  Definition by \defn{transfinite recursion} is possible on $\on$: if
$\alpha$ is an ordinal, and $\cF$ is a singulary operation on $\on$, and
$\cG\colon\pow{\on}\to\on$, then there is a unique singulary operation
$\cH$ on $\on$ such that
\begin{enumerate}
  \item
$\cH(0)=\alpha$,
\item
$\cH(\scr{\beta})=\cF(\cH(\beta))$,
\item
$\cH(\limord)=\cG(\cH\setimb{\limord})$.
\end{enumerate}
(There are also alternative versions of this kind of definition.)
\end{parag}

\section{Operations}

\begin{parag}
  By recursion in the second argument, we can define the binary operations of
\defn{addition,  multiplication, and exponentiation} on $\on$:
\begin{align*}
&\alpha+0=\alpha,&
&\alpha\cdot0=0,&
&\alpha^0=1,\\
&\alpha+\scr\beta=\scr{(\alpha+\beta)}, &
&\alpha\cdot\scr\beta=\alpha\cdot\beta+\alpha,&
&\alpha^{\scr\beta}=\alpha^\beta\cdot\alpha, \\
&\alpha+\limord=\sup_{x<\limord}{(\alpha+x)}; &
&\alpha\cdot\limord=\sup_{x<\limord}{(\alpha\cdot x)}; &
&\alpha^{\limord}=      
      \sup_{0<x<\limord}{(\alpha^x)}.
\end{align*}
(Alternative definitions in terms of \tech{order types} are also possible.)
\end{parag}

\begin{parag}
  A singulary operation $\cF$ on $\on$ is \defn{normal} if:
\begin{enumerate}
  \item\label{item:a}
$\alpha<\beta\lto\cF(\alpha)<\cF(\beta)$ (that is, $\cF$ is strictly
    order-preserving); 
\item\label{item:b}
$\cF(\limord)=\sup_{x<\limord}\cF(x)$.
\end{enumerate}
If $\cF$ is normal, and $a\included\on$, then we can show
\begin{enumerate}\setcounter{enumi}{2}
\item
$\cF(\supr a)=\sup_{x\in a}\cF(x)$.
\end{enumerate}
\end{parag}

\begin{parag}
  By definition, the operations $x\mapsto\alpha+x$ and $x\mapsto
\alpha\cdot x$ satisfy part~\eqref{item:b} of the definition of
normality; so does $x\mapsto\alpha^x$, if $\alpha\neq0$.
However, the successor-operation is \emph{not} normal, even though it
satisfies~\eqref{item:a}; indeed, since
$\alpha<\lambda\lto\scr{\alpha}<\lambda$, we have $\set{\scr
  x}{x<\lambda}\included\lambda$, so
\begin{equation*}
  \sup_{x<\limord}(\scr x)
=\sup\set{\scr x}{x<\lambda}\leq\supr{\limord}=\limord<\scr{\limord}.
\end{equation*}
\end{parag}

\section{Arithmetic}

\begin{parag}
 By induction, we can establish the basic properties of:
\begin{enumerate}
  \item
addition:
\begin{enumerate}
  \item
$\beta<\gamma\lto\alpha+\beta<\alpha+\gamma$, so
$x\mapsto\alpha+x$ is normal;
\item
addition is associative: $\alpha+(\beta+\gamma)=(\alpha+\beta)+\gamma$;
\item
$0+\alpha=\alpha$;
\item
$\alpha\leq\beta\lto\alpha+\gamma\leq\beta+\gamma$;
\end{enumerate}
\item
multiplication:
\begin{enumerate}
\item
if $0<\alpha$, then
$\beta<\gamma\lto\alpha\cdot\beta<\alpha\cdot\gamma$, so
$x\mapsto\alpha\cdot x$ is normal;
\item
multiplication is associative:
$\alpha\cdot(\beta\cdot\gamma)=(\alpha\cdot\beta)\cdot\gamma$; 
\item
multiplication from the left distributes over addition:
$\alpha\cdot(\beta+\gamma)=\alpha\cdot\beta+\alpha\cdot\gamma$; 
\item
$1\cdot\alpha=\alpha$;
\item
$\alpha\leq\beta\lto\alpha\cdot\gamma\leq\beta\cdot\gamma$;
\end{enumerate}
\item
exponentiation:
\begin{enumerate}
\item
if $1<\alpha$, then $\beta<\gamma\lto\alpha^\beta<\alpha^\gamma$, so
$x\mapsto\alpha^x$ is normal;
\item
$\alpha^{\beta+\gamma}=\alpha^\beta\cdot\alpha^\gamma$;
\item
$(\alpha^\beta)^\gamma=\alpha^{\beta\cdot\gamma}$;
\item
$0<\alpha\lto0^\alpha=0$;
\item
$1^\alpha=1$;
\item
$\alpha\leq\beta\lto\alpha^\gamma\leq\beta^\gamma$.
\end{enumerate}
\end{enumerate}
\end{parag}

\begin{parag}
  We now have the following initial segment of $\N$; every entry is a
  limit if it is
\emph{not} of the form $\alpha+n$, where $n\in\N$:
\begin{align*}
&  0,1,2,\dots;\\
&\N,\N+1,\N+2,\dots;\\
&\N+\N=\N\cdot 2,\N\cdot
  2+1,\dots;\N\cdot 3,\dots;\\
&\N\cdot\N=\N^2,\N^2+1,\dots;\N^2+\N,\dots;\N^2+\N\cdot
  2,\dots;\N^2\cdot
  2,\dots;\N^3,\dots;\\
&\N^{\N},\dots;\N^{\N+1},\dots;\N^{\N\cdot
  2},\dots;\N^{\N^2},\dots;\N^{\N^\N},\dots
\end{align*}
\end{parag}

\begin{thmdefn}
  If $\alpha\leq\beta$, then the equation
  \begin{equation*}
    \alpha+x=\beta
  \end{equation*}
has a unique solution, which can be denoted by
\begin{equation*}
  \beta-\alpha.
\end{equation*}
\end{thmdefn}

\begin{proof}
  If there is \emph{some} solution, then its uniqueness follows, since
  $x\mapsto\alpha+x$ is strictly order-preserving.  We prove existence
  by induction on $\beta$:
  \begin{enumerate}
    \item
If $\beta=0$ and $\alpha\leq\beta$, then $\alpha=0$, so
$\alpha+0=\beta$.

\item
Suppose the claim holds when $\beta=\gamma$.  Say
$\alpha\leq\scr\gamma$.  If $\alpha=\scr\gamma$, then
$\alpha+0=\scr\gamma$.  If $\alpha<\scr\gamma$, then
$\alpha\leq\gamma$, so $\gamma-\alpha$ exists, and then
\begin{equation*}
  \alpha+\scr{(\gamma-\alpha)}=\scr{(\alpha+(\gamma-\alpha))}=\scr\gamma.
\end{equation*}
%in particular, $\scr\gamma-\alpha=\scr{(\gamma-\alpha)}$.
Thus the claim holds when $\beta=\scr\gamma$.
\item
Suppose the claim holds when $\beta<\lambda$.  Say
$\alpha\leq\lambda$.  If $\alpha=\lambda$, then $\alpha+0=\lambda$.
Now suppose $\alpha<\lambda$.  We shall show
\begin{equation}\label{eqn:sup}
  \alpha+\sup\set{x}{\alpha+x<\lambda}=\lambda.
\end{equation}
Since $x\mapsto \alpha+x$ is normal, we have
\begin{equation*}
  \alpha+\sup\set{x}{\alpha+x<\lambda}=
  \sup\set{\alpha+x}{\alpha+x<\lambda}\leq\supr\lambda=\lambda.
\end{equation*}
For the reverse inequality, suppose $\alpha\leq\gamma<\lambda$.  Then
$\gamma-\alpha$ exists and is a member of $\set x{\alpha+x<\lambda}$,
so
\begin{gather*}
  \gamma-\alpha\leq\sup\set x{\alpha+x<\lambda},\\
\gamma=\alpha+(\gamma-\alpha)\leq\alpha+\sup\set x{\alpha+x<\lambda}.
\end{gather*}
Therefore $\lambda\leq\alpha+\sup\set x{\alpha+x<\lambda}$, and
\eqref{eqn:sup} holds.
This completes the induction and the proof.\qed
  \end{enumerate}
\renewcommand{\qed}{}
\end{proof}

\begin{parag}
Addition and multiplication on $\N$ have properties that fail
on $\on$.  As we can prove by induction, on $\N$:
\begin{enumerate}
  \item
addition is commutative: $n+m=m+n$;
\item
multiplication is commutative: $n\cdot m=m\cdot n$;
\item
multiplication distributes from the right:
$(n+m)\cdot k=n\cdot k+m\cdot k$.
\end{enumerate}
However, on $\on$,
\begin{enumerate}
  \item
addition does not commute: $1+\N<\N+1$, since
\begin{equation*}
  1+\N=\sup\set{1+x}{x\in\N}\leq\supr{\N}=\N<\N+1;
\end{equation*}
\item
multiplication does not commute: $2\cdot\N<\N\cdot 2$, since
\begin{equation*}
  2\cdot\N=\sup\set{2\cdot x}{x\in\N}\leq\supr{\N}=\N<\N\cdot 2,
\end{equation*}
\item
multiplication does not distribute:
  $(1+1)\cdot\N<1\cdot\N+1\cdot\N$.
\end{enumerate}
\end{parag}

\section{Base $\N$}

\begin{parag}
The remainder of these notes investigates
the possibility of computations with ordinals.
\end{parag}


\begin{lemma}
  $\beta<\alpha\lto\N^\beta+\N^\alpha=\N^\alpha$.
\end{lemma}

\begin{lemma}
  $\beta+\alpha=\alpha\lto(\alpha+\beta)\cdot\gamma=
  \begin{cases}
\alpha\cdot\gamma+\beta,&\text{ if $\gamma$ is a successor;}\\
\alpha\cdot\gamma,&\text{ if $\gamma$ is a limit or $0$.}
  \end{cases}$
\end{lemma}


\begin{parag}
  An algorithm for writing a positive natural number $n$ in
decimal or ``base-ten'' notation is 
the following: 
\begin{enumerate}
  \item
Find $k$ such that $10^k\leq n<10^{k+1}$;
\item
find $n_0$ such that $10^k\cdot n_0\leq n<10^k\cdot(n_0+1)$;
\item
find $n_1$ such that $10^k\cdot n_0+10^{k-1}\cdot n_1\leq n< 
10^k\cdot n_0+10^{k-1}\cdot(n_1+1)$;
\item
and so on.
\end{enumerate}
Then 
\begin{equation*}
n=10^k\cdot n_0+10^{k-1}\cdot n_1+\dotsb+n_k=\sum_{i=0}^k10^{k-i}\cdot n_i, 
\end{equation*}
and we may write $n$ simply as
$n_0\;n_1\dotsb n_k$.  A similar procedure allows us to write any
ordinal in base $\N$.  We first need to know that sufficiently large
powers of $\N$ can be found:
\end{parag}

\begin{lemma}
  $\alpha\leq\N^\alpha$, so $\alpha<\N^{\scr\alpha}$.
\end{lemma}


\begin{lemma}
If $0<\alpha$, then there are (unique) $\beta$ and $n$ such that
\begin{equation*}
  \N^\beta\cdot n\leq\alpha<\N^\beta\cdot (n+1).
\end{equation*}
\end{lemma}

\begin{proof}
If $\alpha\in\N$, then $\beta=0$ and $n=\alpha$.  Now assume $\N\leq\alpha$.
By the previous lemma, the class $\set x{\N^x\leq\alpha}$ is bounded
  above by $\alpha$; so the class is a subset of $\scr\alpha$; so the
  class is a set.  Let $\beta$ be its supremum.  Then $1\leq\beta$.
  By normality of $x\mapsto\alpha^x$, we have
  \begin{equation*}
    \N^\beta
=\supr{\set{\N^x}{\N^x\leq\alpha}}\leq\alpha.
  \end{equation*}
Now, $\alpha<\N^{\scr\beta}=\N^\beta\cdot\N$.  By normality of
$x\mapsto\N^\beta\cdot x$, there is a greatest $n$ such that
$\N^\beta\cdot n\leq\alpha$.  Then $\alpha<\N^\beta\cdot(\scr
n)=\N^\beta\cdot n+\N^\beta$.  So $\beta$ and $n$ are as desired.
(Uniqueness is straightforward.)
\end{proof}

\begin{theorem}
For every positive ordinal $\alpha$, for some positive $k$ in $\N$, there are
ordinals $\beta_0$, \dots, $\beta_k$, and there are positive natural numbers
$n_0$, \dots, $n_{k-1}$ and a natural number $n_k$, such that
\begin{equation*}
  \alpha=\N^{\beta_0}\cdot n_0+\dotsb+\N^{\beta_k}\cdot n_k,
\end{equation*}
where $\beta_k<\dotsb<\beta_0$.
\end{theorem}

\begin{proof}
  Apply the previous lemma repeatedly, to $\alpha$, and then to
  $\alpha-\N^{\beta}\cdot n$, and so on.  The process must end, since
  there is no infinite strictly descending sequence of ordinals.
\end{proof}

\begin{parag}
We can add and multiply ordinals in base $\N$; for example,
  \begin{gather*}
  (\N^{\N+1}\cdot 3+\N^6\cdot 4+1)\cdot(\N^{\N^2}\cdot 2+3)\\
=  (\N^{\N+1}\cdot 3+\N^6\cdot 4+1)\cdot(\N^{\N^2}\cdot 2)+
  (\N^{\N+1}\cdot 3+\N^6\cdot 4+1)\cdot3\\
=  (\N^{\N+1}\cdot 3)\cdot(\N^{\N^2}\cdot 2)+
  (\N^{\N+1}\cdot 3)\cdot 3+\N^6\cdot 4+1\\
=  \N^{\N+1}\cdot(3\cdot\N^{\N^2})\cdot 2+
  \N^{\N+1}\cdot(3\cdot 3)+\N^6\cdot 4+1\\
=  (\N^{\N+1}\cdot\N^{\N^2})\cdot 2+
  \N^{\N+1}\cdot9+\N^6\cdot 4+1\\
=  (\N^{\N+1+\N^2})\cdot 2+
  \N^{\N+1}\cdot9+\N^6\cdot 4+1\\
=  (\N^{\N^2})\cdot 2+
  \N^{\N+1}\cdot9+\N^6\cdot 4+1.
\end{gather*}
\end{parag}

\end{document}

