\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}