\documentclass[%
version=last,%
a5paper,%
12pt,%
%headings=small,%
%bibliography=totoc,% index=totoc,%
twoside,%
open=any,%
%parskip=half,%  this option takes 2.5% more space than parskip
draft=true,%
%titlepage=false,%
DIV=12,%
headinclude=false,%
pagesize]%
{scrbook}
%{scrartcl}

\usepackage{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\ofoot{\pagemark}
\refoot{\leftmark}
\lofoot{\rightmark}
%\cehead{K\"umeler Kuram\i}
%\cohead{\today}

\usepackage{moredefs,lips}

\usepackage{verbatim}
 \usepackage{hfoldsty}
\usepackage[perpage,symbol*]{footmisc}

 \renewcommand{\thefootnote}{\fnsymbol{footnote}}

\usepackage[neverdecrease]{paralist}

\usepackage{pstricks,pst-node,pst-tree}

\usepackage{amsmath,amssymb,amsthm,url,upgreek}
%\allowdisplaybreaks

\DeclareMathOperator{\pred}{pred}

\newtheorem{theorem}{Theorem}
%\newtheorem{proposition}{\"Onerme}
\newtheorem*{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
%\newtheorem*{theorem*}{Teorem}

%\newtheorem{axiom}{\scshape Aks\.\i yom}
%\newtheorem{axiom}{AKS\.IYOM}
%\theoremstyle{definition}
\theoremstyle{remark}

%  The template for the following is taken from
%  http://en.wikibooks.org/wiki/LaTeX/Theorems 
%  The punctuation dot is needed (default is apparently no dot).
%  ``Space after theorem head'' is needed (otherwise errors).
\newtheoremstyle{xca}% name of the style to be used
  {}% measure of space to leave above the theorem. E.g.: 3pt
  {}% measure of space to leave below the theorem. E.g.: 3pt
  {\sffamily}% name of font to use in the body of the theorem
  {}% measure of space to indent
  {\sffamily\itshape}% name of head font
  {.}% punctuation between head and body
  {0.5em}% space after theorem head; " " = normal interword space
  {}% Manually specify head

\theoremstyle{xca}
\newtheorem{xca}{Al\i\c st\i rma}
\renewcommand{\thexca}{\Roman{xca}}

\usepackage{bm}

\newcommand{\lto}{\Rightarrow}
\newcommand{\liff}{\Leftrightarrow}
\newcommand{\Forall}[1]{\forall{#1}\;}
\newcommand{\Exists}[1]{\exists{#1}\;}
\newcommand{\universe}{\mathbf V}
\newcommand{\on}{\mathbf{ON}}
\newcommand{\cn}{\mathbf{KN}}
\newcommand{\zf}{\ensuremath{\mathrm{ZF}}}
\newcommand{\ac}{\ensuremath{\mathrm{AC}}}
\newcommand{\zfc}{\ensuremath{\mathrm{ZFC}}}
\newcommand{\ch}{\ensuremath{\mathrm{KH}}}
\newcommand{\gch}{\ensuremath{\mathrm{GKH}}}
\DeclareMathOperator{\cardinal}{card}
\newcommand{\card}[1]{\cardinal(#1)}
\newcommand{\cardsum}{\oplus}
\newcommand{\cardprod}{\otimes}
\DeclareMathOperator{\cofinality}{kf}
\newcommand{\cof}[1]{\cofinality(#1)}

\DeclareMathOperator{\supp}{supp}

%\renewcommand{\max}{\operatorname{maks}}
\newcommand{\letsep}{\quad}

\newcommand{\pow}[2][]{\wp_{#1}(#2)}
\usepackage{mathrsfs}
%\newcommand{\pow}[2][]{\mathscr P_{#1}(#2)}
%\newcommand{\powf}[1]{\pow[\upomega]{#1}}

\newcommand{\included}{\subseteq}
\newcommand{\nincluded}{\nsubseteq}
\newcommand{\includes}{\supseteq}
\newcommand{\pincluded}{\subset}
\newcommand{\npincluded}{\not\subset}

\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}

\renewcommand{\emptyset}{\varnothing}
\renewcommand{\phi}{\varphi}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\upepsilon}{\upvarepsilon}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\setminus}{\smallsetminus}

\DeclareMathOperator{\lc}{lc}

\usepackage{chngcntr}
\counterwithout{equation}{chapter}


%\usepackage[all]{xy}

\begin{document}
%\frontmatter
\title{Ordinal Analysis II}
\subtitle{A course at the Nesin Matematics Village}
\author{David Pierce}
\date{February 3--9, 2020\\
Last edited February 14, 2020}
\publishers{Matematik B\"ol\"um\"u\\
Mimar Sinan G\"uzel Sanatlar \"Universitesi\\
\.Istanbul\\
\url{dpierce@msgsu.edu.tr}\\
\url{mat.msgsu.edu.tr/~dpierce/}\\
\url{polytropy.com}}

\maketitle

\tableofcontents

\addchap{Preface}

Here are notes in English from
Ordinal Analysis II,
given at the Nesin Matematik K\"oy\"u in \c Sirince,
February 3--9, 2020.
English is the language I wrote on the blackboards
of the Ni\c sanyan K\"ut\"uphanesi,
while speaking mostly in Turkish.
One student proposed that I speak in English,
but another student objected.

At the beginning of the first day,
when there were around fifty students,
I wrote the sequence of ordinals---%
\eqref{eqn:on} on page \pageref{eqn:on}---%
across all four boards in the library.
On the last day, there were seven students.

I had given Ordinal Analysis I in the previous week,
in the Arf Dersli\u gi.
The two courses together together covered
much of what I had done
in Aksiyomatik K\"umeler Kuram\i\
in the previous semester at Mimar Sinan.
\begin{compactdesc}
\item[Ordinal Analysis I] introduced the Zermelo--Fraenkel axioms
as they were needed to develop and prove the desired properties
of the class $\on$ of ordinals.
\item[Ordinal Analysis II]
  assumed those properties
  (listed on page \pageref{on-props})
  and developed the arithmetic of the ordinals.
\end{compactdesc}
The latter course
is summarized on page \pageref{sum}.
I did not typeset new notes for the first course.
I did not assume that students in the second course
had taken the first.
In all but one or two cases they had not.
One student from the Mimar-Sinan course
did attend the entirety of Ordinal Analysis II.

I started that course,
thinking that I would
progressively introduce concrete examples of well-ordered sets:
\begin{compactenum}[1)]
  \item
    $\upomega$,
    closed under addition,
    multiplication, and exponentiation,
    but containing no limits;
  \item
    $\upomega\sqcup\upomega$,
    isomorphic to $\upomega+\upomega$
    and containing a single limit;
    \item
      $\upomega\times\upomega$,
      isomorphic to $\upomega\cdot\upomega$,
      closed under addition,
      and containing infinitely many limits,
      which themselves have no limit;
    \item
      the set of operations on $\upomega$
      that have finite support: this set is
      isomorphic to $\upomega^{\upomega}$,
      is closed under addition and multiplication,
      and has limits of limits;
    \item
      the set of finite rooted trees: this set is
      isomorphic to $\upepsilon_0$
      and closed under all of the operations.
\end{compactenum}
In the event, I did not isolate the last two examples,
but I interpreted arbitrary powers $\alpha^{\beta}$
as sets of functions,
and after $\upomega$ I considered only $\on$ itself
as being closed under all of the operations.

I often left proofs as exercises.
Had there been time,
I would have had students give their proofs at the board:
I do this at Mimar Sinan,
and I have done it in other courses at the Math Village.
This time I wanted to cover all of my Mimar-Sinan course
in two-thirds of the time.

Some students asked for references.
These would include:
\begin{compactitem}
\item
  the notes (in Turkish) from my Mimar-Sinan course;
\item
  any set-theory textbook,
  particularly Levy, \emph{Basic Set Theory}
  (Dover, 2002), which has perhaps been my own main reference;
\item
  Ali Nesin's A\c c\i k Ders text,
  \emph{Aksiyomatik K\"umeler Kuram\i\ (D\"onem 1),}
  on the website of the T\"urkiye Bilimler Akademisi.
  I have recommended this text to students at Mimar Sinan
  and used as a source for Turkish terminology.
\end{compactitem}

\addchap{My Personal Journey}

I was not prepared for the question of references.
Since I started learning real mathematics from one Donald J. Brown
in my last two years (1981--3) at St.\ Albans School
in Washington, D.C.,
I have understood the main text of a mathematics course
to be the teacher's own lectures.
Mr Brown had us copy down exactly
what he wrote on the blackboards of his classroom,
and he inspected our notebooks
(though perhaps mainly to see that we had reinforced the holes
in our sheets of paper so that they would not easily tear
from our three-ring binders).

Mr Brown did have us buy
supplementary books,
to be used particularly as sources of exercises.%%%%%
\footnote{For the record,
  the books
  were the following,
  roughly in order of use.
\begin{compactitem}
\item
  Kutepov and Rubanov,
  \emph{Problem Book: Algebra and Elementary Functions}
  (Moscow: Mir, 1978);
\item
  Dorofeev, Potapov, and Rozov,
  \emph{Elementary Mathematics:
    Selected Topics and Problem Solving}
  (Moscow: Mir, 1973);
  \item
    Spivak, \emph{Calculus,}
    Second Edition (Berkeley: Publish or Perish, 1980);
  \item
    Salas and Hille,
    \emph{Calculus: One and Several Variables, Part I,}
    Third Edition (New York: Wiley, 1978);
  \item
    Petit Bois, \emph{Tables of Indefinite Integrals}
    (New York: Dover, 1961);
  \item
    Apostol, \emph{Mathematical Analysis,} Second Edition
    (Reading, Massachusetts: Addison-Wesley, 1974).
\end{compactitem}
  I am able to list these books,
  because I have kept them.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
One of the books was Spivak's \emph{Calculus.}
I read this,
while understanding that Spivak's approach to the subject
was not ``official'' when it differed from our own
(as it did for example
in the development of the real numbers as a complete ordered field,
and later in the definitions of the trigonometric functions).
I might have preferred Spivak's or another approach;
If I ever taught my own course.
I could do things my way.

This is what I have often done,
starting when I was assigned to join two colleagues
in teaching Fundamentals of Mathematics at METU in Ankara
in the fall of 2001-2.
One of those colleagues (who was from Germany)
proposed that he and I write the text of the course.
Part of my own share of the writing
became the text that Ay\c se Berkman used
when teaching Set Theory at METU in the fall of 2003-4.
I revised and rewrote that text
when teaching the set-theory course for myself
in 2006-7, 2008-9, and 2010-1.
When I moved to Istanbul,
I prepared texts in Turkish
for the course Aksiyomatik K\"umeler Kuram\i,
which I have given so far in
2012-3, 2013-4, 2015-6, 2017-8, and 2019-20.

Without going back and reviewing all of those texts
(though they are all on my webpage at Mimar Sinan),
I think the progression has been as follows.
Initially I tried to write down what a \emph{teacher} should know,
or at least what \emph I wanted to know.
I pared down down what I wrote
as I learned the material and the students.
I have come to emphasize ordinal arithmetic,
through computation with Cantor normal forms,
because, as I understand it,
the Turkish national university entrance examinations
are largely computational,
at least as far as mathematics is concerned.

It has also come to seem worthwhile to me
to develop an analogy between the ``well-order'' of the ordinal numbers
and the complete dense ordering of the real numbers.
I am not a set theorist in the sense of publishing new research in the subject,
and I do not expect my students to become set theorists
(though one of them has).
Students are more likely to work with analysis than set theory.
The former had been my own introduction to modern mathematical rigor,
through Mr Brown's two-year course of honors precalculus and calculus.
All students of mathematics learn such techniques
as differentiation and integration,
which are justified by the aforementioned rigor.
Students may forget the techniques,
but they ought to retain an awareness of the possibility of justifying them.
The standards of justification are universal,
precisely because they are the individual property of each of us.

\addchap{Summary}\label{sum}


\begin{compactdesc}
\item[Monday]
  Paradoxes of Russell and Burali-Forti.
  $\upomega$ and $\upomega\sqcup\upomega$
  as well-ordered sets.
  Addition on $\upomega$ is defined by recursion;
  its properties are proved by induction.
  Addition of a natural number to an element of $\upomega\sqcup\upomega$
  in two ways, only one being continuous.
\item[Tuesday]
  Continuity of functions,
  especially increasing functions,
  from ordered sets to ordered sets.
\item[Wednesday]
  The desired properties of $\R$
  lead to Dedekind's construction;
  of $\on$,
  to von Neumann's.
  Transfinite recursion.
  $\alpha+\beta\cong\alpha\sqcup\beta$.
\item[Thursday]
  History of our subject.
  Properties of addition and multiplication of ordinals
  proved by transfinite induction.
  An increasing operation on $\on$ is continuous
  if and only if its value at every limit is the supremum
  of its values at the preceding ordinals.
  $\alpha\cdot\beta\cong\alpha\times\beta$.
  Cantor normal forms of elements of $\upomega\times\upomega$
  and $\upomega^{\upomega}$.
\item[Friday]
  Ordinal exponentiation.
  Cantor normal forms of arbitrary ordinals
  and the generalization to arbitrary bases.
  $\alpha^{\beta}$ is isomorphic to the set of functions
  from $\beta$ to $\alpha$ with finite support.
\item[Saturday]
  Computation with Cantor normal forms.
  Each of $\alpha+\beta$, $\alpha\cdot\beta$, and $\alpha^{\beta}$
  is equipollent with the greater of $\alpha$ and $\beta$,
  if these are infinite.
\end{compactdesc}





\chapter{Monday}

The \emph{ordinal numbers} or \textbf{ordinals}
compose this \emph{linear order}:%%%%%
\footnote{The definition of linear ordering
  is spelled out on page \pageref{lo}.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{equation}\label{eqn:on}
  \left.
  \begin{gathered}
    0,1,2,\dots;\upomega,\upomega+1,\upomega+2,\dots;
    \upomega+\upomega=\upomega\cdot2,\\
    \upomega\cdot2+1,\dots;\upomega\cdot3,\upomega\cdot3+1,\dots;
    \upomega\cdot\upomega=\upomega^2,\\
    \upomega^2+1,\dots;\upomega^2+\upomega,\upomega^2+\upomega+1,\dots;
    \upomega^3,\dots;
    \upomega^{\upomega},\\
    \upomega^{\upomega}+1,\dots,\upomega^{\upomega^{\upomega}},\dots;
    \upepsilon_0,\upepsilon_0+1,\dots;\upepsilon_1,\dots;
    \upomega_1,\dots
  \end{gathered}
  \right\}
\end{equation}
\begin{compactitem}
  \item
$\upomega$ is \emph{omega}, ``large o,''
    the minuscule case of the last letter of the Greek alphabet;
    we shall understand
\begin{equation*}
  \upomega=\{0,1,2,\dots\},
\end{equation*}
the set of \textbf{natural numbers.}
(The set $\{1,2,3,\dots\}$ of \emph{counting numbers}
can be denoted by $\N$.)
\item
$\upepsilon_0$ will be the first solution; $\upepsilon_1$, the next;
to the equation
\begin{equation*}
  \upomega^x=x.
\end{equation*}
\item
  $\upomega_1$ will be the least ordinal $\alpha$ such that the set
\begin{equation*}
  \{x\colon x<\alpha\}
\end{equation*}
is \textbf{uncountable,}
meaning there is no bijection with $\upomega$ or a subset of it.%%%%%
\footnote{People asked about the $\epsilon_x$ and $\upomega_1$,
  so I talked about them.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{compactitem}
Moreover, the ordinals have the following properties:
\begin{compactenum}
%\item
%  There is a first or least one.
\item
  Every $\alpha$ of them has a \textbf{successor,} $\alpha'$ or $\alpha+1$,
  which is the first of those that are greater than it.
\item
  Every set $A$ of them that has no greatest element
  still has a \textbf{supremum}
  or least upper bound, $\sup(A)$.
  \newcounter{onenum}
  \setcounter{onenum}{\value{enumi}}
\end{compactenum}

\begin{theorem}[Burali-Forti Paradox]\label{thm:BF}
  The class of ordinals is not a set.
\end{theorem}

\begin{proof}
  Since every ordinal has a successor,
  the class of ordinals has no supremum,
  so it cannot be a set.
\end{proof}

The class of ordinals is ``too big'' to be a set.
Another example is given by the following.

\begin{theorem}[Russell Paradox]
  The class $\{x\colon x\notin x\}$ is not a set.
\end{theorem}

A technical property of the ordinals is the following.
\begin{compactenum}
  \setcounter{enumi}{\value{onenum}}
\item
  They are \textbf{left-narrow:}%%%%%
  \footnote{In class,
    I did not use this term,
    which is from Levy, I.1(vii), p.\ 33.}
%%%%%%%%%%%%%%%%%%%%%%%%%
  for each $\alpha$ of them,
  the class $\{x\colon x<\alpha\}$
  or $\pred(\alpha)$ is a set.
\end{compactenum}

\begin{theorem}
  The class of ordinals is \textbf{well-ordered:}
  it is left-narrow, and
  every non\-empty set $A$ of them has a least element, $\min(A)$.
\end{theorem}

\begin{proof}
  Let $B$ be a nonempty set of ordinals, and let
  \begin{equation*}
    A=\bigcap_{x\in B}\pred(x)=\{x\colon\Forall y(y\in B\lto y<x)\}.
  \end{equation*}
  This is a set of ordinals,
  so it has a supremum, $\alpha$.
  \begin{compactitem}
  \item
    If $\alpha\notin A$, then it is the least element of $B$.
  \item
    If $\alpha\in A$, then its successor is the least element of $B$.
    \qedhere
  \end{compactitem}
\end{proof}

Conversely, the following are true in every well-ordered class.
\begin{compactenum}
\item
  If $\alpha$ is not the greatest element, then
  \begin{equation*}
    \alpha'=\min\{x\colon\alpha<x\}.
  \end{equation*}
\item
  If $A$ has an upper bound, then
  \begin{equation*}
    \sup(A)=\min\{x\colon\Forall y(y\in A\lto y\leq x)\}.
  \end{equation*}
\end{compactenum}

In $\upomega$, every element is either the least element,
namely $0$, or the successor of an element.

\begin{theorem}
  $\upomega$ admits \textbf{(finite) induction:}
  If $A\subseteq\upomega$ and
  \begin{compactenum}[1)]
  \item
    $0\in A$,
  \item
    $\Forall x(x\in A\lto x'\in A)$,
  \end{compactenum}
  then $A=\upomega$.
\end{theorem}

\begin{proof}
  The least element $\upomega\setminus A$
  can be neither $0$ nor a successor, so there isn't one.
  Therefore $\upomega\setminus A=\emptyset$.
\end{proof}

For any sets $A$ and $B$, we define
\begin{equation*}
  A\sqcup B=(A\times\{0\})\cup(B\times\{1\}),
\end{equation*}
the \textbf{disjoint union} of $A$ and $B$.

\begin{theorem}\label{thm:w+w}
  $\upomega\sqcup\upomega$ is well-ordered
  by the rule
  \begin{equation*}
    (a,e)<(b,f)\liff e<f\lor(e=f\land a<b).
  \end{equation*}
\end{theorem}

\begin{proof}
  In order,
  \begin{equation*}
    \upomega\sqcup\upomega
    =\{(0,0),(1,0),(2,0),\dots;(0,1),(1,1),(2,1),\dots\}.
  \end{equation*}
  Thus $\upomega\sqcup\upomega$ is well-ordered.
Indeed, for nonempty subsets $A$,
\begin{equation*}
  \min(A)=
  \begin{cases}
    (\min\{x\colon(x,0)\in A\},0),&\text{ if }\Exists x(x,0)\in A;\\
    (\min\{x\colon(x,1)\in A\},1),&\text{ if }\Forall x(x,0)\notin A.
  \end{cases}\qedhere
\end{equation*}
\end{proof}

In $\upomega\sqcup\upomega$, $(0,1)$ is neither the least element
  nor the successor of an element.
We call such an element of a well-ordered set a \textbf{limit.}
Thus a limit is an element $a$ such that
\begin{equation*}
  \Exists xx<a\land\Forall x(x<a\lto x'<a).
\end{equation*}
Let us denote this condition by
\begin{equation*}
  \lim(a).
\end{equation*}

\begin{theorem}
  $\upomega\sqcup\upomega$ admits \textbf{transfinite induction:}
  If $A\subseteq\upomega\sqcup\upomega$ and
  \begin{compactenum}[1)]
  \item
    $0\in A$,
  \item
    $\Forall x(x\in A\lto x'\in A)$,
  \item
    $\Forall x(\lim(x)\land\pred(x)\included A\lto x\in A)$,
  \end{compactenum}
  then $A=\upomega$.
\end{theorem}

\begin{proof}
  The least element $(\upomega\sqcup\upomega)\setminus A$
  can be neither $0$, nor a successor, nor a limit.
\end{proof}

\begin{theorem}
  On $\upomega$,
  functions can be defined by \textbf{(finite) recursion:}
  If $A$ is any set, and $b\in A$, and $f\colon A\to A$,
  then a unique function $g$ from $\upomega$ to $A$ exists such that
  \begin{compactenum}[1)]
  \item
    $g(0)=b$,
  \item
    $\Forall xg(x')=f(g(x))$.
  \end{compactenum}
\end{theorem}

\begin{proof}
  If it exists,
  such a function is unique, by induction.
  Likewise,
  for each $n$ in $\upomega$,
  if it exists,
  a function $g_n$ from $\pred(n')$ to $A$
  such that
  \begin{compactenum}[1)]
  \item
    $g_n(0)=b$;
  \item
    $\Forall x(x<n\lto g(x')=f(g(x))$,
  \end{compactenum}
  is unique,
   by induction.
  By induction, $g_n$ does exist for all $n$ in $\upomega$,
  since
  \begin{compactenum}[1)]
  \item
    $g_0$ can be $\{(0,b)\}$,
  \item
    $g_{n'}$ can be $g_n\cup\{(n',f(g_n(n)))\}$.
  \end{compactenum}
  Now we can define
  \begin{equation*}
    g(n)=g_n(n).\qedhere
  \end{equation*}
\end{proof}

Now for each $n$ in $\upomega$ we define the operation
\begin{equation*}
  x\mapsto n+x
\end{equation*}
on $\upomega$ by the rules
\begin{compactenum}[1)]
\item
  $n+0=n$,
\item
  $n+k'=(n+k)'$.
\end{compactenum}
Now we have \textbf{addition} as a binary operation on $\upomega$.

\begin{theorem}\label{thm:+inc}
  For each $n$ in $\upomega$,
  the operation $x\mapsto n+x$ is strictly increasing.
\end{theorem}

\begin{proof}
  We prove
  \begin{equation*}
    k<m\lto n+k<n+m
  \end{equation*}
  by induction on the rightmost letter, $m$.
  \begin{compactenum}
  \item
    Since always $k\not<0$, we conclude
  \begin{equation*}
    k<0\lto n+k<n+0.
  \end{equation*}
\item
  Suppose $k<\ell\lto n+k<n+\ell$.
  Say now $k<\ell'$.  Then $k\leq\ell$.
  There are two cases.
  \begin{compactenum}
  \item
    If $k=\ell$, then $n+k=n+\ell$.
  \item
    If $k<\ell$, then $n+k<n+\ell$ by hypothesis.
  \end{compactenum}
  In either case,
    \begin{align*}
      n+k
      \leq n+\ell
      &<(n+\ell)'&&\text{[definition]}\\
      &=n+\ell'.&&\text{[definition]}\qedhere
    \end{align*}
  \end{compactenum}
\end{proof}

\begin{theorem}\label{thm:+ass}
  Addition on $\upomega$ is associative.
\end{theorem}

\begin{proof}
  We prove
  \begin{equation*}
    (n+k)+m=n+(k+m)
  \end{equation*}
  by induction on $m$.%%%%%
  \footnote{I did not give the remainder of the proof.}
  %%%%%%%%%%%%%%%%%%%%%%%
  \begin{compactenum}
  \item
    By definition,
    \begin{equation*}
      (n+k)+0=n+k=n+(k+0).
    \end{equation*}
  \item
    Suppose
    $(n+k)+\ell=n+(k+\ell)$.  Then
    \begin{align*}
      (n+k)+\ell'
      &=((n+k)+\ell)'&&\text{[definition]}\\
      &=(n+(k+\ell))'&&\text{[hypothesis]}\\
      &=n+(k+\ell)'&&\text{[definition]}\\
      &=n+(k+\ell').&&\text{[definition]} \qedhere     
    \end{align*}
  \end{compactenum}
\end{proof}

\begin{lemma}\label{lem:0}
  On $\upomega$,
  \begin{equation*}
    0+n=n.
  \end{equation*}  
\end{lemma}

\begin{proof}
  We use induction.%%%%%
  \footnote{In class I combined this and the next lemma as one,
    leaving the proof of the first part as an exercise.}
  %%%%%%%%%%%%%%%%%%%%%%%%%%
  \begin{compactenum}
  \item
        By definition,
    \begin{equation*}
      0+0=0.
    \end{equation*}
  \item
    Suppose $0+m=m$.  Then
    \begin{align*}
      0+m'
      &=(0+m)'&&\text{[definition]}\\
      &=m'.&&\text{[hypothesis]}\qedhere
    \end{align*}
  \end{compactenum}
\end{proof}

\begin{lemma}\label{lem:'}
  On $\upomega$,
  \begin{equation*}
    (n+k)'=n'+k.
  \end{equation*}
\end{lemma}

\begin{proof}
  We use induction on $k$.
  \begin{compactenum}
  \item
    By definition,
    \begin{equation*}
      (n+0)'=n'=n'+0.
    \end{equation*}
  \item
    Suppose
    $(n+m)'=n'+m$.
    Then
    \begin{align*}
      (n+m')'
      &=(n+m)''&&\text{[definition]}\\
      &=(n'+m)'&&\text{[hypothesis]}\\
      &=n'+m'.&&\text{[definition]}\qedhere
    \end{align*}
  \end{compactenum}
\end{proof}

\begin{theorem}\label{thm:+comm}
  Addition is commutative on $\upomega$.
\end{theorem}

\begin{proof}
  We prove $n+k=k+n$ by induction on $n$.
  First,
    \begin{align*}
      0+k
      &=k&&\text{[Lemma \ref{lem:0}]}\\
      &=k+0.&&\text{[definition]}
    \end{align*}
    Next, if $m+k=k+m$, then
    \begin{align*}
      m'+k
      &=(m+k)'&&\text{[Lemma \ref{lem:'}]}\\
      &=(k+m)'&&\text{[hypothesis]}\\
      &=k+m'.&&\text{[definition]}\qedhere
    \end{align*}
\end{proof}

\begin{theorem}\label{thm:x+n}
  For each $n$ in $\upomega$,
  the function $x\mapsto x+n$ is strictly increasing.
\end{theorem}

\begin{proof}
  Theorems \ref{thm:+inc} and \ref{thm:+comm}.
\end{proof}

We can embed $\upomega$ in $\upomega\sqcup\upomega$ by the rule
\begin{equation*}
  x\mapsto(x,0).
\end{equation*}
Then we can identify each element of $\upomega$ with its image, but define
\begin{equation*}
  \upomega+n=(n,1).
\end{equation*}
In order then,
  \begin{equation*}
    \upomega\sqcup\upomega
    =\{0,1,2,\dots;\upomega,\upomega+1,\upomega+2,\dots\}.
  \end{equation*}
For each $k$ in $\upomega$,
we extend the operation
\begin{equation*}
  x\mapsto x+k
\end{equation*}
from the domain $\upomega$ to the domain $\upomega\sqcup\upomega$
by defining
\begin{equation*}
  (\upomega+n)+k=\upomega+(n+k).
\end{equation*}
The operation is still strictly increasing.
However,
\begin{equation*}
  \sup\{x+k\colon x<\upomega\}=\upomega,
\end{equation*}
which is strictly less than $\upomega+k$ if $k>0$.
Therefore, as we shall see,
the operation then is not \emph{continuous} at $\upomega$.
If we define
\begin{equation*}
  x\mapsto k+ x
\end{equation*}
on $\upomega\sqcup\upomega$ by
\begin{equation*}
  k+(\upomega+n)=\upomega+n,
\end{equation*}
then the operation is still strictly increasing.
Also,
\begin{equation*}
  \sup\{k+x\colon x<\upomega\}=\upomega=k+\upomega,
\end{equation*}
so the operation \emph{is} continuous at $\upomega$.

\chapter{Tuesday}

To define continuity,
suppose $f$ is a function from a linear order $A$
to a linear order $B$, and $c\in A$.
For example, $A$ and $B$ could be the set of real numbers.
Then $f$ is \textbf{continuous} at $c$,
provided that for all $\epsilon_1$ and $\epsilon_2$ in $B$ such that
\begin{equation*}
  \epsilon_1<f(c)<\epsilon_2,
\end{equation*}
for some $\delta_1$ and $\delta_2$ in $A$ such that
\begin{equation*}
  \delta_1<c<\delta_2,
\end{equation*}
for all $x$ in $A$,
\begin{equation*}
  \delta_1<x<\delta_2\lto  \epsilon_1<f(x)<\epsilon_2.
\end{equation*}
In case $B$ or $A$ has a minimum or maximum,
and $f(c)$ or $c$ is it,
we must allow
\begin{compactitem}
  \item
$\epsilon_1$ or $\delta_1$ to be $-\infty$,
  \item
    $\epsilon_2$ or $\delta_2$ to be $\infty$.
\end{compactitem}
In case $B$ is well-ordered, we shall understand
\begin{align*}
  (-\infty)'&=\min(B),&\max(B)'&=\infty,
\end{align*}
and likewise for $A$.

\begin{theorem}\label{thm:con}
  Suppose $A$ and $B$ are well-ordered,
  $f\colon A\to B$, and $c\in A$.
  \begin{compactenum}
  \item
    If $c$ is the least element or a successor in $A$,
    then $f$ is continuous at $c$.
    \item
      Suppose $c$ is a limit.
      The following are equivalent.
      \begin{compactenum}
        \item
          $f$ is continuous at $c$.
          \item
            For all $\epsilon$ such that $\epsilon<f(c)$,
            for some $\delta$ such that $\delta<c$,
            for all $x$ in $A$,
            \begin{equation*}
              \delta<x<c\lto\epsilon<f(x)\leq f(c).
            \end{equation*}
              \item
            For all $\epsilon$ such that $\epsilon<f(c)$,
            for some $\delta$ such that $\delta<c$,
            \begin{align*}
              \epsilon&<\min_{\delta<x<c}f(x),&
              \sup_{\delta<x<c}f(x)&=f(c).
            \end{align*}
                \end{compactenum}
  \end{compactenum}
\end{theorem}

\begin{proof}
  \begin{asparaenum}
    \item
  If $c$ is not a limit in $A$, we may suppose $c=d'$
  for some $d$ in $\{-\infty\}\cup A$.
  Also $c'\in A\cup\{\infty\}$.
  Thus
  \begin{equation*}
    d<c<c'.
  \end{equation*}
  Moreover,
  \begin{equation*}
    \Forall x(d<x<c'\lto x=c).
  \end{equation*}
 Thus for all $\epsilon_1$ and $\epsilon_2$ in $B$ such that
\begin{equation*}
  \epsilon_1<f(c)<\epsilon_2,
\end{equation*}
for all $x$ in $A$,
\begin{equation*}
  d<x<c'\lto  \epsilon_1<f(x)<\epsilon_2.
\end{equation*}
Therefore $f$ is continuous at $c$.
\item
  Now suppose $c$ is a limit.
  \begin{compactenum}
  \item
    Suppose $f$ is continuous at $c$, and $\epsilon<f(c)$.
    For some $\delta$ such that $\delta<c$,
    for all $x$ in $A$,
    \begin{equation*}
      \delta<x<c'\lto\epsilon<f(x)<f(c)'
    \end{equation*}
    and therefore
    \begin{equation*}
        \delta<x\leq c\lto\epsilon<f(x)\leq f(c).
    \end{equation*}
              \item
                Suppose that,
                for all $\epsilon$ such that $\epsilon<f(c)$,
            for some $\delta$ such that $\delta<c$,
            \begin{equation*}
              \Forall x(\delta<x<c\lto\epsilon<f(x)\leq f(c)).
            \end{equation*}
            This means precisely
            \begin{align*}
              \epsilon&<\min_{\delta<x<c}f(x),&
              \sup_{\delta<x<c}f(x)&\leq f(c).
            \end{align*}
            Suppose if possible that,
            for all $\delta$ such that $\delta<c$,
            \begin{equation*}
              \sup_{\delta<x<c}f(x)< f(c).
            \end{equation*}
            Now let $\epsilon=\sup_{\delta<x<c}f(x)$.
            By our hypothesis,
            for some $d$ such that $d<c$,
            \begin{equation*}
              \Forall x(d<x<c\lto\epsilon<f(x)\leq f(c)).
            \end{equation*}
            Since $c$ is a limit,
            there is $a$ in $A$ such that $\max(d,\delta)<a<c$.
            Then
            \begin{equation*}
              f(a)\leq\sup_{\delta<x<c}f(x)=\epsilon<f(a),
            \end{equation*}
            which is absurd.
          \item
            Suppose
            for all $\epsilon$ such that $\epsilon<f(c)$,
            for some $\delta$ such that $\delta<c$,
            \begin{align*}
              \epsilon&<\min_{\delta<x<c}f(x),&
              \sup_{\delta<x<c}f(x)&=f(c).
            \end{align*}
            Then
            \begin{equation*}
              \Forall x(\delta<x<c'\lto\epsilon<f(x)\leq f(c)<f(c)'.
            \end{equation*}
Thus $f$ is continuous at $c$.\qedhere
  \end{compactenum}
  \end{asparaenum}
\end{proof}

\begin{corollary}
  Under the conditions of the theorem,
  if $f$ is also increasing, then
  it is continuous at a limit $c$ if and only if
  \begin{equation*}
    \sup_{x<c}f(x)=f(c).
  \end{equation*}
\end{corollary}

The set $\upomega\sqcup\upomega$
is $\upomega\times\{0,1\}$,
a subset of $\upomega\times\upomega$.
This is well-ordered by the rule of Theorem \ref{thm:w+w}.
Let us use the notation
\begin{equation*}
  \upomega\cdot n+k=(k,n).
\end{equation*}
The elements $\upomega\cdot n$ are limits when $n>0$.
Now we can define
\begin{equation}\label{eqn:ww}
  (\upomega\cdot n+k)+(\upomega\cdot m+\ell)
  =
  \begin{cases}
    \upomega\cdot n+(k+\ell),&\text{ if }m=0,\\
    \upomega\cdot(n+m)+\ell,&\text{ if }m>0.
  \end{cases}
\end{equation}

\begin{theorem}
  For each $\alpha$ in $\upomega\times\upomega$,
  the operation
  \begin{equation*}
    x\mapsto\alpha+x
  \end{equation*}
  is strictly increasing and continuous;
  the operation
  \begin{equation*}
    x\mapsto x+\alpha
  \end{equation*}
  is increasing, though not strictly,
  and is not continuous unless $\alpha=0$.
\end{theorem}

We could also define
\begin{equation*}
  (\upomega\cdot n+k)\oplus(\upomega\cdot m+\ell)
  =\upomega\cdot(n+m)+(k+\ell).
\end{equation*}
Then $\oplus$ is commutative and associative,
but continuous in neither argument.

\chapter{Wednesday}

What \emph{is} an ordinal number?
Well, what is an real number?
To do real analysis,
all one need know is that the real numbers together compose a
\emph{complete ordered field,} $\R$.
That this is \textbf{complete} means every nonempty subset with an upper bound
has a least upper bound, or supremum.

Every ordered field includes the ordered field $\Q$
of rational numbers.
In an ordered field,
if $\Q$ has an upper bound $a$,
then $a-1$ is also an upper bound;
therefore there is no least upper bound.

Ordered fields in which $\Q$ is bounded do exist.
For example, if
\begin{gather*}
  \Q[X]=\{\text{polynomials in $X$ over $\Q$}\},\\
  \Q(X)=\left\{\frac fg\colon f\in\Q[X]\land g\in\Q[X]\setminus\{0\}\right\},
\end{gather*}
this field can be ordered by the rule
\begin{equation*}
  \frac{a_0+a_1X+\dots+a_mX^m}{b_0+b_1X+\dots+b_nX^n}>0
  \liff \frac{a_m}{b_n}>0.
\end{equation*}
Hence for all $a$ in $\Q$, $X-a>0$, and so $X>a$.
Thus $X$ is an upper bound of $\Q$.

An ordered field in which $\Q$ has no upper bound
is called \textbf{Archimedean.}
Being complete,
$\R$ must be Archimedean.
Because of this, $\Q$ is \textbf{dense} in $\R$:
between any two real numbers lies a rational number.
Therefore the function $f$ on $\R$ given by
\begin{equation*}
  f(\alpha)=\{x\in\Q\colon x<\alpha\}
\end{equation*}
is injective.
Moreover, its range is the set of subsets $A$ of $\Q$ such that
\begin{gather*}
  \emptyset\pincluded A\pincluded\Q,\\
  \Forall x\Forall y(x<y\land y\in A\lto x\in A).
\end{gather*}
Thus we can define the range of $f$ without having $f$ or $\R$.
This means we can \emph{define} $\R$ as the range of $f$.

One then must extend the definitions of addition and multiplication on $\Q$
to $\R$.
For every $a$ in $\Q$, the functions $x\mapsto a+x$
and $x\mapsto a\cdot x$ are continuous on $\Q$;
they will remain so on $\R$.

To do ordinal analysis,
all we need know is that the ordinal numbers together compose a class $\on$
with certain properties:
\begin{compactenum}\label{on-props}
\item
  $\on$ is \textbf{well-ordered.}  This means:
  \begin{compactenum}
  \item
    $\on$ is \label{lo}\textbf{linearly ordered,}
so that for any $\alpha$, $\beta$, and $\gamma$ in $\on$,
\begin{gather*}
  \alpha\not<\alpha,\\
  \alpha<\beta\land \beta<\gamma\lto \alpha<\gamma,\\
  \alpha\leq \beta\lor \alpha>\beta.
\end{gather*}
\item
    every nonempty subset $A$ of $\on$ has a least element, $\min(A)$.
  \item
    the class $\pred(\alpha)$ or $\{x\colon x<\alpha\}$
    of predecessors of a given ordinal $\alpha$ is a set.%%%%%
    \footnote{It follows now that every nonempty \emph{class}
      of ordinals has a least element,
      but I did not spell this out.}
    %%%%%%%%%%%%%%%%%%%%%%%%%%%
  \end{compactenum}
\item
  $\on$ is non-empty, so it has a least element, $0$.
\item
  $\on$ has no greatest element, so
  every element $\alpha$ of $\on$ has a successor, $\alpha'$,
  namely $\min\{x\colon x>\alpha\}$. 
\item
  Every subset $A$ of $\on$ has an upper bound
  and therefore a supremum, $\sup(A)$,
  namely
  \begin{equation*}
    \min\{x\colon\Forall y(y\in A\lto y\leq x)\}.
  \end{equation*}
\item
  $\on$ contains limits,
  namely elements that are neither $0$ nor successors;
  the least limit is $\upomega$.
\end{compactenum}


Can we prove that there are more limits than $\upomega$?
As we did from $\upomega$ to $\upomega\sqcup\upomega$,
we recursively define
$x\mapsto\upomega+x$ from the subset $\pred(\upomega)$ of $\on$
to $\on$ itself by
\begin{align*}
  \upomega+0&=\upomega,&\upomega+x'&=(\upomega+x)'.
\end{align*}
Then $\sup\{\upomega+x\colon x<\upomega\}$
is the next limit after $\upomega$.
It exists by the \textbf{Replacement Axiom:}
the image of a set under a function is still a set.

For any $\alpha$ in $\on$, we define $x\mapsto\alpha+x$
by \emph{transfinite recursion}:
\begin{compactenum}
  \item
  $\alpha+0=\alpha$.
  \item
    $\alpha+\beta'=(\alpha+\beta)'$.
  \item
    $\lim(\gamma)\lto\alpha+\gamma=\sup\{\alpha+x\colon x<\gamma\}$.
\end{compactenum}
We can do this by the following.

\begin{theorem}[Transfinite Recursion]\label{thm:tr}
  If $\alpha\in\on$ and $\bm F$ is an operation on $\on$,
  then a unique operation $\bm G$ on $\on$
  exists such that
  \begin{compactenum}[1)]
  \item
    $\bm G(0)=\alpha$,
  \item
    $\Forall x(\bm G(x')=\bm F(\bm G(x)))$,
  \item
    $\Forall x(\lim(x)\lto\bm G(x)=\sup(\bm G[\pred(x)])$.
  \end{compactenum}
\end{theorem}

\begin{proof}
  By transfinite induction,
  there is at most one such $\bm G$.
  For the same reason,
  for each $\beta$ in $\on$, there is at most one function $g_{\beta}$
  from $\pred(\beta')$ to $\on$ with the properties of $\bm G$,
  and also
  \begin{equation*}
\delta\leq\gamma\leq\beta\lto g_{\beta}(\delta)=g_{\gamma}(\delta).
  \end{equation*}
  Again by transfinite induction,
  there is at least one such $g_{\beta}$ for each $\beta$;
  for we can let
  \begin{gather*}
    g_0=\{(0,\alpha)\},\\
    g_{\beta'}=g_{\beta}\cup\{(\beta',\bm F(g_{\beta}(\beta)))\},\\
    \lim(\gamma)\lto g_{\gamma}
    =\bigcup\{g_x\colon x<\gamma\}
    \cup\{(\gamma,\sup\{g_x(x)\colon x<\gamma\})\}.
  \end{gather*}
  Then $\bm G$ can be $x\mapsto g_x(x)$.
\end{proof}

By a modification of the proof,
there is $\bm G$ such that
  \begin{compactenum}[1)]
  \item
    $\bm G(0)=\emptyset$,
  \item
    $\Forall x\bm G(x')=\bm G(x)\cup\{\bm G(x)\}$,
  \item
    $\Forall x(\lim(x)\lto\bm G(x)=\bm G[\pred(x)])$.
  \end{compactenum}
  In this case,
  \begin{equation*}
    \Forall x(\bm G(x)=\bm G[\pred(x)]).
  \end{equation*}
  Then $\bm G[\on]$ consists of sets that are
  \begin{compactitem}
  \item
    well-ordered by $\in$,
  \item
    \emph{transitive,}
  \end{compactitem}
where a set $A$ is \textbf{transitive} if
\begin{equation*}
  \Forall x\Forall y(y\in x\land x\in A\lto y\in A),
\end{equation*}
that is,
\begin{equation*}
  \Forall x(x\in A\lto x\included A).
\end{equation*}
One can show that \emph{every} transitive set
that is well-ordered by $\in$ belongs to the range of $\bm G$.
Thus we can define $\on$ as this range.
Now each $\alpha$ in $\on$ is $\pred(\alpha)$;
also,
\begin{equation*}
  \alpha'=\alpha\cup\{\alpha\}.
\end{equation*}
Hence
\begin{align*}
  0&=\emptyset,&1=0'&=\{0\},&2=1'&=\{0,1\},
\end{align*}
and so on.
Also,
  if $A$ is a set of ordinals, then
  \begin{equation*}
    \sup(A)=\bigcup A=\{x\colon\Exists y(y\in A\land x\in y)\}.
  \end{equation*}

\begin{theorem}
  For all $\alpha$ and $\beta$ in $\on$,
  \begin{equation*}
    \alpha+\beta\cong\alpha\sqcup\beta,
  \end{equation*}
  where $\alpha\sqcup\beta$ is well-ordered by the rule,
  \begin{equation*}
    (a,b)<(c,d)\liff b<d\lor (b=d\land a<c).
  \end{equation*}
\end{theorem}

\begin{proof}
  Since $\alpha+\beta=\alpha\cup\{\alpha+x\colon x<\beta\}$,
  the map
    \begin{equation*}
    x\mapsto
    \begin{cases}
      (x,0),&\text{ if }x<\alpha,\\
      (y,1),&\text{ if }x=\alpha+y<\alpha+\beta
    \end{cases}
    \end{equation*}
    is an order-preserving bijection from
  $\alpha+\beta$ to $\alpha\sqcup\beta$.
\end{proof}

We know from yesterday that $x\mapsto\alpha+x$ is always continuous.
What is the least positive ordinal, after $\upomega$,%%%%%
\footnote{I forgot this condition in class.}
on which $(x,y)\mapsto x+y$ is closed?

\chapter{Thursday}

Some history:
\begin{compactdesc}
\item[Archimedes] (died 212 \textsc{b.c.e.}):
  examples of integral calculus
\item[Newton, Leibniz]
  (born 1642, 1646): calculus
\item[Dedekind] (b.\ 1831): definition of $\R$ (discovered 1858,
  published 1872)
\item[Cantor] (b.\ 1845): ordinals beyond $\upomega$ (1869)
\item[Zermelo] (b. 1871): most of our set-theory axioms (1908)
\item[Skolem, Fraenkel] (b.\ 1887, 1891): the Replacement Axiom (1922)
  \item[von Neumann] (b. 1903): definition of $\on$ (1923)
\end{compactdesc}

Yesterday we defined addition on $\on$ by transfinite recursion.
We proved the following on Monday, as Theorem \ref{thm:+inc},
for addition on $\upomega$.

\begin{theorem}\label{thm:a+x}
  For each $\alpha$ in $\on$, the operation $x\mapsto\alpha+x$ on $\on$
  is strictly increasing.
\end{theorem}

\begin{proof}
  We prove
  \begin{equation*}
    \beta<\gamma\lto\alpha+\beta<\alpha+\gamma
  \end{equation*}
  by transfinite induction on $\gamma$.
  The first and limit steps are just as for Theorem \ref{thm:+inc}:
  \begin{compactenum}
  \item
    The claim is true when $\gamma=0$.
  \item
    If, for some $\delta$, the claim is true when $\gamma=\delta$,
    then it is true when $\gamma=\delta'$.
  \end{compactenum}
  For the third step, the limit step,
  we suppose $\delta$ is a limit and the claim is true whenever $\gamma<\delta$.
  Suppose also $\beta<\delta$.
  Then
  \begin{equation*}
    \beta<\gamma<\delta
  \end{equation*}
  for some $\gamma$ (for example, $\gamma=\beta'$).  Therefore
  \begin{equation*}
    \alpha+\beta<\alpha+\gamma\leq\sup_{x<\delta}(\alpha+x)=\alpha+\delta,
  \end{equation*}
  so our claim is true when $\gamma=\delta$.
  This completes the proof by transfinite induction.
\end{proof}

Now $x\mapsto\alpha+x$ is also continuous,
by Theorem \ref{thm:con} and its corollary from Tuesday:
if an operation $\bm F$ on $\on$
(or from any well-ordered set or class to a well-ordered set or class)
is increasing,
then $\bm F$ is continuous if and only if, at every limit $\gamma$,
\begin{equation*}
  \bm F(\gamma)=\sup_{x<\gamma}\bm F(x)=\sup\bm F[\gamma].
\end{equation*}
We proved the following as Theorem \ref{thm:+ass},
for addition on $\upomega$.

\begin{theorem}
  Addition on $\on$ is associative.
\end{theorem}

\begin{proof}
  We prove
    \begin{equation*}
      \alpha+(\beta+\gamma)=(\alpha+\beta)+\gamma
    \end{equation*}
    by transfinite induction on $\gamma$.
    The first two steps are just as for Theorem \ref{thm:+ass}.
    Suppose now $\delta$ is a limit,
    and the claim is true whenever $\gamma<\delta$.
    Then
    \begin{align*}
      \alpha+(\beta+\delta)
      &=\alpha+\sup_{x<\delta}(\beta+x)&&\text{[definition]}\\
      &=\sup_{x<\delta}(\alpha+(\beta+x))&&\text{[Theorem \ref{thm:norm}]}\\
      &=\sup_{x<\delta}((\alpha+\beta)+x)&&\text{[hypothesis]}\\
      &=(\alpha+\beta)+\delta.&&\text{[definition]}\qedhere
    \end{align*}
\end{proof}

Here we have used the following.

\begin{theorem}\label{thm:norm}
  Suppose
  \begin{compactitem}
    \item
      $\bm F$ is an increasing, continuous operation on $\on$,
      \item
        $A$ is a nonempty subset of $\on$,
      \item
        $\alpha=\sup(A)$.
  \end{compactitem}
  \begin{compactenum}
  \item
    If $\alpha\notin A$, then
    \begin{equation*}
\sup\bm F[A]=\sup\bm F[\alpha].      
    \end{equation*}
    \item
In any case,
  \begin{equation*}
    \bm F(\alpha)=\sup\bm F[A].
  \end{equation*}
  \end{compactenum}
\end{theorem}

  \begin{proof}
    The second part is easy when $\alpha\in A$.
  Suppose $\alpha\notin A$.
  Then $\alpha$ must be a limit, so,
  since $\bm F$ is increasing and continuous,
  \begin{equation*}
    \bm F(\alpha)=\sup\bm F[\alpha].
  \end{equation*}
  The second part now follows from the first.
  Since $A\included\alpha$ and $\bm F$ is increasing,
  \begin{equation*}
    \sup\bm F[A]\leq\sup\bm F[\alpha].
  \end{equation*}
  When $\beta<\alpha$, then $\beta<\gamma$ for some $\gamma$ in $A$,
  and therefore, again since $\bm F$ is increasing,
  \begin{equation*}
    \sup\bm F[\alpha]\leq\sup\bm F[A].\qedhere
  \end{equation*}
  \end{proof}

Note that
\begin{equation*}
  \alpha+1=\alpha+0'=(\alpha+0)'=\alpha'.
\end{equation*}
Thus
\begin{equation*}
  1+\upomega=\sup_{x<\upomega}(1+x)=\upomega<\upomega'=\upomega+1,
\end{equation*}
so addition is not commutative;
likewise, for all $n$ in $\upomega$,
\begin{equation*}
  n+\upomega=\upomega.
\end{equation*}

The following generalizes Lemma \ref{lem:0}
(used to prove Theorem \ref{thm:+comm},
that addition is commutative on $\upomega$).

\begin{theorem}\label{thm:0}
  For all $\alpha$ in $\on$,
  \begin{equation*}
    0+\alpha=\alpha.
  \end{equation*}
\end{theorem}

\begin{proof}
  Transfinite induction.
\end{proof}

The following is the version of Theorem \ref{thm:x+n}
(that $x\mapsto x+n$ is strictly increasing on $\upomega$)
for $\on$.

  \begin{theorem}\label{thm:x+a}
    For all $\alpha$ in $\on$, the operation $x\mapsto x+\alpha$
    is increasing, that is,
    \begin{equation*}
      \beta<\gamma\lto\beta+\alpha\leq\gamma+\alpha.
    \end{equation*}
  \end{theorem}

  \begin{proof}
    Transfinite induction on $\alpha$.
  \end{proof}

  It follows from Theorems \ref{thm:a+x} and \ref{thm:x+a}
  that $\alpha$ is closed under addition
  if (and only if) it is closed under $x\mapsto x+x$.
  This operation is $x\mapsto x\cdot2$
  by the following definition.
\begin{compactenum}
\item
  $\alpha\cdot0=0$.
\item
  $\alpha\cdot\beta'=\alpha\cdot\beta+\alpha$.
\item
  $\lim(\gamma)\lto\alpha\cdot\gamma=\sup\{\alpha\cdot x\colon x<\gamma\}$.
\end{compactenum}
By Theorem \ref{thm:0},
\begin{gather*}
  \alpha\cdot1=\alpha\cdot0'=\alpha\cdot0+\alpha=0+\alpha=\alpha,\\
  \alpha\cdot2=\alpha\cdot1'=\alpha\cdot1+\alpha=\alpha+\alpha,
\end{gather*}
and so on.

\begin{theorem}
  For all $\alpha$ in $\on$,
  \begin{compactenum}[1)]
    \item
      $0\cdot\alpha=0$,
    \item
      $1\cdot\alpha=\alpha$.
  \end{compactenum}
\end{theorem}

\begin{proof}
  Transfinite induction.
\end{proof}

The operation
$x\mapsto\alpha\cdot x$ is now
\begin{compactitem}
  \item
    increasing and continuous when $\alpha=0$;
  \item
    strictly increasing and continuous when $\alpha=1$.
\end{compactitem}
It is
strictly increasing and continuous whenever $\alpha>1$,
by an analogue of Theorem \ref{thm:a+x}.

\begin{theorem}
  For all $\alpha$, $\beta$, and $\gamma$ in $\on$,
  \begin{gather*}
    \alpha\cdot(\beta\cdot\gamma)=(\alpha\cdot\beta)\cdot\gamma,\\
    \alpha\cdot(\beta+\gamma)=\alpha\cdot\beta+\alpha\cdot\gamma.
  \end{gather*}
\end{theorem}

\begin{proof}
  Induction on $\gamma$ in either case.
\end{proof}

Multiplication is not commutative, because for example
for all $n$ in $\upomega$, if $n>1$, then
\begin{equation*}
  n\cdot\upomega=\sup_{x<\upomega}(n\cdot x)=\upomega=\upomega\cdot1
  <\upomega\cdot n.
\end{equation*}

\begin{theorem}
  For all $\alpha$ and $\beta$ in $\on$,
  \begin{equation*}
    \alpha\cdot\beta\cong\alpha\times\beta,
  \end{equation*}
  where $\alpha\times\beta$ is well-ordered by the rule,
  \begin{equation*}
    (a,b)<(c,d)\liff b<d\lor (b=d\land a<c).
  \end{equation*}
\end{theorem}

\begin{proof}
  $\alpha\cdot\beta=\{\alpha\cdot y+x\colon x<\alpha\land y<\beta\}$,
  and the map
  \begin{equation*}
    \alpha\cdot y+x\mapsto(x,y)
    \end{equation*}
    is a well-defined order-preserving bijection from
  $\alpha\cdot\beta$ to $\alpha\times\beta$.
\end{proof}

If $\gamma<\upomega\cdot\upomega$, then
\begin{equation*}
  \gamma=\upomega\cdot b+a
\end{equation*}
for some $a$ and $b$ in $\upomega$.  Then
$\upomega\cdot b+a$ is the \textbf{Cantor normal form} of $\gamma$.
Compare with how every number less than $10\cdot10$ can be written as
\begin{equation*}
  10\cdot b+a
\end{equation*}
for some $a$ and $b$ in $10$ (which is $\{0,1,2,\dots,9\}$).

We add Cantor normal forms of elements of $\upomega\cdot\upomega$
by the rule \eqref{eqn:ww} from Tuesday.

\begin{theorem}
  For each $\alpha$ in $\omega$,
  the product $\alpha\cdot\upomega$ is closed under addition.
\end{theorem}

\begin{proof}
  Suppose $\beta<\alpha\cdot\upomega$.  Then
  \begin{equation*}
    \beta<\alpha\cdot n
  \end{equation*}
  for some $n$ in $\upomega$,
  and thus
  \begin{equation*}
    \beta\cdot2<\alpha\cdot n\cdot 2<\alpha\cdot\upomega.\qedhere
  \end{equation*}
\end{proof}

Thus $0$, $\upomega$, and $\upomega\cdot\upomega$ are closed under addition.
Here $\upomega\cdot\upomega$ is $\upomega^2$ by the following definition:
\begin{compactenum}
\item
  $\alpha^0=1$.
\item
  $\alpha^{\beta'}=\alpha^{\beta}\cdot\alpha$.
\item
  $\lim(\gamma)\lto\alpha^{\gamma}=\sup\{\alpha^x\colon 0<x<\gamma\}$.
\end{compactenum}
We shall see that every nonzero element of $\upomega^{\upomega}$
has a Cantor normal form
\begin{equation*}
  \upomega^{n_0}\cdot k_0+\upomega^{n_1}\cdot k_1+\dots+\upomega^{n_m}\cdot k_m,
\end{equation*}
where
\begin{gather*}
  \upomega>n_0>n_1>\dots>n_m,\\
  0<k_0<\upomega\land0<k_1<\upomega\land\dots\land0<k_m<\upomega.
\end{gather*}
The same will be true for \emph{every} ordinal,
if we remove the requirement $\upomega>n_0$.

\chapter{Friday}

The following are now strictly increasing and continuous:
\begin{compactitem}
  \item
    $x\mapsto\alpha+x$ for all $\alpha$,
  \item
    $x\mapsto\alpha\cdot x$ when $\alpha>0$,
\item
  $x\mapsto\alpha^x$ when $\alpha>1$.
\end{compactitem}
Also
\begin{gather*}
  \alpha^0=1,\\
  \alpha^1=\alpha^{0'}=\alpha^0\cdot\alpha=1\cdot\alpha=\alpha,\\
  \alpha^2=\alpha^{1'}=\alpha^1\cdot\alpha=\alpha\cdot\alpha.
\end{gather*}

\begin{theorem}
  For all $\alpha$ in $\on$,
  \begin{compactenum}
  \item
    $0^{\alpha}=0$ if $\alpha>0$.
  \item
    $1^{\alpha}=1$.
  \end{compactenum}
\end{theorem}

\begin{proof}
  Induction.
\end{proof}

\begin{theorem}
  For all $\alpha$, $\beta$, and $\gamma$ in $\on$,
  \begin{gather*}
    \alpha^{\beta+\gamma}=\alpha^{\beta}\cdot\alpha^{\gamma},\\
    \alpha^{\beta\cdot\gamma}=(\alpha^{\beta})^{\gamma}.
  \end{gather*}
\end{theorem}

\begin{proof}
  Induction on $\gamma$.
\end{proof}

Yesterday we could assign to each element $\gamma$ of $\upomega^2$
a Cantor normal form $\upomega\cdot n+m$ as follows.
\begin{compactenum}
\item
  If $\gamma<\upomega$, we are done.
  Suppose now
    \begin{equation*}
      \upomega\leq\gamma<\upomega^2
      =\upomega\cdot\upomega.
    \end{equation*}
  \item
    We let
    \begin{equation*}
      n=\sup\{x\colon\upomega\cdot x\leq\gamma\},
    \end{equation*}
    a nonzero element of $\upomega$, and then
  \begin{equation*}
    \upomega\cdot n\leq\gamma<\upomega\cdot n'=\upomega\cdot n+\upomega.
  \end{equation*}
\item
  We let
  \begin{equation*}
    m=\sup\{x\colon\upomega\cdot n+x\leq\gamma\},
  \end{equation*}
  an element of $\upomega$, and then
  \begin{equation*}
    \gamma=\upomega\cdot n+m.
  \end{equation*}
\end{compactenum}

To find the Cantor normal form of an arbitrary ordinal,
we need to know that it is bounded by a power of $\upomega$.
For this, we use the following.

\begin{theorem}\label{thm:xa}
  For all $\alpha$ in $\on$, $x\mapsto x\cdot\alpha$ is increasing.
\end{theorem}

\begin{proof}
  Induction on $\alpha$.
\end{proof}

\begin{lemma}\label{lem:a}
  If $\alpha\geq2$, then for all $\gamma$ in $\on$,
  \begin{equation*}
    \gamma\leq\alpha^{\gamma}.
  \end{equation*}
\end{lemma}

\begin{proof}
  Induction.
  \begin{compactenum}
  \item
    $0<1=\alpha^0$.
  \item
    Suppose
    $\beta<\alpha^{\beta}$ for some $\beta$.
    \begin{compactenum}
    \item
      If $\beta=0$, then $\beta'=1<\alpha=\alpha^{\beta'}$.
    \item
      If $\beta>0$, then by Theorem \ref{thm:xa},
    \begin{equation*}
      \beta'=\beta+1\leq\beta+\beta=\beta\cdot2
      \leq\beta\cdot\alpha
      \leq\alpha^{\beta}\cdot\alpha
      =\alpha^{\beta'}.
    \end{equation*}
    \end{compactenum}
  \item
    Suppose $\beta$ is a limit and the claim is true when $\gamma<\beta$.
    Then
    \begin{equation*}
      \beta=\sup_{x<\beta}x\leq\sup_{x<\beta}(\alpha^x)=\alpha^{\beta}.\qedhere
    \end{equation*}
  \end{compactenum}
\end{proof}

We can now find the Cantor normal form
of an arbitrary nonzero $\gamma$ in $\on$ as follows.
More generally, instead of $\upomega$ as a base,
we can use an arbitrary $\alpha$, as long as $\alpha>1$.
\begin{compactenum}
  \item
We know from Lemma \ref{lem:a} that
\begin{equation*}
  \gamma<\alpha^{\gamma'},
\end{equation*}
and therefore $\gamma'$ is an upper bound
of $\{x\colon\alpha^x\leq\gamma\}$,
which is also nonempty, because it contains $0$.
We let
\begin{equation*}
  \beta_1=\sup\{x\colon\alpha^x\leq\gamma\},
\end{equation*}
and then, by Theorem \ref{thm:norm},
\begin{multline*}
  \alpha^{\beta_1}
  =\alpha^{\sup\{x\colon\alpha^x\leq\gamma\}}\\
  =\sup\{\alpha^x\colon\alpha^x\leq\gamma\}
  \leq\gamma
  <\alpha^{\beta_1{}'}
  =\alpha^{\beta_1}\cdot\alpha.
\end{multline*}
\item
  We let
  \begin{equation*}
    \alpha_1=\sup\{x\colon\alpha^{\beta_1}\cdot x\leq\gamma\},
  \end{equation*}
  a nonzero element of $\alpha$, and then,
  again by Theorem \ref{thm:norm},
  \begin{multline*}
    \alpha^{\beta_1}\cdot \alpha_1
    =\alpha^{\beta_1}\cdot\sup\{x\colon\alpha^{\beta_1}\cdot x\leq\gamma\}\\
    =\sup\{\alpha^{\beta_1}\cdot x\colon\alpha^{\beta_1}\cdot x\leq\gamma\}
    \leq\gamma\\
    <\alpha^{\beta_1}\cdot \alpha_1{}'
    =\alpha^{\beta_1}\cdot \alpha_1+\alpha^{\beta_1}.
  \end{multline*}
\item
We let
\begin{equation*}
  \delta=\sup\{x\colon\alpha^{\beta_1}\cdot \alpha_1+x\leq\gamma\},
\end{equation*}
an element of $\alpha^{\beta_1}$,
and then,
  again by Theorem \ref{thm:norm},
  \begin{multline*}
    \alpha^{\beta_1}\cdot \alpha_1+\delta
    =\alpha^{\beta_1}\cdot \alpha_1+\sup\{x\colon\alpha^{\beta_1}\cdot \alpha_1+x\leq\gamma\}\\
    =\sup\{\alpha^{\beta_1}\cdot \alpha_1+x\colon\alpha^{\beta_1}\cdot \alpha_1+x\leq\gamma\}
    \leq\gamma\\
    <\alpha^{\beta_1}\cdot \alpha_1+\delta'
    =(\alpha^{\beta_1}\cdot \alpha_1+\delta)'.
  \end{multline*}
Thus
\begin{align*}
  \gamma&=\alpha^{\beta_1}\cdot \alpha_1+\delta,&
  \delta&<\alpha^{\beta_1}.
\end{align*}
\end{compactenum}
If $\delta>0$,
then we apply to $\delta$ the same process that we did to $\gamma$.
Ultimately we obtain, for some $m$ in $\upomega$, the expansion
\begin{equation}\label{eqn:cnf}
  \gamma=\alpha^{\beta_1}\cdot\alpha_1+\alpha^{\beta_2}\cdot\alpha_2
  +\dots+\alpha^{\beta_m}\cdot\alpha_m,
\end{equation}
where
\begin{align*}
  \beta_1&>\beta_2>\dots>\beta_m,&
  \bigwedge_{1\leq j\leq m}\alpha>\alpha_j&>0.
\end{align*}
The expansion has finitely many terms, since $\on$ is well-ordered,
so the strictly decreasing sequence of $\beta_j$ must end.
If $m=0$, the expansion is $0$.

We have shown
\begin{align*}
  \alpha+\beta&\cong\alpha\sqcup\beta,&
  \alpha\cdot\beta&\cong\alpha\times\beta.
\end{align*}
Now let
\begin{equation*}
  {}^{\beta}\alpha=\{\text{functions from $\beta$ to $\alpha$}\}.
\end{equation*}
Then we have established a function $f\mapsto f_{\gamma}$
from $\alpha^{\beta}$ to ${}^{\beta}\alpha$, where,
if $\gamma$ is as in \eqref{eqn:cnf}, with $\beta>\beta_1$,
then
\begin{equation*}
  f_{\gamma}(x)=
  \begin{cases}
    \alpha_j,&\text{ if }x=\beta_j,\\
    0,&\text{ otherwise}.
  \end{cases}
\end{equation*}
The function is injective,
briefly because all of the functions mentioned at the beginning of today
are strictly increasing.
The range of the function is
\begin{equation*}
  \bigl\{f\in{}^{\beta}\alpha\colon
  \{x\in\beta\colon f(x)\neq0\}\text{ is finite}\bigr\},
\end{equation*}
and we can well-order this so that it is isomorphic to $\alpha^{\beta}$.


\chapter{Saturday}

We develop some rules for computing with Cantor normal forms.
We have already effectively proved the following.

\begin{lemma}\label{lem:sol}
  If $\alpha\leq\beta$, then the equation
  \begin{equation*}
    \alpha+x=\beta
  \end{equation*}
  is solved by $\sup\{x\colon\alpha+x\leq\beta\}$.
\end{lemma}

\begin{proof}
  Letting
    $\gamma=\sup\{x\colon\alpha+x\leq\beta\}$,
  We compute
  \begin{multline*}
    \alpha+\gamma
    =\alpha+\sup\{x\colon\alpha+x\leq\beta\}\\
    =\sup\{\alpha+x\colon\alpha+x\leq\beta\}
    \leq\beta
    <\alpha+\gamma'
    =(\alpha+\gamma)',
  \end{multline*}
  so $\alpha+\gamma=\beta$.
\end{proof}

\begin{lemma}\label{lem:n+wa}
  If $\alpha>0$ and $n<\upomega$,
  then $n+\upomega^{\alpha}=\upomega^{\alpha}$.
\end{lemma}

\begin{proof}
  \begin{asparaenum}
    \item
      We know the claim is true when $\alpha=1$.
      \item
  Hence, when $\beta\geq1$,
  \begin{equation*}
    n+\upomega^{\beta'}\leq\upomega^{\beta}+\upomega^{\beta+1}
    =\upomega^{\beta}\cdot(n+\upomega)
    =\upomega^{\beta'}.
  \end{equation*}
  (This did not require an inductive hypothesis.)
  \item
  If $\beta$ is a limit and the claim is true when $\alpha<\beta$,
  then (in the standard way)
  \begin{equation*}
    n+\upomega^{\beta}
    =n+\sup_{x<\beta}\upomega^x
    =\sup_{x<\beta}(n+\upomega^x)
    =\sup_{x<\beta}\upomega^x
    =\upomega^{\beta}.\qedhere
  \end{equation*}
  \end{asparaenum}
\end{proof}

\begin{theorem}\label{thm:a+b=b}
  If $\alpha<\beta$, then
  \begin{equation*}
    \upomega^{\alpha}+\upomega^{\beta}=\upomega^{\beta}.
  \end{equation*}
\end{theorem}

\begin{proof}
  By Lemma \ref{lem:sol}, for some $\gamma$,
    $\beta=\alpha+\gamma$,
  and then
  \begin{equation*}
    \upomega^{\alpha}+\upomega^{\beta}
    =\upomega^{\alpha}+\upomega^{\alpha+\gamma}
    =\upomega^{\alpha}\cdot(1+\upomega^{\gamma})
    =\upomega^{\alpha}\cdot\upomega^{\gamma}=\upomega^{\beta}.
    \qedhere
  \end{equation*}
\end{proof}

We have seen that, every $\alpha$ has a Cantor normal form,
given by
\begin{equation*}
  \alpha=\upomega^{\alpha_1}\cdot a_1
  +\dots+\upomega^{\alpha_m}\cdot a_m,
\end{equation*}
where
\begin{equation*}
  \alpha_1>\dots>\alpha_m,\qquad
  \bigwedge_{1\leq j\leq m}\upomega>a_j>0.
\end{equation*}
If $\alpha>0$, so that $m\geq1$, let us say
\begin{align*}
  \deg(\alpha)&=\alpha_1,&\lc(\alpha)&=a_1,
\end{align*}
the \textbf{degree} and \textbf{leading coefficient} of $\alpha$.
Thus, for every positive ordinal $\alpha$, for some ordinal $\beta$,
\begin{align*}
  \alpha&=\upomega^{\deg(\alpha)}\cdot\lc(\alpha)+\beta,&
  \deg(\beta)<\deg(\alpha).
\end{align*}
By Theorem \ref{thm:a+b=b},
  if $\deg(\alpha)<\deg(\beta)$, then
  \begin{equation*}
    \alpha+\beta=\beta.
  \end{equation*}
Now we can compute sums of Cantor normal forms.  Thus for example
\begin{multline*}
  (\upomega^{\upomega+5}\cdot2+\upomega^3\cdot5+1)
  +(\upomega^{\omega}+\upomega^2\cdot6)\\
  =\upomega^{\upomega+5}\cdot2+\upomega^{\omega}+\upomega^2\cdot6.
\end{multline*}

\begin{lemma}\label{lem:nwa}
  If $\alpha>0$ and $n\in\N$,
  then $n\cdot\upomega^{\alpha}=\upomega^{\alpha}$.
\end{lemma}

\begin{proof}
  For some $\beta$, $\alpha=1+\beta$.
  We know $n\cdot\upomega=\upomega$, and then
  \begin{equation*}
    n\cdot\upomega^{\alpha}
    =n\cdot\upomega\cdot\upomega^{\beta}
    =\upomega\cdot\upomega^{\beta}
    =\upomega^{\alpha}.\qedhere
  \end{equation*}
\end{proof}

\begin{theorem}
  Let $\beta>\deg(\alpha)$ and $n\in\N$.
  \begin{compactenum}
  \item
    If $k\in\N$, then
    \begin{equation*}
      (\upomega^{\beta}\cdot n+\alpha)\cdot k
      =\upomega^{\beta}\cdot n\cdot k+\alpha.
    \end{equation*}
  \item
    If $\gamma\geq1$, then
    \begin{equation*}
      (\upomega^{\beta}\cdot n+\alpha)\cdot\upomega^{\gamma}
      =\upomega^{\beta+\gamma}.
    \end{equation*}
  \end{compactenum}
\end{theorem}

\begin{proof}
  \begin{asparaenum}
  \item
    We use (finite) induction.
    \begin{compactenum}
      \item
        The claim is trivially true when $k=1$.
        \item
    If it is true when $k=\ell$, then
    \begin{align*}
      (\upomega^{\beta}\cdot n+\alpha)\cdot(\ell+1)
      &=(\upomega^{\beta}\cdot n+\alpha)\cdot\ell
      +\upomega^{\beta}\cdot n+\alpha\\
      &=\upomega^{\beta}\cdot n\cdot\ell+\alpha
      +\upomega^{\beta}\cdot n+\alpha\\
      &=\upomega^{\beta}\cdot n\cdot\ell
      +\upomega^{\beta}\cdot n+\alpha\\
      &=\upomega^{\beta}\cdot n\cdot(\ell+1)+\alpha.
    \end{align*}
    \end{compactenum}
  \item
    As in the proof of Lemma \ref{lem:nwa},
    we need only prove the claim when $\gamma=1$.
    We have
    \begin{multline*}
      \upomega^{\beta+1}
      =\sup_{x<\upomega}(\upomega^{\beta}\cdot x)
      \leq\sup_{x<\upomega}((\upomega^{\beta}\cdot n+\alpha)\cdot x)\\
      \leq\sup_{x<\upomega}(\upomega^{\beta}\cdot(n+1)\cdot x)
      =      \upomega^{\beta+1},
    \end{multline*}
    while also $\sup_{x<\upomega}((\upomega^{\beta}\cdot n+\alpha)\cdot x)
    =(\upomega^{\beta}\cdot n+\alpha)\cdot\upomega$.\qedhere
  \end{asparaenum}
\end{proof}

Now we can compute products of Cantor normal forms;
for, we have (under the obvious conditions)
\begin{multline*}
  (\upomega^{\beta}\cdot n+\alpha)\cdot(\upomega^{\gamma_1}\cdot d_1+\dots
  +\upomega^{\gamma_m}\cdot d_m+d_{m+1})\\
  =\upomega^{\beta+\gamma_1}\cdot d_1+\dots
  +\upomega^{\beta+\gamma_m}\cdot d_m
  +\upomega^{\beta}\cdot n\cdot d_{m+1}
  +\alpha,
\end{multline*}
the last two terms being deleted when $d_{m+1}=0$.

\begin{theorem}
  If $k\in\N$, $n\in\upomega$, and $\upomega\leq\alpha$, then
  \begin{gather*}
    k^{\upomega^{n+1}}
    =k^{\upomega^{1+n}}
    =(k^{\upomega})^{\upomega^n}
    =\upomega^{\upomega^n},\\
    k^{\upomega^{\alpha}}
    =k^{\upomega^{1+\alpha}}
    =\upomega^{\upomega^{\alpha}}.
  \end{gather*}
\end{theorem}

\begin{lemma}
  $\alpha$ is a non-successor if and only if, for some $\beta$,
  $\alpha=\upomega\cdot\beta$.
\end{lemma}

\begin{proof}
  $0$ is not a successor and is $\upomega\cdot0$.
  Suppose $\alpha>0$.
  In Cantor normal form,
  \begin{equation*}
    \alpha=\upomega^{\alpha_1}\cdot a_1+\dots+\upomega^{\alpha_m}\cdot a_m+a_{m+1},
  \end{equation*}
  where $\alpha_m>0$ and $a_{m+1}\in\upomega$.
  By Lemma \ref{lem:sol}, for some $\beta_i$,
  \begin{equation*}
    \alpha
    =\upomega\cdot(\upomega^{\beta_1}\cdot a_1+\dots+\upomega^{\beta_m}\cdot a_m)
    +a_{m+1},
  \end{equation*}
  which is a limit if and only if $a_{m+1}>0$.
\end{proof}

\begin{theorem}
  If $\gamma$ is a limit, then
  \begin{equation*}
    (\upomega^{\beta}\cdot n+\alpha)^{\gamma}=\upomega^{\beta\cdot\gamma}.
  \end{equation*}
\end{theorem}

We end with \textbf{cardinalities.}
If there is, from $A$ to $B$,
\begin{compactitem}
  \item
  an injection, $A\preccurlyeq B$;
\item
  a bijection, $A\approx B$;
\end{compactitem}
is written.

\begin{theorem}[Schr\"oder--Bernstein]
  If
  \begin{align*}
    f&\colon A\xrightarrow{\preccurlyeq}B,&
  g&\colon B\xrightarrow{\preccurlyeq}A,
  \end{align*}
  then
  \begin{equation*}
    A\approx B.
  \end{equation*}
\end{theorem}

\begin{proof}[Zermelo's proof.]
  Under the hypothesis,
  \begin{align*}
    A&\approx g\circ f[A],&
    g\circ f[A]&\included g[B]\included A,&
    g[B]&\approx B.
  \end{align*}
  Thus, assuming
  \begin{align*}
    A&\included B\included C,&
    f&\colon C\xrightarrow{\approx}A,
  \end{align*}
  we find a bijection $g$ from $B$ onto $A$.
  Let
  \begin{equation*}
    \mathscr E=\{X\included B\colon(B\setminus A)\cup f[X]\included X\}.
  \end{equation*}
  Then
  \begin{align*}
    B&\in\mathscr E,&
    X\in\mathscr E&\lto(B\setminus A)\cup F[X]\in\mathscr E.
  \end{align*}
  Let
  \begin{equation*}
    D=\bigcap\mathscr E=\{t\colon\Forall X(X\in\mathscr E\lto t\in X)\}.
  \end{equation*}
  Then
  \begin{align*}
    D&\in\mathscr E,&D&=(A\setminus B)\cup f[D].\qedhere
  \end{align*}
\end{proof}

\begin{theorem}
  If $\alpha\cdot\beta\neq0$ and $\max(\alpha,\beta)\geq\upomega$, then
  \begin{align*}
    \alpha+\beta&\approx\max(\alpha,\beta),&
    \alpha\cdot\beta&\approx\max(\alpha,\beta).
  \end{align*}
\end{theorem}

\begin{proof}
  Since
  \begin{gather*}
    \alpha+\beta\approx\alpha\sqcup\beta\approx\beta\sqcup\alpha\approx\beta+\alpha,\\
    \alpha\cdot\beta\approx\alpha\times\beta\approx\beta\times\alpha\approx\beta\cdot\alpha,
  \end{gather*}
  and also by Lemmas \ref{lem:n+wa} and \ref{lem:nwa}
  we may assume $\upomega\leq\alpha\leq\beta$.  Then
  \begin{equation*}
    \beta
    \leq\alpha+\beta
    \leq\beta+\beta
    =\beta\cdot2
    <\beta\cdot\alpha
    \leq\beta\cdot\beta
    =\beta^2.
  \end{equation*}
  Thus it is enough to show
  \begin{equation*}
    \beta\approx\beta^2.
  \end{equation*}
  This is true when $\beta=\upomega$,
  since for example if
  \begin{equation*}
    t_n=\frac{n\cdot(n+1)}2,
  \end{equation*}
  then $(k,m)\mapsto t_{k+m}+k$ is a bijection from $\upomega\times\upomega$
  to $\upomega$.
  Then by finite induction, for all $n$ in $\N$,
  \begin{equation*}
    \upomega^n\approx\upomega.
  \end{equation*}
  Letting $\gamma=\deg(\beta)$,
  we know for some $\delta$, where $\deg(\delta)<\gamma$,
  \begin{equation*}
    \beta=\upomega^{\gamma}\cdot\lc(\beta)+\delta
    \approx\delta+\lc(\beta)\cdot\upomega^{\gamma}
    =\upomega^{\gamma}.
  \end{equation*}
  We may assume now $\gamma\geq\upomega$.  Since for any $\alpha$ and $\beta$
  \begin{equation}\label{eqn:a^b}
    \alpha^{\beta}\approx\{f\in{}^{\beta}\alpha\colon\card{\supp(f)}<\upomega\},
  \end{equation}
  where by definition
  \begin{equation*}
    \card{\supp(f)}<\upomega
    \liff
    \{x\in\beta\colon f(x)\neq0\}\text{ is finite,}
  \end{equation*}
  we have generally
  \begin{equation*}
    \alpha\approx\gamma\land\beta\approx\delta
    \lto\alpha^{\beta}\approx\gamma^{\delta}.
  \end{equation*}
  In our case,
  \begin{equation*}
    \beta^2\approx(\upomega^{\gamma})^2
    \approx\upomega^{\upomega^{\deg(\gamma)}\cdot2}
    \approx\upomega^{2\cdot\upomega^{\deg(\gamma)}}
    =\upomega^{\upomega^{\deg(\gamma)}}
    \approx\upomega^{\gamma}
    \approx\beta.\qedhere
  \end{equation*}
\end{proof}

\begin{corollary}
  For all infinite $\alpha$, for all $n$ in $\N$,
  \begin{equation*}
    \alpha^n\approx\alpha.
  \end{equation*}
\end{corollary}

\begin{theorem}
  If $\min(\alpha,\beta)\leq2$ and $\upomega\leq\max(\alpha,\beta)$, then
  \begin{equation*}
    \alpha^{\beta}\approx\max(\alpha,\beta).
  \end{equation*}
\end{theorem}

\begin{proof}
  From Lemma \ref{lem:a} we know
  \begin{equation*}
    \max(\alpha,\beta)\leq\alpha^{\beta}.
  \end{equation*}
  From \eqref{eqn:a^b},
  an element of $\alpha^{\beta}$ uniquely determines
  an ordered pair consisting of, for some $n$ in $\upomega$,
  \begin{compactitem}
  \item
    a subset $\{\beta_i\colon i< n\}$ of $\beta$, where
      $\beta_0<\dots<\beta_{n-1}$;
  \item
    a function $(\alpha_i\colon i<n)$ in ${}^n\alpha$.
  \end{compactitem}
  Moreover, the finite subsets of $\beta$
  correspond precisely to the elements of $2^{\beta}$.
  Thus
  \begin{equation*}
    \alpha^{\beta}\preccurlyeq2^{\beta}\times\alpha^{\upomega}.
  \end{equation*}
  Then also
  \begin{equation*}
    2^{\beta}
    \preccurlyeq\bigcup_{x<\upomega}{}^x{\beta}
    \preccurlyeq\bigsqcup_{x<\upomega}\beta
    \approx\upomega\times\beta\approx\beta,
  \end{equation*}
  and likewise
  \begin{equation*}
    \alpha^{\upomega}
    \approx\bigcup_{x<\upomega}{}^x{\alpha}
    \approx\alpha.\qedhere
  \end{equation*}
\end{proof}

\end{document}

