\documentclass{amsart} \usepackage[parfill]{parskip} \usepackage{graphicx} \usepackage{amssymb, latexsym} \usepackage{epstopdf} \usepackage{color} \DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png} \textwidth = 6.5 in \textheight = 9 in \oddsidemargin = 0.0 in \evensidemargin = 0.0 in \topmargin = 0.0 in \headheight = 0.0 in \headsep = 0.0 in \parskip = 0.2in \parindent = 0.0in \pagestyle{plain} \newcommand{\ord}{\text{ord}} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{cor}[theorem]{Corollary} \newtheorem{prop}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \theoremstyle{definition} \newtheorem*{definition}{Definition} \newtheorem*{defn}{Definition} \newtheorem{example}{Example} \theoremstyle{remark} \newtheorem*{notation}{Notation} \newtheorem*{note}{Note} \newtheorem*{recall}{Recall} \newsavebox{\savepar} \newenvironment{xbox}{\begin{lrbox}{\savepar} \begin{minipage}[c]{\textwidth}} {\end{minipage}\end{lrbox}\fcolorbox{black}{green}{\usebox{\savepar}}} \renewcommand{\baselinestretch}{1.3} \begin{document} \setcounter{section}{7} \section{Transfinite Numbers in ZF} \subsection{Transitive Sets} \hfill As noted in the previous chapter, the Axiom of Infinity asserts the existence of an infinite set $x$ containing each of the following sets as an element: \[ a_0 = \emptyset, \, a_1 = \{ \emptyset \}, \, a_2 = \big\{ \emptyset, \{ \emptyset \} \big\}, a_3 = \Big\{ \emptyset, \{ \emptyset \}, \big\{ \emptyset, \{ \emptyset\} \big\} \Big\}, \dots \] \begin{defn} A \emph{pure set} is any set built up progressively from the empty set and the operation `set of'. Symbolically, a pure set consists entirely of $\emptyset$'s and \{ \}'s. \end{defn} The pure sets $a_0, a_1, a_2, \dots $can be used to re-define cardinal and ordinal numbers within the framework of ZF in such a way that the set paradoxes are avoided. \begin{defn} A set $a$ is \emph{transitive} iff whenever $x$ is an element of $a$, all elements of $x$ are also elements of $a$. Expressed in terms of a formula with one free variable, $a$ is transitive iff \[ \tau (a) := \forall x \, \forall y \, \Big( \big[ ( y \in x) \land (x \in a )\big] \implies y \in a \Big). \] \end{defn} \begin{example} The sets $a_0, a_1, a_2$ and $a_3$ are transitive sets. \begin{xbox} However, $\big\{ \{ \emptyset \}\big\}$ is not transitive, because..... Hence, not all pure sets are transitive. \end{xbox} \end{example} \begin{prop} A set $a$ is transitive if and only if every element of $a$ is also a proper subset of $a$ (that is, $x \in a \implies x \subset a$). \end{prop} \begin{xbox} \begin{proof} \end{proof} \end{xbox} \begin{xbox} \begin{note} Although every element in a transitive set is also a proper subset, it need not be the case that every proper subset of a transitive set is also an element. \end{note} \end{xbox} \begin{prop} \hfill \begin{enumerate} \item The power set of a transitive set is transitive. \item Let $c$ be a \emph{set} of transitive sets. The $\bigcup c$ and $\bigcap c$ are transitive sets. \end{enumerate} \end{prop} \begin{xbox} \begin{proof} \end{proof} \end{xbox} \subsection{Ordinals} \hfill \begin{xbox} \begin{defn} A transitive set is an \emph{ordinal} iff each of its elements is also a transitive set. Expressed in terms of a formula with one free variable, $a$ is an ordinal iff \[ \vartheta(a) := \tau(a) \land \dots \] \end{defn} \end{xbox} \begin{example} The sets $a_0, \, a_1,\, a_2$ and $a_3$ are ordinals. \begin{xbox} A transitive set that is not an ordinal is.... \end{xbox} \end{example} \begin{xbox} \begin{note} An ordinal is a set in which ``$\in$" is a transitive relation. \end{note} \end{xbox} \begin{notation} The class of all ordinals, $\{ a \, | \, \vartheta(a) \}$ is denoted by $\mathcal{O}$. We will prove later that $\mathcal{O}$ is a proper class. \end{notation} \begin{prop} \hfill \begin{enumerate} \item Every element of an ordinal is also an ordinal. \item For every ordinal $a$, $a \cup \{ a \}$ is also an ordinal. \end{enumerate} \end{prop} \begin{xbox} \begin{proof} \end{proof} \end{xbox} \begin{theorem}[Law of Trichotomy for Ordinals] For any two ordinals $a$ and $b$, exactly one of the following is true: $a \in b$ or $a = b$ or $b \in a$; that is, any two ordinals are comparable with respect to the membership relation. \end{theorem} \begin{proof} This proof, although rather complicated, is a good illustration of the usefulness of the Axiom of Foundation. First, we express the relationship of comparability as a formula with two free variables: \[ \kappa(a, b) := \big[ (a \in b) \lor (a=b) \lor (b \in a) \big]. \] Note that the Axiom of Foundation precludes the possibility of any two of $a \in b$ or $a = b$ or $b \in a$ being true at the same time. We must prove the statement $\forall a \forall b \, \big[ \vartheta(a) \land \vartheta(b) \ \Rightarrow\kappa(a,b)\big]$. Assume the statement is false. Let $a^0$ be an ordinal such that there exists an ordinal $b^0$ that is not comparable to $a^0$; symbolically, $\lnot \kappa(a^0, b^0)$. We want to find the `smallest' pair of ordinals that are not comparable. By the previous proposition, $a^0 \cup \{ a^0 \}$ is also an ordinal and therefore a set. By the Subset Axiom, \[ x = \bigg\{ a \in a^0 \cup \{ a^0 \} \, | \, \exists b \,\Big( \vartheta(b) \land [\lnot \kappa(a, b) ]\Big)\bigg\} \] is a set. Since $a^0 \in x$, $x$ is nonempty and so by the Axiom of Foundation, there exists $a^1 \in x$ such that $a^1 \cap x = \emptyset$; that is, there exists an ordinal $b^1$ that is not comparable to $a^1$ (symbolically, $\lnot \kappa(a^1, b^1)$), but every element of $a^1$ is comparable to every other ordinal. In other words, $a^1$ is a `smallest' ordinal that is not comparable with at least one other ordinal. We now use the same approach to find a `smallest' ordinal with which $a^1$ is not comparable. By applying the Axiom of Foundation to the set \[ y = \bigg\{ c \in b^1 \cup \{ b^1 \} \mid \vartheta(c) \land [\lnot \kappa(a^1, c) ]\bigg\}, \] we conclude there exists an ordinal $c^1 \in y$ such that $c^1 \cap y = \emptyset$; that is, there exists an ordinal $c^1$ such that $\lnot \kappa(a^1, c^1)$ but every element of $c^1$ is comparable to $a^1$. We claim that $c^1 \subset a^1$. To prove this, we must show that every element of $c^1$ is an element of $a^1$. So let $d \in c^1$. By construction, $d$ is an ordinal that is comparable to every other ordinal, so either $d \in a^1$ or $d = a^1$ or $a^1 \in d$. If $d = a^1$, then by substitution, $a^1 \in c^1$, contradicting $\lnot \kappa(a^1, c^1)$. If $a^1 \in d$, then since $d \in c^1$, by transitivity of the membership relation among ordinals, $a^1 \in c^1$, again contradicting $\lnot \kappa(a^1, c^1)$. Hence $d \in a^1$ and our claim is proved. Finally, since $c^1$ is a proper subset of $a^1$, let $e \in a^1 \backslash c^1$; that is, $e \in a^1$ but $e \not \in c^1$. By construction, $e$ is an ordinal that is comparable to every other ordinal, so either $e = c^1$ or $c^1 \in e$. However, these both contradict $\lnot \kappa(a^1, c^1)$. Hence, our original assumption that there exist ordinals that are not comparable must be false. \end{proof} \begin{prop}\label{prop:Owellord} The class $\mathcal{O}$ is well-ordered by $\in$; that is: \begin{enumerate} \item $\in$ is a quasi-order on $\mathcal{O}$; \item every nonempty \emph{set} of ordinals has a first element under $\in$. \end{enumerate} \end{prop} \begin{xbox} \begin{proof} \end{proof} \end{xbox} \begin{notation} For ordinals $a$ and $b$, $a \prec b \iff a \in b$. \end{notation} \begin{prop}\label{wellord} \hfill \begin{enumerate} \item Every ordinal is a well-ordered set (under $\prec / \in$). \item Every ordinal $a$ is the set of all ordinals less than $a$; that is, $a = \{ b \in \mathcal{O} \, | \, b \prec a \} = s(a)$. \end{enumerate} \end{prop} \begin{xbox} \begin{proof} \end{proof} \end{xbox} \begin{prop}\label{firstphi} Let $\phi(v)$ be a formula with one free variable. If there exists an ordinal $b$ such that $\phi(b)$, then there exists a first ordinal $b_0$ such that $\phi(b_0)$. \end{prop} \begin{xbox} \begin{proof} (\emph{Hint.} We will prove soon that $\mathcal{O}$ is a proper class, so $\{ b \in \mathcal{O} \, | \, \phi(b) \}$ may not be a set. However, consider $\{ c \in b \, | \, \phi(c) \}$. \end{proof} \end{xbox} \begin{prop}\label{prop:ordord} \hfill \begin{enumerate} \item For any ordinal $a$, $a \cup \{ a \}$ is the immediate successor of $a$ in $\mathcal{O}$. \item If $y$ is a set of ordinals, then $\bigcup y$ is an ordinal. Moreover, $\bigcup y$ is the least upper bound on the set $y$ in the class $\mathcal{O}$; that is, \begin{enumerate} \item for all $a \in y$, $a \preceq \bigcup y$, and \item if $b$ is any other ordinal satisfying for all $a \in y$, $a \preceq b$, then $\bigcup y \prec b$. \end{enumerate} (Note that $y$ may or may not not itself be an ordinal.) \end{enumerate} \end{prop} \begin{xbox} \begin{proof} \hfill \begin{enumerate} \item \item Since every ordinal is a transitive set, $y$ is a set of transitive sets. Hence, by Proposition 8.2 (2), $\bigcup y$ is a transitive set. To show $\bigcup y$ is an ordinal, we must show each one of its elements is a transitive set. So let $x \in \bigcup y$. By definition, there exists $a \in y$ such that $x \in a$. Since $y$ is a set of ordinals, $a$ is an ordinal and so by definition all of its elements are transitive sets. Hence $x$ is a transitive set. Next we show that $\bigcup y$ is an upper bound on the set $y$ in the class $\mathcal{O}$. Let $a \in y$. Since $y$ is a set of ordinals, $a$ is an ordinal, and as just shown, $\bigcup y$ is an ordinal. By the Law of Trichotomy for Ordinals, $a \prec \bigcup y$ or $a = \bigcup y$ or $ \bigcup y \prec a$. We have to show that it cannot be the case that $ \bigcup y \prec a$ (\emph{i.e.} that $\bigcup y \in a$). Assume $\bigcup y \in a$. Since $a$ is an ordinal, it is a transitive set and so by Proposition 8.1, $\bigcup y$ is a proper subset of $a$. Hence, there exists some $x \in a$ such that $x \not \in \bigcup y$. This contradicts the definition of $\bigcup y$. Finally we show that $\bigcup y$ is the least upper bound on $y$ in $\mathcal{O}$. Let $b$ be a different ordinal satisfying $a \preceq b$ for all $a \in y$; we want to show that $\bigcup y \prec b$. By the Law of Trichotomy for Ordinals, since $b \neq \bigcup y$, it suffices to show that it cannot be the case that $b \prec \bigcup y$ (\emph{i.e.} that $b \in \bigcup y$). Again we proceed by contradiction. Assume $b \in \bigcup y $. By definition of $\bigcup y$, there exists some $a \in y$ such that $b \in a$. But then $b \prec a$, contradicting our assumption that $b$ is an upper bound on $y$. \end{enumerate} \end{proof} \end{xbox} \begin{cor} The class $\mathcal{O}$ is a proper class. \end{cor} \begin{proof} Assume $\mathcal{O}$ is a set. Since all of its elements are ordinals, by Proposition \ref{prop:ordord}, $ \bigcup \mathcal{O}$ is itself an ordinal that is the least upper bound on $\mathcal{O}$. By Proposition \ref{prop:ordord}(1), $ \bigcup\mathcal{O} \cup \{ \bigcup \mathcal{O}\}$ is also an ordinal that strictly succeeds all ordinals in $\mathcal{O}$. Hence, $ \bigcup\mathcal{O} \cup \{ \bigcup \mathcal{O}\}$ is an ordinal that is not in $\mathcal{O}$, a contradiction. \end{proof} \begin{theorem}\label{ordnum} For any well-ordered set $x$, there exists a unique ordinal $a$ that is order-isomorphic to $x$. \end{theorem} The proof of this theorem is beyond the scope of this course. \begin{note} This theorem states that each ordinal is a \emph{particular} set that represents all well-ordered sets of a certain order type. Compare this to our naive definition of an ordinal number. \end{note} \begin{defn} An ordinal $a$ is : \begin{enumerate} \item a \emph{successor ordinal} iff there exists an ordinal $b$ such that $a = b \cup \{b\}$; \item a \emph{natural number} iff every ordinal $c \preceq a$ is either $\emptyset$ or a successor ordinal; \item a \emph{limit ordinal} iff $a \neq \emptyset$ and $a$ is not a successor ordinal. \end{enumerate} \end{defn} \begin{note} Every ordinal is either $\emptyset$, a successor ordinal or a limit ordinal. \end {note} \begin{example} The sets $a_1, \, a_2, \, a_3$ are successor ordinals; $a_0, \, a_1, \, a_2, \, a_3$ are natural numbers. \end{example} \begin{theorem} There exists a limit ordinal. \end{theorem} \begin{xbox} \begin{proof} Let $x$ be a set satisfying the Axiom of Infinity and let $y$ be the set of all ordinals in $x$. (Note that $y$ is a set by the Subset Axiom.) We know that $a_0 =\emptyset, a_1 = \{ \emptyset \}, a_2 = \big\{ \emptyset, \{ \emptyset \} \big\}$ and $a_3 = \Big\{\emptyset, \, \{ \emptyset \}, \big\{ \emptyset, \, \{ \emptyset \} \big\} \Big\} $ are all ordinals that are in $x$, and so $y$ is nonempty. By Proposition \ref{prop:ordord} (2), $\bigcup y$ is an ordinal which is the least upper bound of $y$ in the class $\mathcal{O}$. We claim that $\bigcup y$ is a limit ordinal. .... \end{proof} \end{xbox} \begin{notation} From now on, we identify $a_n$ with $n$ for all $n \in \mathbb{N}$. Thus we have: \[ \emptyset \equiv 0;\qquad \{ \emptyset \} \equiv \{ 0 \} \equiv 1; \qquad \big\{ \emptyset, \, \{ \emptyset \} \big\} \equiv \{ 0, 1\} \equiv 2;\qquad \Big\{\emptyset, \, \{ \emptyset \}, \big\{ \emptyset, \, \{ \emptyset \} \big\} \Big\} \equiv \{0, 1, 2\} \equiv 3. \] More generally, $\{0, 1, 2, \dots, n-1 \} \equiv n$. Natural numbers therefore \textbf{are} pure sets. The first limit ordinal is denoted by $\omega$; by Proposition \ref{wellord}(2), $\omega = \{0, 1, 2, \dots, n, \dots \}= \mathbb{N}$ . Its immediate successor is $\omega \cup \{\omega\} = \{0, 1, 2, \dots ; \omega\}$. \end{notation} \begin{lemma}\label{lemma:lim} Let $\lambda$ be a limit ordinal. Then: \begin{enumerate} \item if $a \prec \lambda$, then $a \cup \{ a \} \prec \lambda$; \item $\lambda = \bigcup \{ a \, | \, a \prec \lambda \}$. \end{enumerate} \end{lemma} \begin{xbox} \begin{proof} \end{proof} \end{xbox} \begin{example} As noted above, $\omega = \bigcup \{n \, | \, n \in \mathbb{N}\}$. However, it is also true that $\omega = \bigcup \{2n \, | \, n \in \mathbb{N} \}$. By Proposition \ref{prop:ordord}(2), $\bigcup \{2n \, | \, n \in \mathbb{N} \} $ is the least upper bound on the set of even natural numbers. Since no natural number is greater than or equal to all even natural numbers, the least upper bound is $\omega$. Similarly, $\omega = \bigcup \{2^n \, | \, n \in \mathbb{N}\}$. \end{example} \begin{theorem}[Principle of Transfinite Induction on $\mathcal{O}$] For any formula with one free variable $\phi(v)$, if \begin{enumerate} \item $\phi(0)$, and \item for any ordinal $a$, $\phi(a) \implies \phi\big(a \cup \{ a\} \big)$, and \item for any limit ordinal $\lambda$, $\Big[\phi(a)$ for all ordinals $a \prec \lambda \Big] \implies \phi(\lambda)$, \end{enumerate} then $\phi(a)$ for all ordinals $a$. \end{theorem} \begin{xbox} \begin{proof} (\emph{Hint.} Apply Proposition \ref{firstphi} to the formula $\lnot \phi(v)$.) \end{proof} \end{xbox} \newpage \subsection{Ordinal Arithmetic} \begin{defn} Let $a$ be an ordinal. Then: \begin{enumerate} \item $a + 0 = a$; \item for any ordinal $b$, $a + \big(b \cup \{b\}\big) = (a+b) \cup \{a + b\}$; \item for any limit ordinal $\lambda$, $a + \lambda = \bigcup \{a+b \, | \, b \prec \lambda\}$. \end{enumerate} \end{defn} \begin{note} If $b=0=\emptyset$, then $ b \cup \{b\} =0 \cup \{0\} = \emptyset \cup \{\emptyset\} = \{\emptyset\} = 1$. Hence, for any ordinal $c$, \[ c +1 = c+\big(0 \cup \{0\}\big)=(c+0) \cup\{c+0\} = c \cup \{c\}, \] the immediate successor of $c$. We will use this additive notation from now on. Note that part (2) of the definition can be rewritten in this notation as \[ a + (b+1) = (a+b)+1. \] \end{note} \begin{prop} For all ordinals $a, b$, if $b \neq 0$, then $a +b \prec a$. \end{prop} \begin{xbox} \begin{proof} \end{proof} \end{xbox} \begin{defn} Let $a$ be an ordinal. Then: \begin{enumerate} \item $a \cdot 0 = 0$; \item for any ordinal $b$, $a \cdot \big(b +1) = (a\cdot b) +a$; \item for any limit ordinal $\lambda$, $a \cdot \lambda = \bigcup \{a\cdot b \, | \, b \prec \lambda\}$. \end{enumerate} \end{defn} \begin{prop} \hfill \begin{enumerate} \item The ordinal $0$ is an additive identity; that is, for any ordinal $a$, $a + 0 = 0 + a = a$. \item For any ordinal $a$, $a \cdot 0 = 0 \cdot a = 0$. \item The ordinal $1$ is a multiplicative identity; that is, for any ordinal $a$, $a \cdot 1= 1 \cdot a = a$. \item If $\lambda$ is a limit ordinal, then so is $a + \lambda$ for any ordinal $a$; $a \cdot \lambda$ is a limit ordinal for any nonzero ordinal $a$. \end{enumerate} \end{prop} \begin{xbox} \begin{proof} \hfill \begin{enumerate} \item By definition, $a + 0 = a$, for all ordinals $a$. Next, we use transfinite induction on the formula $\phi(v) := (0 + v = v)$. Since $0+0 = 0$, we have $\phi(0)$. Next let $a$ be an ordinal and assume $\phi(a)$; that is, assume $0+a =a$. Using the definition of ordinal addition and the assumption, \[ 0 + (a \cup \{a\}) = (0+a) \cup \{0+a\} = a \cup \{a\}, \] and so $\phi \big ( a \cup \{a\}\big)$. Finally, let $\lambda$ be a limit ordinal and assume that $\phi(a)$ for all $a \prec \lambda$. Then using the definition and this assumption, \[ 0+ \lambda = \bigcup \{ 0+a \, | \, a \prec \lambda \} = \bigcup \{ a \, | \, a \prec \lambda \} = \lambda, \] by Lemma \ref{lemma:lim}. By the Principle of Transfinite Induction, $\phi(a)$ for all ordinals $a$. \item \item \item Let $\lambda $ be a limit ordinal. By definition, $a + \lambda = \bigcup \{a+b \, | \, b \prec \lambda\}$. Since this is clearly not 0, it suffices to show that it is not a successor ordinal. Suppose $ \bigcup \{a+b \, | \, b \prec \lambda\}= c \cup \{ c \}$ for some ordinal $c$. By Proposition \ref{prop:ordord} (2) $c \cup \{ c \}$ is the least upper bound on $ \{a+b \, | \, b \prec \lambda\}$; since $c \prec c \cup \{ c \}$, $c$ cannot be an upper bound on this set. Hence there exists some $b \prec \lambda$ such that $c \prec a + b$. Since $c \cup \{ c \}$ is the immediate successor of $c$, either $c \cup \{ c \} = a+b$ or $c \cup \{ c \} \prec a+b$. In both cases, $c \cup \{c \} \prec (a+b) \cup \{a + b \} = a + (b \cup \{b\})$. Since $a + (b \cup \{b\})$ is an element of the set $ \{a+b \, | \, b \prec \lambda\}$, this is a contradiction. \end{enumerate} \end{proof} \end{xbox} \begin{xbox} \begin{example} Neither ordinal addition nor ordinal multiplication is commutative: $1 + \omega = \omega$ while $\omega + 1 \succ \omega$, and $2 \cdot \omega =\omega$ while $\omega \cdot 2 = \omega + \omega \succ \omega$. \end{example} \end{xbox} \begin{note} It can be shown that these definitions accord with our previous definitions of ordinal number arithmetic. That is, if $a$ and $b$ are ordinals, then these definitions of $a + b$ and $a \cdot b$ coincide with the definitions of $\ord(a) + \ord(b)$ and $\ord(a) \cdot \ord(b)$ given in Chapter 5. \end{note} %\begin{xbox} %\begin{defn} %Let $a \neq 0$ be an ordinal. Then: [define ordinal exponentiation in a transfinite inductive way] %\end{defn} %\end{xbox} %\begin{xbox} %\begin{note} %Ordinal exponentiation with $a=0$ is defined separately by $0^0 =1$ and for $b \neq 0,\, 0^b =0$. This differs from the definition above because... %\end{note} %\end{xbox} %\begin{xbox} %\begin{example} %$2^\omega = \omega$; note that under cardinal number arithmetic in Chapter 2, $2^\alpha > \alpha$ for all cardinal numbers $\alpha$ by Cantor's Theorem. %\end{example} %\end{xbox} %\begin{prop} %For any ordinals $a, b$ and $c$, %\begin{enumerate} %\item $a^1 = a$ and $1^a=1$; %\item if $\lambda$ is a limit ordinal and $a$ is a nonzero ordinal, then $a^\lambda$ is a limit ordinal; %\item $a^b \cdot a^c = a^{b+c}$; %\item $(a^b)^c = a^{b\cdot c}$. %\end{enumerate} %\end{prop} %\begin{xbox} %\begin{proof} %(\emph{Hint.} For (1) use transfinite induction on $a$, and for (2) and (3) use transfinite induction on $c$.) %\end{proof} %\end{xbox} \begin{note} If we apply these definitions of ordinal arithmetic to 0 and successor ordinals, then we have the usual arithmetic on the natural numbers, $\mathbb{N}$. Thus, all of classical number theory can be formulated in the language of ZF. \end{note} \subsection{Cardinals} \hfill Since the definition of injection and bijection on sets can be expressed in the language of ZF, we still have the notion of when two sets have the same cardinality, and when the cardinality of one set is strictly less than that of another. \begin{defn} An ordinal $a$ is an (\emph{von Neumann}) \emph{cardinal} iff for every ordinal $b \in a$, the cardinality of $b$ is strictly less than that of $a$. In other words, a cardinal is the first ordinal of its cardinality. Expressed in terms of a formula with one free variable, $a$ is a cardinal iff \[ \varkappa(a) := \vartheta(a) \land \forall b \, \Big( b \in a \implies \lnot \, \exists k \, \big[ \beta_{a,b}(k)\big] \Big). \] (Recall that $\beta_{a,b}(k)$ is a formula asserting that $k$ is a bijection from $a$ to $b$.) \end{defn} \begin{xbox} \begin{example} Natural numbers? $\omega$? $\omega \cup \{ \omega\}= \omega +1$? \end{example} \end{xbox} \begin{notation} We let $\mathcal{K} = \{ a \, | \, \varkappa(a) \}$ denote the class of all cardinals. Clearly, $\mathcal{K} \subset \mathcal{O}$. \end{notation} \begin{theorem}[Hartog's Theorem] For any ordinal $a$, there exists an ordinal of strictly greater cardinality. \end{theorem} \begin{proof} We provide only the sketch of a proof. Let $a$ be an ordinal. As a set, $a$ can be well-ordered by the Well-Ordering Theorem, but there is no uniqueness to this well-ordering. It can be shown in ZFC that the collection of \emph{all} well-orderings of $a$ constitutes a set. By Theorem \ref{ordnum}, each element of this set is a well-ordered set that is order-isomorphic to a unique ordinal of the same cardinality as $a$. If we replace each element of this set by that unique ordinal, then by the Axiom of Replacement, the collection of all such ordinals also constitutes a set; call it $x$. Thus, $x$ is the set of all ordinals whose cardinality is the same as that of $a$; in particular, $a \in x$ . By Proposition \ref{prop:ordord}(2), $\bigcup x$ is an ordinal which is the least upper bound of $x$. It can be proved that $\bigcup x$ has cardinality strictly greater than that of $a$. \end{proof} This theorem establishes that, in particular, there are infinitely many \emph{infinite} cardinals. We retain the aleph notation to denote these cardinals. The first infinite cardinal is $\omega$, which in this context is denoted $\aleph_0$. By Hartog's Theorem, there exists an ordinal of cardinality strictly greater than $\omega$, which means there must exist an uncountable ordinal. By Proposition \ref{firstphi}, there exists a first such ordinal. By definition, this ordinal is a cardinal, which will be $\aleph_1$. Repeating this argument, we can generate $ \aleph_2, \, \aleph_3$, and in fact $\aleph_n$ for any natural number $n$. We can go even further. Since $\omega= \mathbb{N}$ is a set, we can apply the Axiom of Replacement to replace each natural number $n \in \omega$ with $\aleph_n$ to obtain a set $a = \{ \aleph_n \, | \, n \in \omega \}$. This is a set of ordinals, so by Proposition \ref{prop:ordord}(2), $\bigcup a$ is an ordinal that succeeds all the $\aleph_n$. Let $\psi(v): = \left(\bigcup a \in v\right) \land \varkappa(v)$; this formula with one free variable that `says' that $v$ is a cardinal that succeeds $\bigcup a$, and so by transitivity, every $\aleph_n$. Using the same argument as in the paragraph above, there exists a first cardinal $\aleph_\omega$ that satisfies $\aleph_n \prec \aleph_\omega$ for all $n \in \mathbb{N}$. This method can be generalized to any successor or limit ordinal. Thus for any $\lambda \in \mathcal{O}$, there exists a corresponding `$\lambda$-th' infinite cardinal, $\aleph_\lambda \in \mathcal{K}$. Thus we have an injection from $\mathcal{O}$ to the class of infinite cardinals, a subclass of $\mathcal{K}$. Since $\mathcal{K} \subset \mathcal{O}$, by the Schr\"{o}der-Bernstein Theorem, $| \mathcal{O} | = |\mathcal{K} |$. (It turns out that the Schr\"{o}der-Bernstein Theorem also holds as a theorem about the cardinalities of classes, although the proof is beyond the scope of this course.) \begin{prop} The class $\mathcal{K}$ is a proper class. \end{prop} \begin{xbox} \begin{proof} \end{proof} \end{xbox} \end{document}