\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 Introduction to Ordinals
\end{center}
\bigskip

\section{Orderings}
We give here a quick presentation of the definitions and basic facts about the 
ordinals. We start with an ``informal'' presentation, and then 
shift to the formal (Von Neumann) definition.

Our presentation will also be slightly informal in that it takes
place outside of formal $ZFC$ set theory, but this will suffice. 


\begin{defn} A \emph  {partial-ordering} $\preceq_X$ on a set $X$ is a 
reflexive, transitive (binary) relation. That is, it satisfies:

\begin{enumerate} 
\item
$\forall x \ x \preceq x$ (reflexive)
\item
$ \forall x, y, z,\ (x \preceq y \wedge y \preceq z 
\rightarrow x \preceq z)$ (transitive) \\ 
A partial-ordering is \emph {strict} if it also satisfies
\item 
$\forall x, y\ (x \preceq y \wedge y \preceq x \rightarrow x =y)$. 
\end{enumerate}
\end{defn}

We write $\preceq$ for $\preceq_X$ when $X$ is understood. 
If we define $x \equiv y$ iff $x \preceq y$ and $y \preceq x$, 
then it is easy to check that $\equiv$ is an equivalence relation. 
It is easy to see that any partial-ordering is a strict partial ordering
on equivalence classes, and conversely, any strict partial-ordering
on equivalence classes on $X$ induces a partial-ordering. 
Thus, the difference between the two notions is rather trivial. 
Also, some authors use the terms quasi-order and partial-order
respectively to refer to partial-orders and strict partial-orders. 


Given a partial-order $\preceq$, we define $x \prec y$ iff 
$x \preceq y$ and $\neg (y \preceq x)$. Then $\prec$ is 
irreflexive (i.e., $\forall x\ \neg (x \prec x)$) and 
transitive. Conversely, if $\prec$ is irreflexive and transitive, and
$\preceq$ is defined by $x \preceq y$ iff $x \prec y$ or $x = y$, 
then $\preceq$ is a partial-order. Also, if $\preceq$ is a strict
partial-order and $\prec$ is obtained from $\preceq$ and $\preceq'$
is obtained from $\prec$ as above, then $\preceq=\preceq'$. 
Thus, it makes no difference whether we consider $\preceq$ or
$\prec$. 






\begin{defn}
A linear ordering $\preceq$ on a set $X$ is a strict partial-order
which is also \emph{connected}, that is, $\forall x, y\ 
(x \preceq y \vee y \preceq x)$. 
\end{defn}

Thus, a linear order satisfies:

\begin{enumerate}
\item
$\forall x \ x \preceq x$ 
\item
$ \forall x, y, z,\ (x \preceq y \wedge y \preceq z 
\rightarrow x \preceq z)$  
\item 
$\forall x, y\ (x \preceq y \wedge y \preceq x \rightarrow x =y)$ 
\item
$\forall x,y\ (x \preceq y \vee y \preceq x)$ 
\end{enumerate}

Equivalently, the strict part $\prec$ of a linear order is 
characterized by:


\begin{enumerate}
\item
$\forall x\ x \nprec x$ (irreflexive) \label{lo1}
\item
$\forall x\forall y (x \prec y \vee x=y \vee y \prec x)$ (connected)\label{lo2}
\item
$\forall x \forall y \forall z (x \prec y \wedge y \prec z \rightarrow 
x \prec z)$ (transitive)\label{lo3}
\end{enumerate}


\begin{exer} Show directly that if $\preceq$ satisfies 
the first set of axioms, then the corresponding $\prec$ satisfies
the second set, and vice-versa.
\end{exer}


Note that exactly one of the cases holds in axiom~\ref{lo2} above. 

Examples of linear orderings include $(\mathbb{N},\prec)$, 
$(\mathbb{R},\prec)$, $(\mathbb{Q},\prec)$, $(\mathbb{Z},\prec)$, where $\prec$
in all cases is the ordering induceed by the usual ordering on $\mathbb{R}$. 



\begin{defn}
A well-ordering $(X,\prec_X)$ is a linear ordering such that for every 
$S\subseteq X$, $S \neq \emptyset$, $S$ has a $\prec$ least element. 
That is, $\exists x \in S \ \forall y \in S\ \neg (y \prec x)$. 
\end{defn}



The axiom of choice ($\ac$) is the statement that every set
can be well-ordered. 


With their usual orderings, $\mathbb{N}$ is well-ordered, but $\Z,
\Q,\R$ are not.

More generally, if $R$ is a binary relation on a set $X$, we say $R$ 
is well-founded if for every $S\subseteq X$, $S \neq \emptyset$, 
$\exists x \in S \ \forall y \in S\ \neg (y R x)$.
Thus, a well-ordering is just a linear ordering which is well-founded. 


\begin{fact}(DC)
A relation $R$ on a set $X$ is well-founded iff there does not exist 
an infinite decreasing chain, i.e., elements $x_0,x_1,\ldots$ of $X$ 
with $x_{n+1} R x_n$ for all $n$.
\end{fact}

\begin{proof}
If $R$ is well-founded, and $x_0,x_1,\ldots$ is a sequence form $X$, 
let $x_n$ be an $R$-minimal element of $S\doteq \{ x_0,x_1,\ldots\}$.
Then $\neg x_{n+1} R x_n$. (This direction did not use $AC$). 

Suppose now $(X,R)$ has no infinite decreasing chains, and let 
$S\subseteq X$, $X \neq \emptyset$. For each finite decreasing chain 
$x_n R x_{n-1}R\dots R x_2 R x_1 R x_0$ of elements from $S$, 
``pick'' an $x_{n+1} \in S$ such that $x_{n+1} R x_n$. This exixts by the 
assumption on $S$. This defines a decresing chain $x_0,x_1,\ldots$. 


More formally, for each finite decreasing chain 
$\vec x=x_n R x_{n-1} R \dots R x_2 R x_1 R x_0$ of elements from $S$, let 
$A_{\vec x}=\{ y \in S \colon y R x_n\}$. By assumption, $A_{\vec x} \neq 
\emptyset$. By $DC$, there is an infinite sequence $x_0,x_1,\ldots$ 
such that $\forall n\ x_{n+1} \in A_{x_0,\ldots,x_n}$, i.e., $x_{n+1} R x_n$. 
\end{proof}

Though we are mainly concerned with well-orderings, we can make the following 
definitions for linear orderings.


\begin{defn}
If $(X,\prec_X)$ is a linear ordering and $x \in X$, let 
$I_x^{\prec_X}$ (or just $I_x$ if $\prec_X$ is understood) denote the 
initial segment determined by $x$. That is, $I_x= \{ y \in X \colon 
y \prec x \}$. An initial segment of $X$ means a set $I \subseteq X$ 
such that $\forall x,x' \in X\ (x \in I \wedge x' \prec x \rightarrow 
x' \in I)$. An initial segment $I$ of $X$ is said to be proper if 
$I \neq X$. 
\end{defn}


\begin{defn}
Let $(X,\prec_X)$, $(Y,\prec_Y)$ be linear orderings. We say a map 
$\pi \colon A \to Y$, where $A \subseteq X$, is order-preserving if 
for all $x_1,x_2 \in A$, $x_1 \prec_X x_2 \leftrightarrow \pi(x_1) 
\prec_Y \pi(x_2)$. We say $\pi$ is an order-isomorphism from $X$ to 
$Y$ if $\pi$ is an order-preserving bijection. 
\end{defn}


We frequently just say $\prec_X$, $\prec_Y$ are isomorphic, written 
$\prec_X \cong \prec_Y$, to abbreviate ``order-isomorphic''.



\begin{exer} Show that if $(X,\prec)$ is a well-ordering and $I$ 
is a proper initial segment of $X$, then $\exists x \in X\ 
I=I_x$. 
\end{exer}


\begin{exer} Suppose $(X,\prec_X)$, $(Y,\prec_Y)$ are well-orderings. 
Let $\prec_X \oplus \prec_Y$ be the ordering with domain 
$(X \times \{ 0 \}) \cup (Y \times \{ 1\})$ and ordered by: 
$(z_1,i_1) \prec (z_2,i_2)$ iff $ (i_1 < i_2) \vee (i_1=i_2=0 \wedge 
z_1 \prec_X z_2) \vee (i_1=i_2=1 \wedge z_1 \prec_Y z_2)$. 
Show that $\prec_X \oplus \prec_Y$ is also a well-ordering. 
\end{exer}


\begin{exer} Suppose $(X,\prec_X)$, $(Y,\prec_Y)$ are well-orderings. 
Let $\prec_X \otimes \prec_Y$ be the ordering with domain 
$X \times Y$ and ordered by: $(x_1,y_1) \prec (x_2,y_2)$ iff 
$(y_1 \prec_Y y_2) \vee (y_1=y_2 \wedge x_1 \prec_X x_2)$. 
Show that $\prec_X \otimes \prec_Y$ is also a well-ordering. 
\end{exer}



We develop some of the basic facts about well-orderings. 


\begin{lem} \label{tl1}
If the well-orderings $(X,\prec_X)$, $(Y,\prec_Y)$ are order-isomorphic, then 
the order-isomorphism between them is unique. 
\end{lem}


\begin{proof}
Suppose $f,g\colon x \to Y$ are both order-isomorphisms. We show that $f=g$. 
If not, let $x_0 \in X$ be the $\prec_X$ least $x$ such that $f(x) \neq g(x)$. 
Without loss of generality, Suppose $f(x_0) \prec_Y g(x_0)$. 
Let $x_1$ be such that $g(x_1)=f(x_0)$. 
Clearly $x_1 \neq x_0$. If $x_1 \prec_X x_0$, then by minimality of $x_0$, 
$g(x_1)=f(x_1)\prec_X f(x_0)$, a contradiction. Thus, $x_0 \prec_X x_1$. 
However, this contradicts $g$ being order-preserving. 
\end{proof}


\begin{lem} \label{tl2}
If $(X,\prec_X)$ is a well-ordering, then $X$ is not order-isomorphic to any 
proper initial segment of itself. 
\end{lem}

\begin{proof}
Suppose $\pi \colon I \to X$ is an order-isomorphism 
between the proper initial 
segment $I$ of $X$ and all of $X$. We cannot have $\pi(x)=x$ for all $x \in I$,
as then $\pi$ would not be onto. Let $x_0$ be the least element of $I$ 
such that $\pi(x) \neq x$. 
We can't have $\pi(x_0) \prec x_0$ since then $\pi(\pi(x_0))=\pi(x_0)$, and 
thus $\pi$ is not one-to-one. So, $x_0 \prec \pi(x_0)$.

Let $x_1\in I$ be such that $\pi(x_1)=x_0$. 
Clearly $x_1 \neq x_0$ (since $\pi(x_0)\neq x_0$). If $x_1 \prec x_0$, then 
$\pi(x_1)=x_1\prec x_0$, which is impossible. If $x_0 \prec x_1$, then 
$\pi(x_1)=x_0 \prec \pi(x_0)$, which contradicts $\pi$ being order-preserving. 
\end{proof}


\begin{exer}
Show that if $\pi$ is an isomorphism from $\prec_X$ to 
$\prec_Y$ and $x \in X$, then $\pi \res I_x^{\prec_X}$ is an isomorphism 
between $I_x^{\prec_X}$ and $I_y^{\prec_Y}$. 
\end{exer}


\begin{exer}
Show that there are two countable linear orders, neither
of which order-embeds into the other. Thus, there are 
``incomparable'' linear orders. Can you find three countable 
linear orders, any two of which are incomparable?
\end{exer}



\begin{thm}\label{on1}
Let $(X,\prec_X)$, $(Y,\prec_Y)$ be well-orderings. Then exactly one of the 
following holds. 

\begin{enumerate}
\item
$(X,\prec_X)$ is isomorphic to a proper initial segment of $(Y,\prec_Y)$. 
\item
$(Y,\prec_Y)$ is isomorphic to a proper initial segment of $(X,\prec_X)$.
\item
$(X,\prec_X)$ is isomorphic to $(Y,\prec_Y)$. 
\end{enumerate}
\end{thm}



\begin{proof}
For $x \in X, y \in Y$, define $R(x,y)$ iff $I_x^{\prec_X} \cong 
I_y^{\prec_Y}$. 

First note that for all $x \in X$ and $y_1,y_2 \in Y$, if $R(x,y_1)$ and 
$R(x,y_2)$, then $y_1=y_2$. If not, say w.l.o.g $y_1 \prec_Y y_2$. 
But then, $I_x^{\prec_X} \cong I_{y_1}^{\prec_{Y}} \cong I_{y_2}^{\prec_{Y}}$. 
This violates lemma~\ref{tl2}. 

Thus, $R$ is a partial function. Likewise, $R$ is one-to-one, since if 
$R(x_1,y),R(x_2,y)$ but (w.l.o.g.) $x_1 \prec_X x_2$, then 
$I_{x_1}^{\prec_X}\cong I_{y}^{\prec_{Y}} \cong I_{x_2}^{\prec_X}$. 

We next claim that $\dom(R)$ is an initial segment of $\prec_X$. 
Suppose  $x_2 \in \dom(R)$ and $x_1 \prec_X x_2$. Say $R(x_2,y_2)$, that is, 
$I_{x_2}^{\prec_X} \cong I_{y_2}^{\prec_{Y}}$. 
Let $\pi$ be an isomorphism from $I_{x_2}^{\prec_X}$ to $I_{y_2}^{\prec_{Y}}$. 
By the exercise above, 
$I_{x_1}^{\prec_X} \cong I_{y_1}^{\prec_{Y}}$, where $y_1=\pi(x_1)$. 
Thus, $R(x_1,y_1)$, and so $x_1 \in \dom(R)$. We have also shown that 
$R$ is order-preserving from $\prec_X$ to $\prec_Y$. 

An exactly similar argument shows likewise that $\ran(R)$ is an initial 
segment of $\prec_Y$. 

We have shown so far that $R$ is an isomorphism from an initial segment of 
$\prec_X$, say $I$,  to an initial segment of $\prec_Y$, say $J$.  


We now consider cases.

If  $I=X$ but $J \neq Y$, Then case (1) of the theorem holds. 
If $I\neq X$ but $J = Y$, then case (2) of the theorem holds. 
If  $I= X$ and $J = Y$, then clearly case (3) of the theorem holds. 
Suppose finally that  $I \neq X$ and $J \neq Y$. 
We show that this case does not occur.
By an exercise, let $I=I_x^{\prec_x}$ and $J=I_y^{\prec_Y}$. 
Since $R$ is an isomorphism between $I$ and $J$, by definition we have 
$R(x,y)$. Thus $x \in \dom(R)$, so $x \in I_x$, a contradiction. 


We have now shown that one of the three cases of the theorem holds. 
Uniqueness of the case follows immediately from lemma~\ref{tl1}. 
\end{proof}


We now state our (slightly informal) definition of ordinal. 


\begin{defn}
An ordinal $\alpha$ is an equivalence class of a wellordering $(X,\prec_X)$ 
under order-isomorphism. Thus, $\alpha=[(X,\prec_X)]$. 
\end{defn}


\begin{rem}
The informality in the above definition lies in some set theoretic subtleties. 
Namely, the ``equivalence classes'' as defined above are actually 
too large to be sets, they are proper classes. Thus, from a formal 
set theoretic point of view, the definition doesn't make sense (this is 
actually a minor problem that plagues many common definitions in mathematics). 
However, the problem is easy to correct if one does the formal development 
of set theory and moreover, we will give a better definition
not affected by this problem shortly. 
\end{rem}



We frequently use lower case Greek letters like $\alpha,\beta,\gamma$ for 
ordinals. $\on$ denotes the (proper class) of all ordinals. 
Suppose $\alpha,\beta$ are ordinals. Say $\alpha=[(X,\prec_X)]$ and 
$\beta=[(X,\prec_X)]$. We say $\alpha<\beta$ iff $(X,\prec_X)\cong 
(Y,\prec_Y)$. This is clearly well-defined. 








Theorem~\ref{on1} may then be restated as saying for any two ordinals 
$\alpha,\beta$,
exactly one of the following holds: $\alpha<\beta$, $\alpha=\beta$, or 
$\alpha>\beta$. Note that if $\alpha=[(X,\prec_X)]$ and $\beta<\alpha$, then 
we may represent $\beta$ as $\beta=[(I_x,\prec_X)]$ for some proper 
initial segment $I_x$ of $\prec_X$. 



\begin{exer}
Let $\alpha,\beta \in \on$. Suppose that $\forall \gamma 
<\alpha \ \exists \delta <\beta\ \gamma \leq \delta$. Show that 
$\alpha \leq \beta$ (hint: use theorem~\ref{on1} and lemma~\ref{tl2}).
\end{exer}


\begin{exer} 
Let $\alpha,\beta \in \on$. Suppose there is an 
order-preserving map $\pi$ from $\alpha$ to $\beta$. Show that $\alpha \leq 
\beta$. 
\end{exer}

\section{Ordinals}


We now give the formal definition of ordinal, due to von Neumann. 
The previous informal definition (aside from the minor set-theoretic
problem alluded to) is acceptable but awkwerd due to the 
continuing need to take representatives of equivalence classes. 
The definition we now give avoids this by giving a 
canonical representative for each class. 


\begin{defn}
A set $X$ is transitive if $\forall x \in X\ \forall y \in x\ (y \in X)$. 
\end{defn}

We may now state the official Von Neumann definition of ordinal.


\begin{defn}
An ordinal $\alpha$ is a transitive set which is well-ordered by the 
$\epsilon$ (set element) relation (resticted to $\alpha \times \alpha$). 
\end{defn}


We frequently use lower case Greek letters like $\alpha,\beta,\gamma$ for 
ordinals. $\on$ denotes the (proper class) of all ordinals. 



\begin{lem}
If $\alpha \in \on$ and $\beta \in \alpha$, then $\beta \in \on$
and $\beta=I_\beta^\alpha$.
\end{lem}


\begin{proof}
If $\gamma \in \beta$, then $\gamma \in \alpha$ by transitivity,
and thus $\beta=I_\beta^\alpha$. This also shows $(\beta,\in)$
is a well-ordering, as it is an initial segment of a well-ordering. 
To see $\beta$ is transitive, 
suppose $\delta\in \gamma \in \beta$. 
Since $\alpha$ is transitive, $\delta,\gamma \in \alpha$. Since $\in$ 
is a transitive relation on  $\alpha$ (part of the definition of a linear 
ordering), we also have $\delta \in \beta$, and we are done. 
\end{proof}



The fact that representatives are now unique is embodied in the following 
lemma. 


\begin{lem} \label{uniq}
If $\alpha,\beta \in \on$ and $\alpha \cong \beta$, then $\alpha=\beta$. 
\end{lem}


\begin{proof}
Let $\pi \colon \alpha \to \beta$ be an isomorphism. It suffices to show that 
$\pi$ is the identity map. Suppose not, and let $\alpha_0 \in \alpha$ be 
least such that $\pi(\alpha_0) \neq \alpha_0$. Thus, $\forall \gamma \in 
\alpha_0 \ (\pi(\gamma)=\gamma)$. Now, since $\pi$ is an order-isomporphism 
from $(\alpha,\in)$ to $(\beta,\in)$, we have 
$\{\pi(\gamma) \colon \gamma\in \alpha_0 \}=\{ \delta \in \pi(\alpha_0)\}$. 
Thus, $\alpha_0=\{ \gamma \colon \gamma \in \alpha_0\}= 
\{\pi(\gamma) \colon \gamma\in \alpha_0 \}=
\{ \delta \in \pi(\alpha_0)\}= \pi(\alpha_0)$, 
a contradiction. 
\end{proof}



\begin{lem} \label{oncon}
If $\alpha$, $\beta \in \on$ then exactly one of the following holds:
$\alpha \in \beta$, $\alpha=\beta$, or $\beta \in \alpha$. 
\end{lem}

\begin{proof}
Uniqueness follows from theorem~\ref{on1}. If $(\alpha,\in) \cong
(\beta,\in)$, then by lemma~\ref{uniq} $\alpha=\beta$. 
Suppose $\alpha$ is isomorphic to a proper initial segment of 
$\beta$. Let $\beta_0 \in \beta$ be such that $(\alpha,\in) \cong
(\beta_0,\in)$ (which is the initial segment determined by 
$\beta_0$ in $(\beta,\in)$). Then since $\beta_0$ is an ordinal, 
$\alpha=\beta_0 \in \beta$. The other case is similar.
\end{proof}

The following theorem gives a fundamental property of ordinals. It says, in 
effect, that the collection of all ordinals behaves like an ordinal. 




\begin{thm} \label{onord}
The collection of ordinals with the $\in$ relation satisfies the axioms
for a linear order. That is, $\forall \alpha \in \on\ \alpha 
\notin \alpha$, $\forall \alpha, \beta \in \on\ (\alpha \in \beta \vee
\alpha=\beta \vee \beta \in \alpha)$, $\forall \alpha, \beta,\gamma \in 
\on\ (\alpha \in \beta \wedge \beta \in \gamma \rightarrow 
\alpha \in \gamma)$.  Furthermore, it behaves like a well-odering
in that if 
$S \subseteq \on$ is a non-empty set of ordinals, then there is an 
$\alpha 
\in S$ which is minimal, i.e., $\forall \beta \in S\ (\beta=\alpha \vee 
\alpha \in \beta)$. 
\end{thm}




\begin{proof}
For any $\alpha \in \on$, $\alpha \notin \alpha$ as otherwise
$\alpha$ would be isomorphic (in fact equal) to a proper
initial segment of itself. We have already shown connectedness
and transitivity is immediate from the definition of ordinal.




Let $S \subseteq \on$ be non-empty, and let $\alpha \in S$. 
Let $S'=\{ \beta \in \alpha \colon \beta \in S\}$. If $S'$
is empty, we are done. Otherwise, let $\alpha_0$ be a minimal
element of $S'$, which exists as $(\alpha,\in)$ is a well-ordering. 
Then for all $\gamma \in S$, either $\gamma \in \alpha$ in which case
$\alpha_0 =\gamma$ or $\alpha_0 \in \gamma$ by minimality, or
$\gamma =\alpha$ in which case $\alpha_0 \in \gamma$, or 
$\alpha \in \gamma$ in which case $\alpha_0 \in \gamma$ by 
tansitivity. Thus, $\alpha_0$ is minimal.
\end{proof}


We now show that every well-ordering is isomorphic to a unique 
ordinal, which justifies our definition.


\begin{thm}
Every well-ordering $(X, \prec)$ is order-isomorphic to a 
unique ordinal.
\end{thm}

\begin{proof}
Uniqueness follows from theorem~\ref{on1} and lemma~\ref{oncon}. 
Let $Y=\{ x \in X \colon \exists \alpha \in \on (I_x \cong \alpha)\}$. 
Note that $Y$ is an initial segment of $X$, since an initial 
segment of an ordinal is an ordinal. For $x \in Y$, let $f(x)$ be the
unique ordinal such that $I_x \cong f(x)$. 
We claim that $Y=X$. 
If not, let $Y=I_{x_0}$, where $x_0 \in X$. Let 
$A=\{ f(x) \colon x \in Y\} \subseteq \on$. First, $f$ is an 
order-isomorphism between $Y$ and $A$. For if $x_1 \prec x_2$ then
we must have $f(x_1) \in f(x_2)$ as the other possibilities
($f(x_1)=f(x_2)$ or $f(x_2) \in f(x_1)$) lead to an isomorphism
of $I_{x_2}$ with an initial segment of $I_{x_1}$. 
Next, note that $A$ is transitive. For suppose $\alpha=f(x)$, where 
$x \in Y$, and $\beta \in \alpha$. Since $I_x \cong \alpha$, 
there is a $z \prec x$ such that $I_z \cong \beta$. Thus $\beta=
f(z) \in A$. Finally, $A$ is well-ordered by $\in$, as $A \subseteq \on$. 
Thus, $A \in \on$. So, $I_{x_0} \cong A \in \on$, a contradiction. 
So, $Y=X$, and thus $f$ is an order-isomorphism between $X$ and 
an ordinal, and we are done.
\end{proof}




We use the notation $\alpha < \beta$ for ordinals to mean $\alpha \in 
\beta$, which is reasonable in view of theorem~\ref{onord}. 
Thus, every ordinal is the set of smaller ordinals, that is, 
$\alpha=\{ \beta \in \on \colon \beta < \alpha\}$. 

The first few ordinals are described as follows. 
The least ordinal is $\emptyset$, which we also denote by $0$. 
The next ordinal is $\{ 0\}= \{ \emptyset\}$, which we also denote by $1$. 
The next ordinal is $\{ 0,1\}=\{ \emptyset, \{ \emptyset \} \}$, which
we also denote by $2$, etc. The least infinite ordinal is 
$\{ 0,1,2,3,\dots \}$, which we denote by $\omega$ (as a set, it is thus
the set of natural numbers). The next ordinal is $\{ 0,1,\dots, \omega \}$
which we denote by $\omega+1$, etc. 





\begin{defn}
An ordinal $\alpha$ is a successor ordinal if $\{ \beta\colon \beta<\alpha\}$ 
has a largest element. Otherwise $\alpha$ is called a limit ordinal.
\end{defn}

For $\alpha$ a successor ordinal, we call the largest $\beta<\alpha$ the 
predecessor of $\alpha$. 

If $\alpha \in \on$, it is not hard to see from theorem~\ref{on1}
that there is a least ordinal larger than $\alpha$. It fact, it is not hard 
to see directly what this ordinal is. Namely, let $S(\alpha)=
\alpha \cup \{ \alpha\}$. Easily $S(\alpha)$ is an ordinal, and 
if $\beta \in S(\alpha)$, then either $\beta \in \alpha$ or $\beta 
= \alpha$. So, $S(\alpha)$ is the least ordinal greater than 
$\alpha$. 
We usually write $\alpha+1$ for the successor 
of $\alpha$ just constructed (the reason for this notation is given below).
Thus, the successor ordinals are precisely those of the form $\alpha+1$ 
for some $\alpha \in \on$. 




One can extend addition and 
multiplication on the integers $\omega$ to all of the ordinals. 

\begin{defn}
Let $\alpha$, $\beta$ be ordinals. Then $\alpha+
\beta$ is defined to be the ordinal represented by the well-ordering 
$(\alpha,\in)  \oplus (\beta,\in)$ (defined earlier). 

Also, $\alpha \cdot \beta$ is defined to be the ordinal represented by 
the well-ordering $(\alpha,\in) \otimes (\beta,\in)$.
\end{defn}

Thus, $\alpha+\beta$ consists of a copy of $\alpha$ followed by a copy 
of $\beta$. $\alpha \cdot \beta$ consists of $\beta$ copies of $\alpha$. 
Thus $\omega+\omega$ and $\omega \cdot 2$ both consist of two copies 
of $\omega$ and are thus isomorphic. That is, as ordinals, $\omega+\omega=
\omega \cdot 2$. More generally, the following fact is easy to verify (and 
left to the reader).

\begin{fact}
For all ordinals $\alpha,\beta,\gamma$ we have: 
$\alpha+(\beta+\gamma)=(\alpha+\beta)+\gamma$, 
$\alpha\cdot (\beta\cdot \gamma)=(\alpha \cdot \beta) \cdot \gamma$, 
$\gamma \cdot (\alpha+\beta)=\gamma \cdot \alpha + \gamma \cdot \beta$. 
\end{fact}


In general, however, neither $+$ nor $\cdot$ is commutative, and multiplication
is not right distributive over addition. For example, $2+\omega=\omega$, but 
$\omega+2>\omega$. Likewise, $2 \cdot \omega=\omega$, but $\omega\cdot 2=
\omega+\omega>\omega$. Also, $(1+1)\cdot \omega =2 \cdot \omega =\omega 
\neq \omega +\omega$. 

Note though that the notation $\alpha+1$ for the successor of $\alpha$ 
is consistent with with the definition of ordinal addition. 


\begin{exer}
{\bf Exercise}. Show that every ordinal $\alpha$ can be written
uniquely in the form $\alpha=\beta+n$ where $\beta$ is a limit ordinal
and $n \in \omega$. 
\end{exer}


\begin{exer}
Identify the first $\omega$ many ordinals which
are additively closed (we say $\alpha$ is additively closed
if $\forall \beta < \alpha\ (\beta + \beta < \alpha)$. 
\end{exer}



\begin{exer}
Show that if $\beta \leq
\alpha < \beta+ \gamma$, then there is a 
$\gamma' < \gamma$ such that $\alpha=\beta+\gamma'$.
\end{exer} 



Is $S$ is a set of ordinals, let $\cup S$ denote the union of $S$,
that is, $x \in \cup S \leftrightarrow \exists \alpha \in S\ 
x \in \alpha$. Then clearly $\cup S$ is a set of ordinals, and 
so is well-founded. Also, $S$ is easily transitive and hence is
an ordinal. 


\begin{exer}
Show $\cup S$ is the least ordinal greater than or
equal to all of the ordinals in $S$. 
\end{exer}


We often write $\sup (S)$ in place of $\cup S$. 



\section{Countable Ordinals}
An ordinal $\alpha$ is said to be countable if $\alpha$ is countable
as a set. 
The following is a simple but basic fact about the countable ordinals. The 
proof, though, does use $AC$ (the result can fail without $AC$). 

\begin{thm}
Let $\alpha_0,\alpha_1,\ldots$ be a countable set of countable ordinals 
$\alpha_i$. Then there is a countable ordinal $\beta$ such that 
$\beta> \alpha_i$ for all $i$.
\end{thm}

\begin{proof}
It suffices to show that $\cup \{ \alpha_0,\alpha_1,\dots \}$ is 
countable. This follows from the fact that (using $\ac$) a countable
union of countable sets is countable. 
\end{proof}






Another important fact about the countable ordinals is that they all have 
``countable cofinality''. The concept of cofinality can be defined for a 
general ordinal, which we give later. 


\begin{defn}
A limit ordinal $\alpha$ is said to have cofinality $\omega$ (written 
$\cof(\alpha)=\omega$) if there is a map $f \colon \omega \to \alpha$ 
which is increasing (i.e., order-preserving) and unbounded (i.e., 
$\forall \beta <\alpha\ \exists n \in \omega \ f(n) \geq \beta$). 
\end{defn}


We then have:

\begin{thm}
Every countable limit ordinal has cofinality $\omega$. 
\end{thm}

\begin{proof}
Let $\pi \colon \omega \to \alpha$ be a bijection. 
Define $f(n)=\sup \{ \pi(0),\dots,\pi(n)\} +n$. Then $f$ is 
strictly increasing and cofinal in $\alpha$. 
\end{proof}



\section{Ordinal Exponentiation}

The exponentiation operation on the integers can also be
extended to the ordinals. Our definition here is slightly informal,
since we take for granted that a definition by transfinite
recursion is legitimate (will show that later). An equivalent
definition can be given without using recursion, but the recursive
definition is perhaps the most natural. One should be careful
not to confuse ordinal exponentiation with cardinal exponentiation
(which, unfortunately, uses the same notation). 


For $\alpha$, $\beta$ ordinals, we define the ordinal 
$\alpha^\beta$ be recusion on $\beta$ as follows:

\begin{defn}
$\alpha^0=1$. If $\beta=\gamma+1$, then 
$\alpha^{\beta}=\alpha^\gamma \cdot \alpha$. 
If $\beta$ is a limit, $\alpha^\beta =\sup_{\gamma < \beta} \alpha^\gamma$.
\end{defn}


\begin{lem}
For all ordinals $\alpha$, $\beta$, $\gamma$:
$\alpha^{\beta+\gamma}=\alpha^\beta \cdot \alpha^\gamma$, 
$(\alpha^\beta)^\gamma=\alpha^{\beta \cdot \gamma}$.
\end{lem}


\begin{proof}
We show by induction on $\gamma$ that 
$\alpha^{\beta+\gamma}=\alpha^\beta \cdot \alpha^\gamma$. 
For $\gamma=0$ it is immediate. Suppose the equation holds for all 
$\delta < \gamma$. If $\gamma=\delta+1$, then 
$$
\alpha^{\beta+\gamma}=\alpha^{\beta+(\delta+1)}=
\alpha^{(\beta+\delta)+1}=\alpha^{\beta+\delta} \cdot \alpha=
(\alpha^\beta \cdot \alpha^\delta) \cdot \alpha
=\alpha^\beta \cdot (\alpha^\delta \cdot \alpha) =
\alpha^\beta \cdot \alpha^{\delta+1}=\alpha^\beta \cdot \alpha^\gamma
$$
\end{proof}


\begin{exer}
Show the second part of the lemma. 
\end{exer}


\begin{exer}
Show that an ordinal is additively closed iff 
it is of the form $\omega^\beta$ for some $\beta \in \on$. 
\end{exer}


\begin{exer}
Identify the least ordinal closed under 
ordinal exponentiation. 
\end{exer}



\begin{thm} (Cantor Normal Form) Every ordinal $\alpha$ can be written
uniquely in the form 
$$
\alpha= \omega^{\beta_0} \cdot k_0 + \omega^{\beta_1} \cdot k_1 + 
\cdots + \omega^{\beta_n} \cdot k_n
$$
where $\beta_0 > \beta_1 \dots < \beta_n$ and $k_0,\dots,k_n 
\in \omega$. 
\end{thm}

\begin{proof}
First note that for every $\alpha \in \on$ there is a largest 
ordinal $\beta$ such that $\omega^\beta \leq \alpha$. For let $\gamma$
be the least ordinal such that $\omega^\gamma > \alpha$. Then $\gamma$
is a successor, as otherwise $\omega^\gamma= 
\sup_{\delta< \gamma} \omega^\delta \leq \sup_{\delta< \gamma} 
\alpha = \alpha$. So, $\gamma=\beta+1$ for some $\beta$, and $\beta$
is as desired. Let us call $\beta$ the companion to $\alpha$. 

We prove the existence of the normal form by induction on the
size of the companion $\beta_0$ to $\alpha$. By definition 
$\omega^{\beta_0} \leq \alpha$. If equality holds we are done, so 
assume $\omega^{\beta_0} < \alpha$. Since $\alpha< \omega^{\beta_0+1}=
\omega^{\beta_0} \cdot \omega= \sup_k \omega^{\beta_0} \cdot k$, let 
$k_0$ be the largest integer such that $\omega^{\beta_0} \cdot  k_0
\leq \alpha$. Then $\alpha=\omega^{\beta_0} \cdot k_0 + \alpha'$, where
$\alpha' < \omega^{\beta_0}$. Thus, $\alpha'$ has a smaller comapnion
than $\alpha$, and by induction $\alpha'$ has a normal form. If
$\alpha'=\omega^{\beta_1} \cdot k_1 + 
\cdots + \omega^{\beta_n} \cdot k_n$, then substituting we are done. 
\end{proof}


\begin{exer}
Show that if $\alpha_0,\dots, \alpha_n$ are countable
ordinals, then any expression built up from them using
ordinal sums, products, and exponentiation is also countable.
\end{exer}



\begin{exer}
Show that $\omega^\alpha + \omega^\beta$ 
equals $\omega^\beta$ if $\alpha < \beta$. 
\end{exer}

\begin{exer}
We say $\gamma$ is a \emph{mingling} of $\alpha$ and $\beta$ if
$\gamma$ can be written as the disjoint union of $A$ and $B$ where 
$A$ is order-isomorphic to $\alpha$ and $B$ is order-isomorphic to 
$\beta$. Find a mingling $\gamma$ of two ordinals $\alpha$, $\beta$
such that $\gamma > \max \{ \alpha \cdot2, \beta \cdot 2\}$. 
\end{exer}

\begin{exer}
Show that if $\gamma$ is a mingling of $\alpha$ and 
$\beta$ that $\gamma< \max \{ \alpha \cdot 3, \beta \cdot 3\}$. 
(Hint: use Cantor nornal form).
\end{exer}





\end{document}
