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


\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}{8}
\section{Cumulative Hierarchy of Sets}

\subsection{Definitions and Preliminaries}
\hfill


The ordinals can be used to organize the universe of pure ZF sets into a cumulative hierarchy.  The underlying notion here is that a set is `a whole given \emph{after} its parts'; in other words, the elements must exist in some sense `prior' to the formation of the set.  


\begin{xbox}
Read \emph{The iterative conception of a set} by G. Boolos, up to the end of the second full paragraph on p. 493.
\end{xbox}

\begin{defn}
For any ordinal $a$, we define $V_a$ inductively as follows:
\begin{enumerate}
\item $V_0 = \emptyset$;
\item for any ordinal $a$, $V_{a +1} = \wp(V_a)$;
\item for any limit ordinal $\lambda$, $V_\lambda = \bigcup \{ V_a \, | \, a \prec \lambda \}$.
\end{enumerate}
\end{defn}

\begin{xbox}
\begin{example}
$V_1; \: V_2; \: V_3.$
\end{example}
\end{xbox}


\begin{prop}
\hfill
\begin{enumerate}
\item For any ordinal $a$, $V_a$ is a transitive set.
\item For all ordinals $a$, $V_a \subset V_{a+1}$.
\item For any ordinals $a$ and $b$, if $a \prec b$, then $V_a \subset V_b$.
\end{enumerate}
\end{prop}

\begin{xbox}
\begin{proof}
(\emph{Hint.}  For (1), use transfinite induction on $a$.  For (3),  use transfinite induction on $b$.  What you are proving is $\phi(b)$ for all ordinals $b$, where 
\[
\phi(v) = \forall a \Big[ (\vartheta(a) \land a \in v) \implies \forall x \big[ x \in V_a \implies x \in V_v \big ]
\land \lnot (V_a = V_v) \Big ].
\]
That is, $b$ has the property that if $a$ strictly precedes $b$, then $V_a$ is a properly subset of $V_a$.
% If $b=0$, the statement is trivially true, because no such $a$ exists.  Next, assume that $b$ satisfies the property that for all $a \prec b$, $V_a \subset V_b$; we must show that for all $a \prec b+1$, then $V_a \subset V_{b+1}$.  You should split into two cases: $a = b$ and $a \prec b$. Finally, let $\lambda$ be a limit ordinal such that for all $b \prec \lambda$, $\phi(b)$; you must show that for all $a \prec \lambda$, $V_a \subset V_\lambda$.)
\end{proof}
\end{xbox}


\begin{theorem}
Every pure set is an element of $V_a$ for some ordinal $a$.  Thus $\mathcal{V} = \bigcup \{V_a \, | \, a \in \mathcal{O}\}$ is the collection of all pure sets in ZFC (often called the universe of pure sets).
\end{theorem}

The proof of this theorem is beyond the scope of this course.  Note that since the union ranges over a proper class rather than a set,  the Axiom of Union does not  show that $\mathcal{V}$ is a set in ZF.  

Intuitively, $V_a$ is the set of all pure sets eligible to be used as elements to form sets `at stage $a+1$'.  The definition below makes this precise.

\begin{defn}
A pure set $x$ has \emph{rank} $a$ iff $x \in V_{a+1} \backslash V_a$; that is, $x$ is a subset of $V_a$, but not an element of $V_a$. In other words, the elements  of $x$ exist `at stage $a$', but $x$ itself doesn't exist until `stage $a+1$'.
\end{defn}

\begin{notation}
In this case, we write $r(x)=a$.
\end{notation}

\begin{xbox}
\begin{example}
$r(\emptyset) = 0; \; r\big(\{ \emptyset \}\big) =1; \; r\Big(\big\{ \emptyset, \{ \emptyset\} \big\} \Big) = r\Big(\big\{  \{ \emptyset \} \big\}\Big) =2$; [give three pure sets of rank 3]
\end{example}
\end{xbox}

\begin{prop}
For every ordinal $a$, $r(a) = a$.
\end{prop}
\begin{proof}
We will use transfinite induction.  As shown in the example above, $r(0)=r(\emptyset) = 0$.  

Next, assume $r(a) = a$.  By definition, $a \in V_{a+1} \backslash V_a$; we must show  $a+1 = a \cup \{a\} \subset V_{a+1}$ but $a \cup \{a\} \not \in V_{a+1}$.  
By assumption, $a \in V_{a+1}$.  Since $V_{a+1}$ is a transitive set by Proposition 9.2(1), $a \subset V_{a+1}$.  Hence both $a$ and all of its elements are in $V_{a+1}$, and so $a \cup \{ a \} \subset V_{a+1}$.
  To show $a \cup \{a\} \not \in V_{a+1}$, note that $a \in a \cup \{a\}$, but $a \not \in V_a$.  Hence, $a \cup \{a\}$ cannot be a subset of $V_a$, which means $a \cup \{a\} \not \in \wp(V_a) = V_{a+1}$.

Finally, let $\lambda$ be a limit ordinal and assume that for all $a \prec \lambda$, $r(a) = a$.  We must show $r(\lambda)= \lambda$; that is, we must show $\lambda \subset V_\lambda$ but $\lambda \not \in V_\lambda$.  To show $\lambda \subset V_\lambda$, let $a \in \lambda$.  Then $a \prec \lambda$, and so by assumption, $r(a) = a$, which in particular means that $a \in V_{a+1}$.  Since $a+1 \prec \lambda$, $V_{a+1}$ is one of the sets in the union $ \bigcup \{ V_a \, | \, a \prec \lambda \}=V_\lambda$.  Hence $a \in V_\lambda$.  To show $\lambda \not \in V_\lambda$, assume by way of contradiction that $\lambda \in V_\lambda$.  Then there exists $a \prec \lambda$ such that $\lambda \in V_a$. Since $V_a$ is transitive by Proposition 9.1(1), $\lambda \subset V_a$.  Since $a \prec \lambda$, $a \in \lambda$ and so $a \in V_a$.  This is a contradiction.
\end{proof}

\subsection{Constructible Sets}

\begin{recall}
The Power Set Axiom asserts the existence of the set of all subsets of a given set, without specifying how these subsets are formed.  The Subset Axiom, by contrast, refers only to subsets of a known set defined as the extension of a formula with one free variable, $\phi(v)$.  We can define another cumulative hierarchy of sets in which we restrict subsets to only those whose existence is asserted by the Subset Axiom.
\end{recall}

\begin{defn}
For any ordinal $a$, we define $L_a$ inductively as follows:
\begin{enumerate}
\item $L_0 = \emptyset$;
\item for any ordinal $a$, $L_{a +1} =\text{ all sets of the form } \{ x \in L_a\, | \, \phi(x) \}$;
\item for any limit ordinal $\lambda$, $L_\lambda = \bigcup \{ L_a \, | \, a \prec \lambda \}$.
\end{enumerate}
\end{defn}

\begin{note}
 A formula $\phi(v)$ may involve one or more bound variables, in addition to its one free variable.  In the definition above, it is understood that at stage $a$,   the quantifiers range only over sets in $L_a$.
\end{note}

\begin{defn}
The \emph{constructible universe} of sets is $\mathcal{L} = \bigcup \{L_a \, | \, a \in \mathcal{O}\}$.  The members of this collection are called the \emph{constructible sets}.
\end{defn}

\framebox[\textwidth][c]{
\parbox{.9\textwidth}{
\textbf{Axiom of Constructibility.}  Every pure set is constructible; that is, $\mathcal{V} = \mathcal{L}$.
}
}

\begin{defn}
\emph{Constructible set theory} is the set theory obtained by adding the Axiom of Constructibility to the nine ZF axioms; it is denoted by  ZF + ($\mathcal{V} = \mathcal{L}$).
\end{defn}


In 1938, G\"{o}del proved that in ZF + ($\mathcal{V} = \mathcal{L}$), both the Axiom of Choice and the Continuum Hypothesis hold as theorems.  He also showed that if ZF is consistent, then so is ZF + ($\mathcal{V} = \mathcal{L}$).  This in turn implies that both the Axiom of Choice and the Continuum Hypothesis are consistent with ZF.  Initially, G\"{o}del believed that the Axiom of Constructibility should be added to ZF, but he later came to believe the axiom was `false'.

In 1964, Cohen proved that the negation of the Axiom of Choice is also consistent with ZF.  The Axiom of Choice therefore has the same status as the Continuum Hypothesis in that it is independent of ZF.  However, the Axiom of Choice and the Continuum Hypothesis are not equivalent to each other.


\end{document}