\documentclass{amsart}
\usepackage{amssymb}



\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}}
\newcommand{\zfc}{\text{ZFC}}
\newcommand{\zf}{\text{ZF}}
\newcommand{\zfm}{\text{ZF}^{-}}
\newcommand{\sP}{\mathcal{P}}
\newcommand{\pr}{\text{pr}}
\newcommand{\cl}{\text{cl}}
\newcommand{\trcl}{\text{tr cl}}
\newcommand{\rank}{\text{rank}}




\begin{document}

\addtocounter{section}{2}
\addtocounter{exer}{19}

\section{Axioms of Set theory} \label{secaxioms}




Before presenting the axioms of set theory, we first make a 
few basic comments about the relevant first order logic. We will 
give a somewhat more detailed discussion later, but for now 
just say what we need to present the axioms. We work in 
the \emph{language of set theory}. This allows only a single 
binary relation symbol $\in$ in the language (all first-order
languages allow a symbol for equality; thus these are are the only
two relation symbols allowed). There are no function or 
constant symbols. 

A formula of set theory is, roughly speaking, any expression 
built up, using the standard logical operations, from these two 
binary relation symbols. More precisely, our language allows 
in addition to these two symbols the symbols: $\exists$, $\forall$, 
$\wedge$, $\vee$, $\neg$, $\rightarrow$, $\leftrightarrow$, 
$($, $)$, and an infinite list of variables $x_1, x_2, x_3, \dots$ (the 
reader will recall that only $\neg$, $\vee$, and $\exists$ suffice, for
example). An \emph{atomic formula} is an expression of the form 
$x_i \in x_j$ or $x_i \approx x_j$ (formally we should use a 
different symbol for the equality symbol in the formal language 
versus real equality). The collection of formulas (in the language of
set theory) is then defined recursively by the following:

\begin{enumerate}
\item
An atomic formula is a formula.
\item
If $\phi$, $\psi$ are formulas, so are $(\phi \wedge \psi)$, 
$(\phi \vee \psi)$,
$(\neg \phi)$, $(\phi \rightarrow \psi)$, $(\phi \leftrightarrow \psi)$,
$\exists x_i\, \phi$, $\forall x_i\, \phi$. 
\end{enumerate}


We will drop parentheses when the meaning is clear. An occurance 
of a  variable $x$ in the formula $\phi$ 
is \emph{free} if it is not within the scope of an $\exists x$ or $\forall x$
quantifier. The free variables of a formula are the variable which have 
a free occurance in the formula. More formally, this notion is defined
recursively through the following:

\begin{enumerate}
\item
A variable is free in an atomic formula if it occurs in the formula. 
\item
A variable is free in $(\phi \wedge \psi)$, 
$(\phi \vee \psi)$,
$(\neg \phi)$, $(\phi \rightarrow \psi)$, or $(\phi \leftrightarrow \psi)$ iff
it is free in $\phi$ or $\psi$. 
\item
A variable is free in $\exists x_i\, \phi$, or $\forall x_i\, \phi$
if it is free in $\phi$ and not equal to $x_i$. 
\end{enumerate}

We frequently write $\phi(x_1,\dots,x_n)$ to indicate that $x_1,\dots,x_n$
are the free variables in $\phi$. A formula is said to be a
\emph{sentence} if it has no free variables. For example, the sentence
$\phi= \exists x\ \exists y\ \exists z\ (y \in x \wedge z \in x \wedge 
\forall w\ ( w \in x \rightarrow (w =y \vee w =z)))$ asserts that 
there is a set with exactly two elements. 






We present now the formal axioms of $\zfc$ set theory. The axioms, for the
most part, describe allowable rules of set formation. These rules
encompass the methods of forming sets used commonly in 
mathematics. That some rules are necessary is evident from Russell's
paradox: if the collection $S=\{ x \colon x \notin x\}$ were a set, then
we would have a contradiction as $S \in S \rightarrow S \notin S$ and
$S \notin S \rightarrow S \in S$. 

The axioms of set theory are all expressed in the language of set 
theory which has a single binary relation symbol $\in$. 
We now list the axioms with brief comments after them. 
\medskip

({\bf Extensionality}) $\forall x\ \forall y\ (x=y \leftrightarrow 
\forall z\ (z \in x \leftrightarrow z \in y))$. 
\medskip

This asserts two sets are equal iff they have the same elements, that is,
a set is determined by its elements. 
\medskip

({\bf Pairing}) $\forall x\ \forall y\exists z\ (x \in z \wedge y \in z)$.
\medskip

This say that for any sets $x$, $y$, we can find a set containing 
both $x$ and $y$. 
\medskip

({\bf Union}) $\forall x\ \exists u \ \forall y\ \forall z (y \in x \wedge 
z \in y \rightarrow z \in u)$. 
\medskip

This says that for all sets $x$, a set $u$ exists which contains the union
of $x$ (i.e., the union of all the elements of $x$). 
\medskip


({\bf Infinity}) $\exists x\ (\emptyset \in x \wedge \forall y\ 
(y \in x \rightarrow y \cup \{ y\} \in x))$. 
\medskip

This asserts that a set $x$ exists which contains the emptyset, and is
closed under the successor function. This gives that a set containing
all of the $S^n(0)$ exists, that is, an infinite ordinal exists. 
\medskip




({\bf Power Set}) $\forall x\ \exists y\ \forall z\ (z \subseteq x \rightarrow 
z \in y)$. 
\medskip

Here ``$z \subseteq x$'' abbreviates $\forall w\ (w \in z \rightarrow 
w \in x)$. This clearly asserts that a set containing the power set 
of $x$ exists. 
\medskip


({\bf Comprehension Scheme}) For each formula $\phi(x,z,w_1,\dots,w_n)$
the axiom $$\forall z\ \forall w_1,\dots, w_n\ 
\exists y\ \forall x\ (x \in y \leftrightarrow (x \in z \wedge 
\phi(x,z,w_1,\dots,w_n))).$$ 
\medskip


This says that for any set $z$ and parameters $w_1,\dots, w_m$, 
the set $y=\{ x \in z \colon \phi(x,z,w_1,\dots,w_n)\}$ exists. 
We will, in fact, use this common mathematical notation for describing
this set. Note that $\phi$ is not allowed to refer to $y$ (i.e.,
$y$ cannot occur as a free variable in $\phi$), that is, we are not
allowed to define $y$ in terms of itself (this would easily 
give a contradiction).

\medskip
({\bf Replacement Scheme}) For each formula $\phi(x,z,w_1,\dots,w_n)$
the axiom 
$$ \forall a\ \forall w_1,\dots w_n\ [ \forall x \in a \ \exists z 
\phi(x,z,w_1,\dots,w_n) \rightarrow \exists b\ \forall x \in a\ 
\exists z \in b\ \phi(x,z,w_1,\dots,w_n)].$$
\medskip

This says we can, for all sets $a$, and parameters $w_1,\dots,w_n$ 
find a set $b$ large enough to collect the range of a definable 
``function'' (defined by $\phi$) applied to the set $a$. Note that
we are anot assuming that this ``function'' actually exists as a set
(if it did, we wouldn't need this axiom). 


The remaining axiom of $\zf$, the foundation axiom, is a little different
from the previous ones in that it is not a set existence axiom, but
rather resticts the universe of sets. The effect of this axiom
is to restrict our attention to the collection of well-founded sets. 
Adding the axiom to $\zf$ is, in some sense, not critical as
we could always just choose to restrict our attention to these 
sets (a more precise discussion of this point will be given later).


\medskip
({\bf Foundation}) $\forall x\ [ (\exists y\ y \in x) \rightarrow 
(\exists y\ (y \in x \wedge \neg \exists z\ (z \in x \wedge z \in y)))]$.
\medskip

This axiom asserts that the $\in$ relation on every set is well-founded. 
That is, given any non-empty set $x$, an $\in$-minimal element
$y$ of $x$ can be found. Note that this is true for the ordinals 
by definition, without the axiom of foundation. Foundation is asserting
this is true for every set. 


This complete the axiom scheme $\zf$. The scheme $\zfc$ consists of the
$\zf$ axioms plus the axiom of choice ($\ac$):


\medskip
({\bf Axiom of Choice}) $\forall x\ \exists r\ (r\ \text{well-orders}\ x)$
\medskip

We leave it to the reader to write out ``$r$ well-orders $x$'' in 
the first order language of set theory. 




We now fix some fairly standard terminology, proving along the way
that the relevant sets exist. If $\phi$ is a formula in the language of
set theory, say $\phi=\phi(x,z,w_1,\dots,w_n)$, and $w_1,\dots, w_n$ are 
sets, we frequently write
$$y=\{ x \in z \colon \phi(x,z,w_1,\dots,w_n)\}$$ to denote the set 
$y$ obtained by applying the comprehension axiom to $\phi$ and the 
set $z$ (and parameters $w_1,\dots, w_n$; note that $y$ is not allowed
to be free in $\phi$, this is not a problem as we can always change the name
of the set from $y$ to something else). 


\begin{exer} Show that there is a unique empty set, that is, a unique
set which has no elements.
\end{exer}



\begin{exer} Show that for any sets $x_1,\dots,x_n$, the set
$y=\{ x_1,\dots,x_n\}$ exists. More precisely, show there is a unique set $y$
such that $\forall z\ (z \in y \leftrightarrow 
(z=x_1 \vee \dots \vee z= x_n))$.
\end{exer}


We define the \emph{ordered pair} $\langle x,y\rangle$ by:
$\langle x,y\rangle = \{ \{ x\}, \{ x,y \} \}$. This is well-defined by
the previous exercise.


\begin{exer}
Show that if $\langle x,y \rangle=\langle x', y' \rangle$ then 
$x=x'$ and $y=y'$. Thus, this serves as a coding function. 
\end{exer}


For each set $x$, there is a unique set $\cup x$ such that 
$\forall z\ (z \in \cup x \leftrightarrow \exists y\ (y \in x \wedge 
z \in y))$. To see this, first apply the union axiom to get a set 
$u$ such that $\forall y\ \forall z\ (y \in x \wedge z \in y \rightarrow 
z \in u)$. Then apply the comprehension axiom to $u$ to form 
$\{ z \in u \colon \exists y\ (y \in x \wedge z \in y)\}$. 
Frequently one thinks of $x$ as a ``collection'' of sets in writing
$\cup x$, in which case we think of $\cup x$ as the union of the
sets in this collection. Note that $x \cup y = \cup \{ x,y\}$. 


For each non-empty set $x$ there is also a unique set $\cap x$ such that
$\forall z\ (z \in \cap x \leftrightarrow \forall y\ (y \in x \rightarrow 
z \in y))$. Again, $x \cap y =\cap \{ x,y\}$. 

\begin{exer} Show $\cap x$ exists and is uniquely determined. 
\end{exer}


For sets $x,y$, we let $x-y$ denote $\{ z \in x \colon z \notin y\}$,
which clearly exists by comprehension. 

For sets $A$, $B$ we define their cartesian product $A\times B$ 
to be the set $\{ \langle x, y \rangle \colon x \in A \wedge 
y \in B \}$. This exists by applying the replacement axiom 
twice, first to show that for each $y \in B$ that $A \times \{ y\}$
exists, and then to show $A \times B$ exists (using also the
comprehension axiom). Details are in the text. 

We define a \emph{relation} to be a set all of whose elements are
ordered pairs. If $R$ is a relation, we define 
$\dom(R)=\{ x \colon \exists y\ (\langle x, y\rangle \in R) \}$. 
Likewise, we define $\ran(R)= \{ y \colon: \exists x\ (\langle x,y
\rangle \in R) \}$. 

\begin{exer} Show that for any relation $R$ that $\dom(R)$, 
$\ran(R)$ are indeed sets. 
\end{exer}


If $R$ is a relation, the inverse relation $R^{-1}$ is defined by
$R^{-1}= \{ \langle x,y \rangle \colon \langle y,x \rangle \in R\}$. 
We define the notions of the relation $R$ being a function, 
a one-to-one function, an onto function, a bijection, etc., in the usual way. 
We employ the usual notion $f \colon A \to B$ to denote 
$f$ is a function, $\dom(f)=A$, and $\ran(f) \subseteq B$. 
We say $f$ is a \emph{partial} function from $A$ to $B$ if we only 
require $\dom(f) \subseteq A$. 


Having officially now defined the notion of (binary) relation, 
the formal definitions of partial order, linear order, 
well-order, etc., can now be given. They are, of course, the same 
as those given informally earlier. We can now say that working within $\zf$
set theory we have given a precise definition of the ordinals. 


We wish sometimes to refer to collections of sets which are not necessarily
sets themselves, in fact $\zf$ will prove that these collections are not sets. 
Consider first the collection of all sets, which we might
write as $\{ x \colon x=x \}$. Note that this is not a legitimate
application of the comprehension axiom, and so not guananteed to be a set. 
In fact, the Russell paradox argument given earlier is now a proof that
this is not a set. More precisely, $\zf$ proves that 
$\neg \exists x\ \forall y\ (y \in x)$. 

\begin{exer}
Go back over the proof of Russell's paradox and give a precise proof
that $\zf$ proves the above statement. 
\end{exer}

How then are we to deal with such collections which are not sets, and does the 
word ``collection'' here really mean? We answer these questions with the
notion of a \emph{class}. Formally, a class just means a formula $\phi$
in the language of set theory. $\phi$ may have free variables 
which we regard as set parameters. Intuitively, we are thinking of $\phi$
as representing the collection of sets which satisfy $\phi$. 
For example we let $V$ (the universe of all sets) be the class 
$\phi=(x \approx x)$. Thus when we write ``$x \in V$'' we officially mean
$x=x$ (which of course is always true). Another example is the class
$\on$ of all ordinals. This corresponds to the formula $\phi(x)$ which
asserts that $x$ is a transitive set well-ordered by the $\in$ relation. 
Again, when we say ``$x \in \on$'', this abbreviates $\phi(x)$. 
Be aware that the notion of a class is an abbreviation employed in the
meta-theory, not a definition within $\zf$ set theory. 
Thus a statement such as ``for every class C we have $\dots$'' 
denotes a schema of metatheorems, not a theorem (or even statement)
in the language of set theory. A person who objects to this can either
make the above translations and not consider statements 
such as ``for every class C $\dots$,'' or else formalize the metatheory
(e.g., we might consider the metatheory to be a model of Peano arithmetic,
and view formulas as coded by integers). Note that the well-foundedness
principle for ordinals extends to classes. That is, 
if $C \subseteq \on$ is a non-empty class, then $C$ contains a
least element (again, this is a schema in the metatheory, not a 
formal statement in $\zf$). For any particular class $C$, this
can be proved exactly as the proof before for sets. 


\begin{exer} (Burali-Forti Paradox) Show that the class $\on$
is proper, that is, is not a set. More precisely, show that it
is a theorem of $\zf$ that $\neg \exists x\ \forall y \ 
(y \in \on \rightarrow y \in x)$. (hint: use theorem 2.6 and 
lemma 1.8.)
\end{exer}



We can now give a precise definition, within $\zf$, of the natural
numbers, and of the notion of ``finite.'' 

\begin{defn}
$n$ is a natural number iff $(\text{``$n$ is an ordinal''} \wedge 
\forall m \leq  n \ (m=0 \vee \exists \alpha\ m= S(\alpha)))$. We say
a set is \emph{finite} if it can be put in bijection with a natural
number. 
\end{defn}


Note that the above definition defines the natural numbers as a
class. Indeed, without the axiom of infinity it can be a proper class.
However, with the axiom of infinity the set of natural numbers 
exists. To see this, let $x$ be a set as given by the infinity axiom, that is,
$0 \in x$ and $\forall y \in x\ (S(y) \in x)$. We claim that $x$ contains
all of the natural numbers. Suppose not. Let $C$ be the class of natural
numbers which are not in $x$. Then $C$ has a least element, say 
$m$. Clearly $m \neq 0$ as otherwise $m \in x$. By definition
of natural number, $m$ is a successor, say $m=S(k)$. But then
$k \in x$ by minimality of $m$, and thus $m=S(k) \in x$ by the
property of $x$. 
This shows that a set containing the natural numbers exists, and 
by compehension the set of natural numbers exists. We denote this set
by $\omega$. 



\section{Transfinite Recursion}

Definitions by transfinite recursion occur frequently in mathematics and
in set theory in particular. We prove a theorem which says that 
such definitions are legitimate. One common situation is in defining
a function by recursion on an ordinal (or equivalently, a well-ordered 
set). However other situations also arise. First, we sometimes want to use more
general well-founded relations. For example, we may wish to use the
$\in$ relation on a set $x$ (which is well-founded by the
foundation axiom). Secondly, we often wish to do a transfinite 
recursion on a proper class such as $\on$ or $V$ itself. We wish to show
that in all cases this is legitimate. 


At the risk of slight redundancy, we first prove the theorem for sets,
that is, where the domain of the function we are trying to define 
is a set. Then we prove the version for classes, which is really the same
proof if we add the appropriate words. 


\begin{thm} (Set Transfinite Recursion) \label{trans1}
Let $(A,\prec)$ be a set with a well-founded relation. Let $F \colon 
V \times A \to V$ be a class function. That is, $F(x,a,y)$ is a formula
in set theory such that $\zf$ proves that $\forall x \ \forall a \in A\ 
\exists ! y\ F(x,a,y)$. Then there is a unique function $G \colon 
A \to V$ ($G$ is a set) such that $\forall a \in A\ 
[G(a)= F(G \restriction \pr(a),a)]$. 
\end{thm}

Note: in this theorem, $\pr(a)$ denotes the set of predecessors 
$\{ b \in A \colon b \prec a\}$. Also, note that
we are not assuming $\prec$ is transitive, just well-founded. 

Note that theorem~\ref{trans1} is still a schema in 
the meta-theory as it talks about a class function $F$. Of course,
$F$ could be a set as well. 

\begin{exer} Formulate a version of the transfinite recursion
theorem which can be expressed as a statement in $\zf$. You might want to
read the proof of theorem~\ref{trans1} first to suggest what hypotheses
to put on the set function $F$.
\end{exer}


\begin{proof}
For $a \in A$ define $\cl(a) \subseteq A$ by $b \in \cl(A)$ iff 
$\exists f\ \exists n\ (f \text{ is a function } \wedge n \in \omega 
\wedge \dom (f)=n \wedge f(0)=a \wedge f(n-1)=b \wedge \forall 
i <n \ (i >0  \rightarrow f(i) \prec f(i-1)))$. $\cl(a)$ is a set
by comprehension. $a \in \cl(a) \subseteq A$, and $\cl(a)$ is 
the ``downward'' closure of $a$ under $\prec$. In particular, 
if $b \prec a$ then $\cl(b) \subseteq \cl(a)$. 

For $a \in A$, say a function $g$ is an $a$-approximation 
if $\dom(g)=\cl(a)$ and $g$ satisfies the recursive definition on
$\cl(a)$, that is, for all $b \in \cl(a)$ we have 
$g(b)=F(g \restriction \pr(b),b)$. First we claim that for all 
$a \in A$ if $g_1,g_2$ are $a$ approximations then $g_1=g_2$. 
If not, let $a$ be $\prec$ minimal such that this fails, and
let $g_1, g_2$ witness the failure. For $b \prec a$, 
$g_1 \restriction \cl(b)$, $g_2 \restriction \cl(b)$ are 
both $b$-approximations and so by minimality $g_1(b)=g_2(b)$. 
So, $g_1 \restriction \pr(a)=g_2 \restriction \pr(a)$. But then 
$g_1(a)=F(g_1 \restriction \pr(a),a)=
F(g_2 \restriction \pr(a),a)=g_2(a)$, a contradiction. 

Next we claim that for any $a \in A$ an $a$-approximation exists. 
Again, assume this fails and let $a$ be $\prec$ minimal such that
an $a$-approximation does not exist. So for all $b \prec a$, a unique
$b$-approximation exists. Let $g'$ be the union of all the $b$-approximations
for all $b \prec a$. This exists by the replacement axiom applied to the
formula $\phi(b,x)=$``$x$ is a $b$-approximation.'' 
$g'$ is a function. To see this we must show that if 
$b_1, b_2 \in A$, $g_1,g_2$ are $b_1,b_2$ approximations
respectively, and $c \in \cl(b_1) \cap \cl(b_2)$ then 
$g_1(c)=g_2(c)$. This follows since $g_1 \res \cl(c)$, $g_2 \res \cl(c)$
are both $\cl(c)$-approximations and hence are equal by the 
previous paragraph. In particular $g_1(c)=g_2(c)$. Let 
$g=g' \cup \{ \langle a, F(g'\restriction \pr(a),a) \rangle \}$. 
Then $g$ is a function 
with domain $\cl(a)$ and is an $a$-approximation. 

Finally, define $G$ to be the union of all the $a$-approximations for
$a \in A$. This is a set by the replacement axiom as before. 
By the existence and uniqueness claims, $G$ is a function with 
domain $A$, and clearly $G$ satisfies the recursive definition.
\end{proof}


We now consider the class version of the transfinite recursion
theorem. Suppose now $A$ is a class and $\prec$ is a class
relation on $A$ which is well-founded (meaning every non-empty
set which a subset of $A$ has a $\prec$ least element). Suppose
as above that $F \colon V \times A \to V$ is a class function. 
For the recursive condition on $G$ to even make sense, we must
require that for $a \in A$ that $\pr(a)$ is a set. We claim that
this is enough.


\begin{thm} (Class Transfinite Recursion Theorem) \label{trans2}
Let $(A, \prec)$ be a class $A$ together with a class 
relation $\prec$ on $A$ which is well-founded. Assume that 
for every $a \in A$ that $\pr(a)$ is a set. 
Let $F \colon 
V \times A \to V$ be a class function. 
Then there is a unique class function $G \colon 
A \to V$ such that $\forall a \in A\ 
[G(a)= F(G \restriction \pr(a),a)]$. 
\end{thm}


\begin{proof}
By assumption for all $a \in A$ we have that $\pr(a)$ is a set. 
We claim that for all $a \in A$ that $\cl(a)$ is a set. 
To see this, first define for each natural number $n$
the class $\cl_n(a)$ which is defined exactly as $\cl(a)$ except that
we require that the domain of the function $f$ used in the definition
be $n$. We claim that for each $n$ that $\cl_n(a)$ is a set. That is, 
we claim that $\forall a \in A\ \forall n \in \omega \ 
\exists z\ \forall b\ (b \in z \leftrightarrow 
\exists f (f \text{ is a function } \wedge \dom(f)=n \wedge 
f(0)=a \wedge f(n-1)=b \wedge \forall i< n-1 \ ( f(i+1) \prec f(i))))$.
If this claim fails, then we may fix $a \in A$ such that the claim
fails for some $n \in \omega$, and then fix $n \in \omega$ minimal
such that the claim fails for this integer and $a$. By minimality,
$\cl_{n-1}(a)$ exists. Note that $\cl_n(a)$ is $\cl_{n-1}(a)$
together with the $b \prec x$ for $x \in \cl_{n-1}(a)$. 
For each $x \in \cl_{n-1}(a)$ the set of $b \prec x$ is a set
by assumption. Replacement then gives that $\cl_n(a)$ is a set. 
The relation $R(n,z) \leftrightarrow z = \cl_n(a)$ is definable, and
thus replacement applied to the set $\omega$ gives that 
$\cl(a)$ exists. 

For $a \in A$ we now define the notion of an $a$-approximation
exactly as before. We prove as before that for all $a \in A$ that 
$a$-approximations exist and are unique; note that the use of replacement
in construction the function $g'$ in the previous proof is still o.k.
since $\pr(a)$ is a set. Finally, $G$ is defined as before to be the
union of the $a$-approximations, but this is now a class function. 
That is, $G(a)=z \leftrightarrow \exists g\ (g$ is an $a$-approximation
$\wedge \ g(a)=z)$. 
\end{proof}








We finish this section with a note on the axiom of choice. $\ac$
has several equivalent formulations, each of which is useful.
Let $\ac_1$ be the statement as in our official definition, that is, 
$\ac_1= \forall x\ ($``$x$ can be well-ordered''$)$. Let $\ac_2$ be the
statement that for every non-empty relation $R$ there is a function 
$F$ with $\dom(F)=\dom(R)$ such that $\forall x \in \dom(R) \ (
(x,F(x)) \in R$. 

\begin{thm} ($\zf$) $\ac_1 \leftrightarrow \ac_2$. 
\end{thm}

\begin{proof}
We work in $\zf$ set theory. First assume $\ac_1$ and we show $\ac_2$. 
Let $R$ be a non-empty relation. Let $D=\dom(R)$ and $S=\ran(R)$. 
Let $\prec$ well-order $S$. Let $\phi(x,y)$ be the formula (with parameters
$R$ and $\prec$)
$(x,y) \in R \wedge \forall z \prec y\ (\neg (x,z) \in R)$. 
By comprehension, the set $F=\{ (x,y) \in R \colon 
\phi(x,y) \}$ exists. Clearly $F$ is a function with domain $D$ and
is as required. 

Assume next $\ac_2$, and let $X$ be a set. We must show that $X$ can be 
well-ordered. Let $R$ be the relation $R(A,y) \leftrightarrow 
A \subseteq X \wedge y \in A$. $R$ exists since $\sP(X)$ exists and
thus so does $\sP(X) \times X$, and hence $R$ exists by comprehension (note
that replacement is being used in getting the existence of the cartesian
product). We may assume that $\emptyset \notin X$, for if it is then
we well-order $X -\{ \emptyset \}$ and then well-order $X$ by adding 
$\emptyset$ at the end of the well-order. By $\ac_2$, let $G \colon 
(\sP(X)-\{ \emptyset\})  \to X$ be such that $G(A) \in A$ 
for for all non-empty $A \subseteq X$. 
We now define by transfinite
recursion on the well-founded (set like) class $(\on ,\in)$ a 
class function $F \colon \on \to V$. Namely, let $F$ be such that 
for all $\alpha \in \on$, $F(\alpha)=G(\ran(F \restriction \alpha))$
if $X-\ran(F \restriction \alpha) \neq \emptyset$, and otherwise 
$F(\alpha)=\emptyset$. $F$ exists by the transfinite recursion theorem. 
An immediate induction shows that $F(\alpha) \in X$ or $F(\alpha)=\emptyset$
for all $\alpha \in \on$. Also, the set of $\alpha$ such that $F(\alpha) \in
X$ forms an initial segment of the ordinals. We claim that the class $A$ of
ordinals $\alpha$ for which $F(\alpha) \in X$ is a set. To see this, first note
by an immediate induction that $F$ is one-to-one on $A$. Also, 
$\ran(F) \cap X$ is a set by comprehension, call this set $B$. So 
$\forall x \in B \ \exists ! \alpha \in \on\ (F(\alpha)=x)$. By replacement
and the fact that $F$ is one-to-one on $A$ there is a set which contains
all the $\alpha \in \on$ such that $F(\alpha) \in X$, and thus 
by comprehension $A$ is a set (thus $A$ is an ordinal). 
Next we claim that $F$ is onto, that is, 
$B=X$. Suppose not, and let $\alpha_0$ be the least ordinal not in 
$A$. Thus, $A=\alpha_0$ actually. 
Since $F(\alpha_0)=\emptyset$, we must have $\ran(F \restriction 
\alpha_0)= X$ from the definition of $F$. Thus $F$ is onto. Now we easily 
define a well-order of $X$ by: $x_1 \prec x_2 \leftrightarrow
\exists \alpha_1 < \alpha _2\ (F(\alpha_1)=x_1 \wedge F(\alpha_2)=x_2)$.
(note: $F$ is actually a set since $A$ is, but we don't need this.)
\end{proof}



\begin{exer}
Explain what is wrong with the following ``proof'' in $\zf$ that 
an ill-founded relation $\prec$ on a set $X$ must have an 
infinite decreasing chain: let $S \subseteq X$ be non-empty with no
$\prec$ minimal element. Define by transfinite recursion on 
$\omega$ a function $f \colon \omega \to S$ as follows. Let $f(n)$ be
some element of $S$ such that $f(n) \prec f(n-1)$, which exists since 
$f(n-1)$ is not $\prec$-minimal. Then $\{ f(0),f(1),\dots \}$
is a $\prec$-decreasing chain.
\end{exer}



\section{The Rank Hierarchy}


Working in $\zf$ we now define and develop the basic properties of 
the ``rank hierarchy,'' which the basic picture of the universe of sets. 

\begin{defn}
For $\alpha \in \on$ the set $V_\alpha$ is defined by transfinite
recursion as follows.

\begin{enumerate}
\item
$V_0=\emptyset$.
\item
$V_{\alpha+1}=\sP(V_\alpha)$.
\item
For $\alpha$ limit, $V_\alpha=\bigcup_{\beta < \alpha} V_\beta$.
\end{enumerate}
\end{defn}


\begin{lem}
For all $\alpha \in \on$, $V_\alpha$ is transitive. If $\alpha < \beta \in \on$,
then $V_\alpha \subseteq V_\beta$. 
\end{lem}


\begin{proof}
We first show transitivity. This is trivial for $\alpha=0$ and for $\alpha$
a limit since a union of transitive sets is
transitive. Suppose $x \in y \in V_{\alpha+1}$. Then $y \subseteq V_\alpha$,
so $x \in V_\alpha$. By induction $V_\alpha$ is transitive, so 
$x \subseteq V_\alpha$, and so $x \in V_{\alpha+1}$. 

We show that $V_\alpha \subseteq V_\beta$ by induction on $\beta$
for all $\beta \geq \alpha$. For $\beta=\alpha$ this is trivial. 
For $\beta$ limit this follow immediately from induction. 
So assume $V_\alpha \subseteq V_\beta$ and we show $V_\alpha \subseteq 
V_{\beta +1}$. It is enough to show that $V_\beta \subseteq V_{\beta+1}$,
and this follows from the fact that $V_\beta$ is transitive (i.e., an
element of $V_\beta$ is also a subset of $V_\beta$).
\end{proof}



The above definition did not use the axiom of foundation, that is, 
it is given in $\zfm=\zf-$Foundation. Using foundation,
we can show that this rank hierarchy exhaust the universe of sets. 

\begin{defn}
If $x$ is a set, define the transitive closure of $x$, $\trcl(x)$, 
as follows. First, for $n \in \omega$ define $\bigcup^n (x)$ 
recursively by: $\bigcup^0(x)=x$, $\bigcup^{n+1}(x)= \bigcup 
(\bigcup^n(x))$. Set $\trcl (x)= \bigcup_n (\bigcup^n(x))$. 
\end{defn}

\begin{exer}
Write out a direct $\zf$ definition of $\trcl(x)$
not using the transfinite recursion theorem (i.e., ``unravel''
the recursive definition). 
\end{exer}

Clearly $\trcl(x)$ is the smallest transitive set containing $x$. 



\begin{lem} ($\zf$)
For every $x$ there is an $\alpha \in \on$ such that $x \in V_\alpha$. 
\end{lem}


\begin{proof}
Suppose not, and fix $x$ not in any $V_\alpha$. Let $y=\trcl(\{ x \})$. 
Let $z \in y$ be $\in$-minimal such that $z \notin \bigcup_{\alpha \in 
\on} V_\alpha$. This exists by foundation (note that $x \in y$). 
Since $y$ is transitive, $z \subseteq y$, and by minimality of 
$z$ we have $\forall w \in z\ \exists \alpha\ (w \in V_\alpha)$. 
By replacement, there is an $\alpha \in \on$ such that 
$z \subseteq V_\alpha$, and hence $z \in V_{\alpha+1}$, a contradiction.
\end{proof}

Thus, we may now write $V= \bigcup_{\alpha \in \on} V_\alpha$. 

\begin{defn}
The {\em rank} of a set $x$ is the least $\alpha \in \on$ such that 
$x \subseteq V_\alpha$. 
\end{defn}

Equivalently, $\rank(x)=\alpha$ iff $V_{\alpha+1}$ 
is the least element of the $V$-hierarchy in which $x$ appears 
(since $x \subseteq V_\alpha$ iff $x \in V_{\alpha+1}$). 


\begin{exer}
Show that $V_\alpha=\{ x \colon \rank(x) <\alpha\}$.
\end{exer}


\begin{lem} \label{rankcomp}
For any set $x$, $\rank(x)=\sup \{ \rank(y)+1 \colon y \in x\}$.
\end{lem}


\begin{proof}
Let $\alpha=\sup \{ \rank(y)+1 \colon y \in x\}$. Since for every 
$y \in x$ we have $y \in V_{\rank(y)+1} \subseteq V_\alpha$, 
we have $x \subseteq V_\alpha$, so $\rank(x) \leq \alpha$. 
On the other hand, if $\beta < \alpha$, then there is a $y \in x$
such that $\rank(y) +1 > \beta$, and hence $y \notin V_\beta$. 
Thus, $x$ is not a subset of $V_\beta$ so $\rank(x) > \beta$. 
\end{proof}



The previous lemma is not only useful for computing ranks, but it
suggests another way to define rank. Namely, we could 
define $\rank(x)$ by transfinite recursion on the class $V$ with the 
$\in$-relation by the recursion 
$\rank(x)=\sup \{ \rank(y)+1 \colon y \in x\}$. One advantage of this is 
that the transfinite recursion theorem does use the power set axiom, 
and thus neither does this definition of $\rank(x)$. Another advantage is that
this computes $\rank(x)$ is a purely ``local'' manner. To see this,
we first define the notion of rank for an arbitrary well-founded
relation. 


\begin{defn} \label{defrank}
Let $A$ be a class and $\prec$ a set-like well-founded relation on
$A$. For $a \in A$, define by transfinite recursion 
$\rank(a)=\sup \{ \rank(b) \colon b \in A \wedge b \prec a\}$.
\end{defn}

Thus, definition~\ref{defrank} generalizes the computation of
lemma~\ref{rankcomp} to arbitrary well-founded relations. 


\begin{lem}
For any set $x$, $\rank(x)$ is the rank of the $\in$ relation
on the set $\trcl(x)$. 
\end{lem}

\begin{proof}
For $z \in \trcl(x)$, let $|z|$ denote the rank of $z$ in the 
$\in$ relation on $\trcl(x)$. 
We show by induction on $z \in \trcl(x)$ that 
$|z|=\rank(z)$. We have $|z|= \sup \{ |w|+1 \colon w \in z \wedge 
w \in \trcl(z)\}= \sup \{ \rank(w)+1 \colon w \in z \wedge 
w \in \trcl(z)\}= \sup \{ \rank(w)+1 \colon w \in z \}= 
\rank(z)$. The second equality uses induction, and the third 
the fact that $\trcl(x)$ is transitive. 
\end{proof}



\begin{exer}
Show that every ``real'' $x \in \omega^\omega$ has rank $\omega$. 
Show that the set of reals has rank $\omega+1$, and the collection
of Borel subsets of the reals has rank $\omega+2$. 
\end{exer}


\begin{exer}
Show that every function $f \colon \R \to \R$ has rank $\omega+3$,
but can be coded as a set of rank $\omega+1$.
\end{exer}


\begin{exer}
Show that for every ordinal $\alpha$, $\rank(\alpha)=\alpha$.
\end{exer}


\begin{exer}
Show that for any set $x$, $\rank(\sP(x))=\rank(x)+1$. 
Show that for any $x,y$ that $\rank(x \cup y)=\max \{ \rank(x),
\rank(y)\}$ and $\rank(x \cap y)\leq \min \{ \rank(x),
\rank(y)\}$.
\end{exer}




\begin{lem}
Let $A$ be a set and $\prec$ a well-founded relation on $A$. 
Then $\tilde{A}=\{ |a| \colon a \in A\} \in \on$. 
\end{lem}

\begin{proof}
We must show that if $\alpha=|a|$ and $\beta < \alpha$, then 
$\beta=|b|$ for some $b \in A$. Suppose $\beta< \alpha$ is least so
that this fails. Let $\gamma < \beta$ be least such that 
$\gamma \in \tilde{A}$, say $\gamma= |c|$. Then 
$|c|= \sup\{ |d|+1 \colon d \in A \wedge d \prec c \}
\leq \beta$, since each $|d|< \beta$. 
\end{proof}



From this we obtain the following.


\begin{lem}
Let $A$ be a set of cardinality $\kappa$ and $\prec$ a well-founded
relation on $A$. Then $|A| < \kappa^+$.
\end{lem}


\begin{proof}
If $|A| \geq \kappa^+$, then from the previous lemma every
$\alpha< \kappa^+$ would be the rank of some $a \in A$. This
would give a one-to-one mapping of $\kappa^+$ into $A$, 
a contradiction.
\end{proof}









\end{document}
