\documentclass{article}
\usepackage{amsmath,amstext,amsfonts,amsthm}
\usepackage{enumerate}
\input{fitch.sty}
\renewcommand\baselinestretch{0.95}
\topmargin -0.65in
\oddsidemargin -0.25in
\evensidemargin -0.25in
\textwidth 7.0in
\textheight 9.3in
%%% my math definitions
\def\lnot{\neg}
\def\land{\;\wedge\;}
\def\lor{\;\vee\;}
\def\lthen{\;\rightarrow\;}
\def\liff{\;\leftrightarrow\;}
\def\peq{\Leftrightarrow}
\def\cross{\;\times\;}
% some set theoretic definitions
\newcommand{\powerset}{\mathcal{P}}
\newcommand{\es}{\emptyset}
% Vn zermelo hierarchy of sets, V0 - V3
\newcommand{\VO}{\es}
\newcommand{\VI}{\{\VO\}}
\newcommand{\VII}{\{\VO, \VI\}}
\newcommand{\VIII}{\{\VO, \VI, \{\VI\}, \VII\}}
%%% my environments
\theoremstyle{definition}\newtheorem{exercise}{Exercise}[subsection]
\theoremstyle{remark}\newtheorem*{answer}{Answer}
\theoremstyle{plain}\newtheorem*{axiom}{}
%%% my numbering alterations
\numberwithin{equation}{subsection}
%%% professor's macros follow...
\def\spo{\hspace{1ex}}
\def\eqd{\mathord{\spo\spo=_{\mbox{\footnotesize\it def}}\spo\spo}}
\def\Mthen{\mathord{\spo\spo\Rightarrow\spo\spo}}
\def\Miff{\mathord{\spo\spo\Leftrightarrow\spo\spo}}
\def\A{\mathord{{\mathfrak A}}}
\def\sA{\mathord{^{\A}}}
\def\Cn{\mathord{\mbox{Cn}}}
\def\B{\mathord{{\mathfrak B}}}
\def\G{\mathord{{\cal G}}}
\def\N{\mathord{{\mathfrak N}}}
\def\M{\mathord{{\mathfrak N}}}
\def\Nat{\mathord{{\mathbb N}}}
\newcommand\R{{\mathbb R}}
\newcommand\Z{{\mathbb Z}}
\newcommand\Lang{{\cal L}}
\newcommand\E{\mbox{\em Exp}}
\newcommand\Mod{\mbox{\hspace{1pt}Mod\hspace{1pt}}}
\newcommand\Th{\mbox{\hspace{1pt}Th\hspace{1pt}}}
\newcommand\Con{\mbox{\hspace{1pt}Con\hspace{1pt}}}
\def\AS{\mathord{{\mathbb A}_S}}
\def\AL{\mathord{{\mathbb A}_L}}
\def\AE{\mathord{{\mathbb A}_E}}
\def\sN{\mathord{^{\N}}}
\def\sA{\mathord{^{\A}}}
\def\sB{\mathord{^{\B}}}
\def\NS{\mathord{\N_S}}
\def\NL{\mathord{\N_L}}
\def\NA{\mathord{\N_A}}
\def\NM{\mathord{\N_M}}
\def\NE{\mathord{\N_E}}
\newcommand\PAE{{\mathbb P}{\mathbb A}_E}
\def\St{\mathord{{\cal S}t}}
\def\un{\underline}
\def\a{\mathord{\vec{a}}}
\def\app{\mathord{a^{\prime\prime}}}
\def\b{\mathord{\vec{b}}}
\def\c{\mathord{\vec{c}}}
\def\n{\mathord{\vec{n}}}
\def\p{\mathord{\vec{p}}}
\def\q{\mathord{\vec{q}}}
\def\Th{\mathord{Th}}
\def\v{\mathord{\vec{v}}}
\def\w{\mathord{\vec{w}}}
\def\x{\mathord{\vec{x}}}
\def\y{\mathord{\vec{y}}}
\def\z{\mathord{\vec{z}}}
\def\tp{\mathord{t^\prime}}
\def\tpp{\mathord{t^{\prime\prime}}}
\def\sp{\mathord{s^\prime}}
\def\bp{\mathord{b^\prime}}
\def\<{\mathord{\langle}}
\def\>{\mathord{\rangle}}
\def\Prime{\mathord{\mbox{prime}}}
\def\lh{\mathord{\mbox{lh}}}
\def\tf{\mathord{\tilde{f}}}
\def\seqno{\mathord{\mbox{seq$\_$no}}}
\def\restrict{\mathord{|\hspace{-4pt}\stackrel{\backslash}{\hspace{2pt}}}}
\def\twotree{\mathord{\mbox{2-Tree}}}
\def\form{\mathord{\mbox{formula}}}
\def\sent{\mathord{\mbox{sentence}}}
\def\branch{\mathord{\mbox{branch}}}
\def\leaf{\mathord{\mbox{leaf}}}
\def\tail{\mathord{\mbox{tail}}}
\def\appendleaf{\mathord{\mbox{append@leaf}}}
\begin{document}
\centerline{\LARGE\bf Mathematical Logic III}
\centerline{\Large\bf The Joy of Sets}
\centerline{\Large\bf \S2.1 - \S2.4}
\centerline{\large\bf Ryan Flannery}
%%%
%%% chapter 2 - zermelo-fraenkel set theory
%%%
\setcounter{section}{1}
\section{The Zermelo-Fraenkel Axioms}
In chapter 2, Devlin introduces a formal language for set theory as well as a
set of axioms that will provide a framework for set theory in general. The
axioms, known as the Zermelo-Fraenkel axioms, are all intuitive in nature and
are arguably self-evident `truths' about sets. Since set theory provides a
sort of `foundation' for mathematics as a whole, it's certainly desirable to
have something so powerful rest on solid ground.
The language introduced is restrictive in that it only allows the construction
of mathematically oriented collections, but general enough to allow the
construction of {\em any} mathematically oriented collection.
%%%
%%% language of set theory
%%%
\subsection{The Language of Set Theory}
The language we use for set theory is precise in both its notation and grammar,
making it a formal language. We abbreviate this language with the name LAST
(the LAnguage of Set Theory.)
When referring to a specific set in LAST we shall always use the name $w$.
When referring to more than one specific set, we shall always use the name $w$
with integer subscripts (starting with 0) for our names
(i.e. $w_0,w_1,w_2,\ldots$)
Similarly, when referring to arbitrary sets or variables (remember:
{\em everything is a set!}) we shall always use the name $v$ with integer
subscripts (starting with 0) for our names (i.e. $v_0,v_1,v_2,\ldots$)
As for symbols, we inherit all of the standard logical symbols from first order
logic along with the membership symbol, $\in$. Thus, a complete lexicon for
LAST is:
\begin{center}
\begin{tabular}{|c|c||c|c|}
\hline
Symbol & Meaning & Symbol & Meaning \\
\hline
$w_0, w_1, \ldots$ & Named Sets & $v_0, v_1, \ldots$ & Variable Sets \\
\hline
$\in$ & Membership & $=$ & Equality \\
\hline
$\land$ & Conjunction & $\lor$ & Disjunction \\
\hline
$\lnot$ & Negation & $(\ ,\ )$ & Parentheses (for grouping) \\
\hline
$\forall$ & Universal Quantifier & $\exists$ & Existential Quantifier \\
\hline
\end{tabular}
\end{center}
As for the syntax of LAST, the following and {\em only the following}
represent valid formulas (be they clauses, phrases, or sentences):
\begin{enumerate}
\item Any expression of the following form is a valid formula
\[\begin{array}{cccc}
(v_n = v_m) & (v_n = w_m) & (w_m = v_n) & (w_n = w_m) \\
(v_n \in v_m) & (v_n \in w_m) & (w_m \in v_n) & (w_n \in w_m) \\
\end{array}\]
\item If $\phi$ and $\psi$ are valid formulas, so too are
\[\begin{array}{cc}
(\phi \land \psi) & (\phi \lor \psi) \\
\end{array}\]
\item If $\phi$ is a valid formula, so too is
\[\begin{array}{c}
(\neg \phi) \\
\end{array}\]
\item If $\phi$ is a valid formula, so too are
\[\begin{array}{cc}
(\forall v_n \phi) & (\exists v_n \phi)
\end{array}\]
\end{enumerate}
The above for methods are {\em the only} valid methods we allow for
constructing formulas in LAST.
Remember, any formula with no free variables is a {\em sentence}, and sentences
can be evaluated to true or false. Since formulas contain one or more free
variables, which are {\em arbitrary} sets, formulas can {\em not} be assigned a
definite truth value.
When dealing with formulas that have free variables, we often use the
abbreviation $\phi(v_0,\ldots,v_n)$ to indicate that $\phi$ is a formula that
has free variables in the list $(v_0,\ldots,v_n)$. With this, we can describe
{\em collections} of sets in LAST. For example, suppose we have a formula
$\phi(v_n)$ in LAST and we know what all of the specified sets in the formula
(those with names like $w_n$) refer to. Then, for any set $x$, we can
determine if $\phi(x)$ is true or false, and we can define a {\em collection}
as all of the sets that satisfy $\phi(v_n)$.
For our own ease, we also allow the following abbreviations in LAST:
\begin{center}
\begin{tabular}{|c|l|}
\hline
Abbreviation & Meaning \\
\hline
$(\phi \lthen \psi)$ & $((\neg\phi) \lor \psi)$ \\
\hline
$(\phi \liff \psi)$ & $((\phi \lthen \psi) \land (\psi \lthen \phi))$ \\
\hline
$x \subseteq y$ & $(\forall v_n ((v_n \in x) \lthen (v_n \in y)))$ \\
\hline
$x = \bigcup y$ & $(\forall v_n ((v_n \in x) \liff \exists v_m (
(v_n \in v_m) \land (v_m \in y))))$ \\
& $where\ n \not= m\ and\ v_n , v_m \not= x,y$ \\
\hline
$x=\{y\}$ & $(\forall v_n ((v_n \in x) \liff (v_n = y)))$ \\
& $where\ v_n \not= x,y$ \\
\hline
$x=\{y,z\}$ & $(\forall v_n ((v_n \in x) \liff ((v_n = y) \lor (v_n = z))))$ \\
& $where\ v_n \not= x,y,z$ \\
\hline
$x=(y,z)$ & $(\forall v_n ((v_n \in x) \liff ((v_n = \{y\}) \lor
(v_n = \{y,z\}))))$ \\
& $where\ v_n \not= x,y,z$ \\
\hline
$x=y \cup z$ & $x = \bigcup\{y,z\}$ \\
\hline
\end{tabular}
\end{center}
With these abbreviations, using LAST to express the concepts of set theory will
be a bit less cumbersome. However it is important to note that any concept
expressed using these abbreviations could just as easily be expressed without
the abbreviations by simply substituting the abbreviation with its meaning.
%%% - Exercise 2.1.1 goes here!
\begin{exercise}
Define the following.
\begin{enumerate}[(i)]
\item $x$ is an ordered pair
\begin{answer}
As given in the text\ldots
\begin{center}
$\exists v_n (\exists v_m (x = (v_n , v_m)))$
\end{center}
\end{answer}
\item $x$ is a function
\begin{answer}
From page 13 of the text, a function on a set is a relation (a set of
ordered pairs) such that for every $a$ in the domain, there is exactly
one $b$ in the range such that the ordered pair $(a,b)$ is in the
relation.
\begin{center}
$\forall a \exists b ( (a,b) \in x \lthen
\forall c ( (a,c) \in x \liff c = b))$
\end{center}
\end{answer}
\item $x = y \times z$
\begin{answer}
From page 10 of the text, the {\em cartesian product} of $x$ and $y$ is
defined as the set of all ordered pairs $(a,b)$ such that $a \in x$ and
$b \in y$.
\begin{center}
$\forall a \forall b ( (a,b) \in x \liff (a \in y \land b \in z))$
\end{center}
\end{answer}
\item $x$ is an n-ary function from $y$ to $z$
\begin{answer}
From page 13 of the text, an $n$-ary function $x$ on a set $y$ is
defined as an ($n$ + 1)-ary relation on $y$ such that for every $a$
in the domain of the relation there is exactly one $b$ in the range
such that $(a,b)$ is in the relation.
\begin{center}
$\forall_{a \in y_1 \cross \ldots \cross y_n} \exists_{b \in y}(
(a,b) \in x \lthen \forall_{c \in y}( (a,c) \in x \liff c = b))$
\end{center}
\end{answer}
\item $x$ is a poset
\begin{answer}
$x = (y,z)$ is a poset iff $z$ is a binary relation on $y$ that is
reflexive, antisymmetric, and transitive.
\[\begin{array}{rl}
\exists y \exists z ( (y,z) = x \land & (
(z = y \cross y) \\
& \land (\forall_{a\in y} ( (a,a) \in z)) \\
& \land (\forall_{a,b\in y} ( ((a,b) \in z \land a \not= b) \lthen (b,a) \not\in z)) \\
& \land (\forall_{a,b,c\in y} ( ((a,b) \in z \land (b,c) \in z) \lthen (a,c) \in z)) \\
& ) \\
\end{array}\]
\end{answer}
\item $x$ is a toset
\begin{answer}
$x$ is a toset iff $x$ is a connected poset. So, we can expand the
above definition of a poset with the following conjunction that
states the ordering is connected:
\begin{center}
$\land
(\forall_{a,b\in y} (a \not= b \lthen ((a,b) \in z \lor (b,a) \in z)))$
\end{center}
\end{answer}
\item $x$ is a woset
\begin{answer}
$x$ is a woset iff $x$ is a well-founded toset. So, we again expand
the above definition of a toset with the following conjunction that
states the ordering is well-founded:
\begin{center}
$\land
(\forall a((a \subseteq y \land a \not= \es)
\lthen \exists_{b \in a}\forall_{c\in a}(b \leq c))))$
\end{center}
\end{answer}
\item $x$ is an ordinal
\begin{answer}
$x$ is an ordinal iff $x = (y,z)$ is a woset such that $y_a = a$ for
all $a$ in $y$. We can further expand the definition of a woset with
the following conjunction:
\begin{center}
$\land (\forall z (z \in y_a \liff z \in a))$
\end{center}
which is equivalent to\ldots
\begin{center}
$\land (\forall z (z < a \liff z \in a))$
\end{center}
\end{answer}
\item $x$ and $y$ are isomorphic wosets
\begin{answer}
$x = (i,u)$ and $y = (b,v)$ are isomorphic wosets iff $x$ and $y$ are
wosets such that \ldots
\end{answer}
\item $x$ is a group
\item $x$ is an abelian group
\begin{answer}
{\em Omitted since it requires a working knowledge of group-theory.}
\end{answer}
\end{enumerate}
\end{exercise}
%%%
%%% cumulative hierarchy of sets
%%%
\subsection{The Cumulative Hierarchy of Sets}
Here, we develop further the idea of sets and, more specifically, a strict
method for {\em constructing} sets. To illustrate why a formal method of
constructing sets is important, let us start with a loose way of defining sets
and see what trouble it leads us into.
From the last section, we saw how we can define a {\em collection} of sets by
a formula in LAST. With this, it seems intuitive to define $x$ as a set if
and only if there is a formula $\phi(v_n)$ of LAST with just one free variable
$v_n$ where for every $a \in x$, $\phi(a)$. This intuitive way of defining
sets, however, leads to an inconsistent set theory! To explain, let $\phi$ be
the LAST formula
\begin{equation}
(\neg(v_0 \in v_0))
\end{equation}
So, if we follow our above definition, then $\phi$ defines a set $x$ such that
\begin{equation}
x = \{a | a \not\in a\}
\end{equation}
Since $x$ is a set, it is either the case that $x \in x$ or $x \not\in x$.
Let us consider both cases.
(1) If $x \in x$ then $x$ must satisfy $\phi$, that is, $x \not\in x$
{\em(a contradiction of our assumption!)}
(2) If $x \not\in x$ then $x$ must fail to satisfy $\phi$ which means that
$x \in x$ {\em(again, a contradiction of our assumption!)}
So, what was wrong with this method of defining sets? Simple: this method did
not regard what was available in {\em constructing} our set! That is, when we
were building the set $x$, we were presupposing that we already had $x$
constructed (a sort of circular definition of $x$.)
Clearly, we need a more strict method of constructing and defining sets, and
from the above argument we can begin to see the hierarchical nature of
constructing sets.
For example, suppose our base set of objects which we can construct sets from
are the numbers 0 and 1. From this, we could construct the sets $\emptyset$
(since the empty set is a subset of every set...a key point in a few minutes),
\{0\}, \{1\}, and the set \{0,1\}. That's it. Those are all the sets we can
construct. However, if we now extend our set of objects to include the sets
we just constructed (remember, we can have sets of sets), we can then
construct the following sets in addition to the previous sets: \{0,\{0\}\},
\{0,\{1\}\}, \{1,\{0\}\}, \{1,\{1\}\}, \{\{0\},\{1\}\}, \{\{0,1\}\}, and
indeed a few more. We could then consider all of {\em these} sets {\em in
addition} to the ones previously constructed to construct another level of
sets.
Formally, then, where do we begin with this hierarchy of sets? What is our
first `level' of sets? and for how long can we extend this hierarchy of sets?
As stated earlier, the empty set is a subset of every set.
\begin{proof}
Remember, we defined $x \subseteq y$ as $(\forall v_n ((v_n \in x) \lthen
(v_n \in y)))$. So, for any set $x$, $\emptyset \subseteq x$ iff\\
$(\forall v_n ((v_n \in \emptyset) \lthen (v_n \in x)))$. Since the
hypotheses $(v_n \in \emptyset)$ always fails, the statement is always true.
\end{proof}
With this, we start our hierarchy of sets with
\begin{equation}
V_0 = \emptyset
\end{equation}
where $V_0$ denotes the first level of the set theory hierarchy. To make this
hierarchy as powerful as possible, we place no restrictions on how many levels
we allow in this hierarchy. So, for each {\em ordinal number} $\alpha$, we
define $V_\alpha$ as the set of elements in $\bigcup_{\beta < \alpha}
V_\beta$.
Now, suppose we have $V_\alpha$ defined. What sets are in $V_{\alpha + 1}$?
Our intention is clear: $V_{\alpha + 1}$ should consist of all possible sets
definable in $V_\alpha$, but how do we accurately define this? For now, we
don't. As Devlin states, it will not be until Chapter 5 that we discuss the
{\em Axiom of Constructibility}, which will allow us to define what we need.
In the mean time, we accept without definition the notion of an
{\em unrestricted power set} operation. We shall simply assume that given any
set $x$, the power-set of $x$ (abbreviated $\powerset(x)$) simply exists, and
consists of all and only the subsets of $x$.
So, given our intention that $V_{\alpha + 1}$ should consist of all possible
sets definable in $V_\alpha$, we can `formally' define $V_{\alpha + 1}$ as
\begin{equation}
V_{\alpha + 1} = \powerset(V_\alpha)
\end{equation}
This tells us how, given $V_\alpha$, to construct $V_{\alpha + 1}$, and since
we defined $V_0$ to be $\emptyset$ we can easily construct $V_1, V_2, \ldots$
To summarize, we define the {\em cumulative hierarchy of sets} (a.k.a. the
{\em Zermelo hierarchy}) as
\[\begin{array}{lcl}
V_0 & = & \emptyset \\
V_{\alpha + 1} & = & \powerset(V_\alpha) \\
V_{\alpha} & = & \bigcup_{\beta < \alpha}V_\beta,
\text{if $\alpha$ is a limit ordinal} \\
\end{array}\]
\\
One last bit of theory covered in this section is the {\em Axiom of Subset
Selection}. This axiom states that for any given set, there may be numerous
subsets, but that every definable {\em collection} of subsets exists.
Remember, we can define a {\em collection} of sets in LAST by using a formula
with one free variable, written as $\phi(v_n)$. To remove any danger from
defining sets in this fashion (remember the contradiction we reached earlier)
we can limit ourselves
That is, let $x$ be any given set. The formula $\phi(v_n)$ applied to $x$
then defines a subset of $x$ in which every element $a$, $\phi(a)$ holds
true.\\
%%% exercise 2.2.1
\begin{exercise}
Show that if $y \in V_\alpha$ and $x \in y$, then $x \in V_\alpha$.
\end{exercise}
\begin{proof}
In the below proof, we can safely assume that $\alpha > 1$. Otherwise, the
statement would be vacuously true (simple proof).\\
Definition: Let $B = \{ \beta < \alpha : \exists_{x \in V_\beta}
\exists_{y \in x} (y \not\in V_\beta) \}$. Let $\beta_0$
be the minimum element of $B$.\\
Case 1: $\beta_0 = \emptyset$. If this is the case, then there are no
members of $\beta_0$ (it's empty) so proving transitivity is trivial.\\
Case 2: $\beta_0$ is a successor ordinal. That is, $\beta_0 = \gamma + 1$
for some $\gamma$. Pick $x \in V_{\gamma + 1} \land
x \not\subseteq V_{\gamma + 1}$ (from our
assumption, we know such an $x$ must exist.) Now, $x \subseteq V_\gamma$
since $V_{\gamma + 1} = \powerset{V_\gamma}$. Since
$x \not\subseteq V_{\gamma + 1}$ there is a $y \in x$ where
$y \not\in V_{\gamma + 1}$. Since $\gamma < \beta_0$ then $V_\gamma$ {\em
is} transitive! So, $x \subseteq V_\gamma$ and then $y \subseteq V_\gamma$.
Thus, $y \in \powerset{V_\gamma}$, $y \in V_{\gamma + 1}$ and
$y \in V_{\beta_0}$. $\bot$!\\
Case 3: $\beta_0$ is a limit ordinal. Pick $x \in V_{\beta_0} \land
x \not\subseteq V_{\beta_0}$.
Then for some $\gamma < \beta_0$ we know $x \in V_\gamma$. Since $\gamma
< \beta_0$, $V_\gamma$ is transitive! Since $x \in V_\gamma$ then
$x \subseteq V_\gamma$. Then $x \subseteq (V_\gamma \cup *)$, so
$x \subseteq V_{\beta_0}$! $\bot$\\
Thus, the $V_\alpha$ hierarchy is transitive.
\end{proof}
%%% exercise 2.2.2
\begin{exercise}
Show that, for any ordinal $\alpha$, $V_\alpha = \bigcup_{\beta < \alpha}
\powerset(V_\beta)$.
\end{exercise}
\begin{proof} Omitted. \end{proof}
%%% exercise 2.2.3
\begin{exercise}
Show that, if $\alpha < \beta$, then $V_\alpha \subset V_\beta$.
\end{exercise}
\begin{proof}
First, let's use the lemma that Professor Schlipf provided us in class.
\begin{center}
\begin{fitch}
\fh \alpha < \beta & Premise \\
\fa V_\beta \bigcup_{\gamma < \beta} \powerset(V_\gamma) &
From exercise 2.2 \\
\fa \powerset(V_\alpha) \subseteq V_\beta & since $\alpha < \beta$
and above line \\
\fa V_\alpha \in \powerset(V_\gamma) & since $V_\alpha \subseteq V_\alpha$ \\
\fa V_\alpha \in V_\beta & since $\in$ from above two lines \\
\end{fitch}
\end{center}
So, with this lemma, we know that if $\alpha < \beta$ that $V_\alpha \in
V_\beta$. With this lemma, our proof becomes trivial. Note that $V_\alpha
\subset V_\beta$ is the same as $V_\alpha \subseteq V_\beta \land V_\alpha
\not= V_\beta$.
\begin{center}
\begin{fitch}
\fh \alpha < \beta & Premise \\
\fa V_\alpha \in V_\beta & From the above lemma \\
\fa V_\alpha \subseteq V_\beta & From exercise 2.1 \\
\fa \fh V_\alpha = V_\beta & Premise \\
\fa \fa V_\alpha \in V_\alpha & simple substitution with line 2 \\
\fa \fa \bot & since $x \not\in x$! \\
\fa V_\alpha \not= V_\beta & $\bot$-elimination \\
\fa V_\alpha \subseteq V_\beta \land V_\alpha \not= V_\beta &
$\land$-introduction \\
\fa V_\alpha \subset V_\beta & \\
\end{fitch}
\end{center}
\end{proof}
%%% exercise 2.2.4
\begin{exercise}
Check the following:
\begin{enumerate}[(i)]
\item $V_0 = \VO$
\begin{answer} Trivial\ldots $V_0$ is defined to be $\VO$ \end{answer}
\item $V_1 = \VI$
\begin{answer}
By definition, $V_1$ is defined to be $\powerset(V_0)$. The
$\powerset(V_0)$ is the set containing all subsets of $V_0$. The
{\em only} subset of $V_0$ is, indeed, the set ${\es}$. So, for
$V_1$, the only set we can `construct' is the set containing $\es$.
\end{answer}
\item $V_2 = \VII$
\begin{answer}
Using a similar argument from part (i), we see immediately that
all elements in the sets $V_0$ and $V_1$ are in $V_2$.
\end{answer}
\item $V_3 = \VIII$
\begin{answer}
Similar to the last two levels, we see we have the union of all
sets from the previous levels of the hierarchy. Also, we see the
addition of the set ${{\es}}$, which does not appear in any of the
previous levels. It appears because the set ${\es}$ was in a
previous level ($V_2$), and the {\em subset} containing only this
set is ${{\es}}$.
\end{answer}
\end{enumerate}
\end{exercise}
%%% exercise 2.2.5
\begin{exercise} What are $V_4$ and $V_5$? \end{exercise}
\begin{answer}
\[\begin{array}{rrl}
V_4 & = \{ & \VO,\ \VI,\ \{\VI\},\ \{\{\VI\}\},\ \VII,\ \VIII, \\
& & \{\VO,\{\VI\}\},\ \{\VO,\VII\},\ \{\VI,\{\VI\}\},\
\{\VI,\VII\},\ \{\{\VI\},\VII\}, \\
& & \{\VO,\VI,\{\VI\}\},\ \{\VO,\VI,\VII\},\ \{\VO,\{\VI\},\VII\},
\ \{\VI,\{\VI\},\VII\} \\
& \} & \\
\end{array}\]
{\em whew!}\\
Notice how the first line has all 1-element subsets of
$\powerset(V_3)$, the second line has all 2-element subsets of
$\powerset(V_3)$, and the last line has all 3-element subsets of
$\powerset(V_3)$.\\
As for $V_5$, I leave its construction to anyone who wishes to write all
65,536 elements ({\em without} the use of a computer!)
\end{answer}
%%% exercise 2.2.6
\begin{exercise}
How many elements has $V_n$, where $n$ is a positive integer?
\end{exercise}
\begin{answer}
Before we provide a general answer, notice the trend so far\dots
\begin{center}\begin{tabular}{|c|c|}
\hline
Set & Number of Elements \\
\hline
$V_0$ & 0 \\
\hline
$V_1$ & 1 \\
\hline
$V_2$ & 2 \\
\hline
$V_3$ & 4 \\
\hline
$V_4$ & 16 \\
\hline
\end{tabular}\end{center}
Just by looking at this trend, we immediately see that the number of
elements for each of the sets (except $V_0$) are perfect powers of two. As
it turns out, for a set $v_n$ of size $x$, the $\powerset(v_n)$ has
precisely $2^x$ elements. We adopt the syntax $|x|$ to denote the number of
elements in a set $x$.
With that, we can generalize the trend as follows:
\begin{center}\begin{tabular}{|c|c|}
\hline
Set & Number of Elements \\
\hline
$V_0$ & 0 \\
\hline
$V_{n + 1}$ & $2^{|V_n|}$ \\
\hline
\end{tabular}\end{center}
\end{answer}
%%%
%%% zermelo-fraenkel axioms
%%%
\subsection{The Zermelo-Fraenkel Axioms}
Until now, we have made certain {\em assumptions} regarding sets and we are
not ready to remove these assumptions by constructing an axiom base for set
theory. We want to include in our axioms {\em only} what we needed to
construct the $V_\alpha$-hierarchy of sets discussed in the last section.
The first bit of information we required in constructing the $V_\alpha$-
hierarchy was the ordinal numbering system. So, we take the ordinal numbering
system as basic; that is, we just accept the existence of ordinal numbers
without proof.
Next, we look at power-set operation, which is what we used to construct the
consecutive levels of the $V_\alpha$-hierarchy. We create the {\em Power Set
Axiom}:
\begin{axiom}
Power Set Axiom. If $x$ is a set, there is a set that consists of all and
only the subsets of $x$.
\end{axiom}
%%% exercise 2.3.1
\begin{exercise}
Write down a LAST sentence which expresses the power set axiom.
\end{exercise}
\begin{answer}
For every set $x$, we can define the $\powerset(x)$ as follows:
\begin{equation}
\forall x \exists y \forall z (z \subseteq x \liff z \in y)
\end{equation}
\end{answer}
The power set axiom does not yet allow us to construct the entire $V_\alpha$-
hierarchy. What if $\alpha$ is a limit ordinal? In that case, our definition
of $V_{\alpha + 1}$ required the {\em union} of a collection of sets. So, we
create the {\em Axiom of Union}:
\begin{axiom}
Axiom of Union. If $x$ is a set, there is a set whose members are precisely
the members of the members of $x$, i.e. the set $\bigcup x$.
\end{axiom}
%%% exercise 2.3.2
\begin{exercise} Express the axiom of union in LAST. \end{exercise}
\begin{answer}
We can express y as the $\bigcup x$ as follows:
\begin{equation}
\forall x \exists y \forall z (z \in x \liff
\forall a(a \in z \liff a \in y))
\end{equation}
\end{answer}
The next axiom is stressed as the most important, but least appreciated. It
allows us to construct a set $x$, from another set $y$, by replacing every
element $a$ in $x$ with a new set $a'$. We allow any replacement that is
definable by a LAST formula.
\begin{axiom}
Axiom of Replacement. Let $\phi(v_n,v_m)$ be any formula of LAST such that
for each set $a$ there is a unique set $b$ such that $\phi(a,b)$. Let $x$
be a set. Then there is a set $y$ consisting of just those $b$ such that
$\phi(a,b)$ for some $a$ in $x$.
\end{axiom}
%%% exercise 2.3.3
\begin{exercise}
In LAST, we do not have the ability to work with whole formulas of LAST,
so there is no way to translate the Axiom of Replacement into a LAST
formula. Instead, however, we can construct a formula schema. Given any
formula $\phi(v_n,v_m)$ of LAST write down a sentence of LAST that
expresses the Axiom of Replacement.
\end{exercise}
\begin{answer}
\begin{equation}
\forall d \exists r \forall y (y \in r \liff
\exists x ( \phi(x,y) \land x \in d))
\end{equation}
\end{answer}
The next two axioms are the last two we need to construct the cumulative
hierarchy of sets. The first axiom simply asserts the existence of the empty
set. The second axiom is used for the construction of ordinals.
Other axioms, such as the Powerset axiom, require the existence of sets.
These next two axioms (combined with the others) allow us to actually
{\em construct} sets.
\begin{axiom}
Null Set Axiom. There is a set which has no members (denoted by $\es$.)
\end{axiom}
\begin{axiom}
Axiom of Infinity. There is a set $x$ such that $\es \in x$, and such that
$\{a\} \in x$ whenever $a \in x$.
\end{axiom}
The Axiom of Infinity guarantees the existence of {\em at least one} set.
We could, then, use the Axiom of Infinity along with the Axiom of Subset
Selection, to prove the existence of the Null set, thus removing the need for
the Null Set Axiom.
For example, given some set $a$, we could express the Null set as:
\begin{equation}
\es = \{x \in a | x \not= x\}
\end{equation}
%%% exercise 2.3.4
\begin{exercise}
Express the {\em Null Set Axiom} and the {\em Axiom of Infinity} in LAST.
\end{exercise}
\begin{answer}
For the {\em Null Set Axiom}, we can express $\es$ as the set $y$ such that
$y$ has no elements:
\begin{equation}
\exists y \forall x (\neg(x \in y))
\end{equation}
For the {\em Axiom of Infinity}, we define $x$ as
\begin{equation}
\exists x (\es \in x \land \forall a (a \in x \liff \{a\} \in x))
\end{equation}
\end{answer}
The next axiom is so fundamental that we accepted it in \S1.1. It is the
Axiom of Extensionality, and it allows to talk about two sets being ``equal''.
As we did in \S1.1, we define two sets to be equal when their elements are
identical.
\begin{axiom}
Axiom of Extensionality. If two sets have identical elements, then they
are equal.
\end{axiom}
%%% exercise 2.3.5
\begin{exercise}
Express the {\em Axiom of Extensionality} in LAST.
\end{exercise}
\begin{answer}
Two sets, $x$ and $y$, are defined to be equal if and only if:
\begin{equation}
\forall z(z \in x \liff z \in y)
\end{equation}
\end{answer}
Using the axioms we have defined thus far, all that is needed to construct the
cumulative hierarchy of sets is the fact that the membership operator ($\in$)
be well-founded. So, we create the following axiom:
\begin{axiom}
Axiom of Foundation. $\in$ is a well-founded relation. That is, for every
nonempty set $x$, there is a set $a \in x$ such that $a \cap x = \es$.
\end{axiom}
It should be noted that the Axiom of Foundation is also referred to as the
Axiom of Regularity.
%%% exercise 2.3.6
\begin{exercise}
Prove that the relation $\in$ is well-founded if and only if for every
nonempty set $x$, there is a set $a \in x$ such that $a \cap x = \es$.
\end{exercise}
\begin{answer}
Is $\in$ a well-founded relation? Remember from page 11 of our text that
a poset is said to be well-founded if every nonempty subset has a minimal
element. So, this is equivalent to asking if for every set $x$, is
$(x,\in)$ a well-founded poset? Look at the definition we provided earlier
of a poset in exercise 2.1.1 (part v). If we use $\in$ as our relation,
it becomes immediately apparent that $\in$ is {\em indeed} well-founded.
{\em NOTE: We are actually defining a weak-poset, that is, one that is
anti-reflexive. Remember that reflexivity is required for a normal poset,
and $\in$ is clearly not reflexive, so it could not be a normal poset.}
\end{answer}
\begin{exercise}
Assume axioms 1-7 (listed below) and prove that the Axiom of Foundation is
equivalent to the equality:
\begin{equation} V = \bigcup_{\alpha} V_\alpha \end{equation}
\end{exercise}
\begin{answer} Omitted. \end{answer}
In finishing, the Zermelo-Fraenkel axioms are:
\begin{enumerate}
\item Axiom of Extensionality.
\item Null Set Axiom.
\item Axiom of Infinity.
\item Power Set Axiom.
\item Axiom of Union.
\item Axiom of Replacement.
\item Axiom of Subset Selection.
\item Axiom of Foundation.
\item Axiom of Choice (discussed in \S2.7.)
\end{enumerate}
{\em NOTE: The theory consisting of Axioms 1-8 is called ZF set theory. If we
add Axiom 9, the resulting theory is called ZFC set theory.}
%%%
%%% classes
%%%
\subsection{Classes}
{\em It should be noted the objections Devlin has with class theory. First,
class theory looses the `intuition' present in ZF set theory. Second, class
theory is not needed. It can be proven formally that any result about sets
provable in class theory is already provable in ZF set theory. As such,
Devlin spends only a small amount of time introducing the basics of class
theory.}
We now have a good understanding of what we allow to be a set and what we do
not. We allow the ordinals and anything in the $V_\alpha$ hierarchy to exist
as sets, but nothing else. We have, however, used the term ``collection''
often, and as we have seen, collection can be determined by formulas of LAST
(but not all collections can!)
So, we now extend our axiom system to handle `collections', thus leaving the
bounds of {\em set theory} and entering {\em class theory}.
The basics of class theory are as follows:
\begin{enumerate}
\item All sets are classes.
\item Classes that are not sets are {\em proper classes}.
\end{enumerate}
How can we have classes that are not sets? Some basic examples are the
collection of all ordinals and $V$. Since these are not sets, we must not
handle them in any way that we would a class. Even the basic idea that we
constructed ZF set theory on is useless\ldots it is meaningless for one
collection to be a member of another collection.
Classes do, however, exhibit properties similar to sets. For example,
consider the following classes:
\begin{center}
$A = \{\,x\,|\,\phi(x)\}$\\
$B = \{\,x\,|\,\psi(x)\}$
\end{center}
In this case, we can express simple notions such as
\begin{center} $A \subseteq B$ \end{center}
with
\begin{center} $\forall x(\phi(x) \lthen \psi(x))$ \end{center}
%%% exercise 2.4.1
\begin{exercise}
Let $A = \{x\,|\,\phi(x)\}$ and $B = \{x\,|\,\psi(x)\}$. Let $C$ be the
class $A \cup B$. Express the assertion $x \in C$ as a sentence in set
theory.
\end{exercise}
\begin{answer}
\begin{equation} \phi(x) \lor \psi(x) \end{equation}
\end{answer}
%%% exercise 2.4.2
\begin{exercise}
Express the assertion $C = A \cap B$ as a sentence in set theory.
\end{exercise}
\begin{answer}
\begin{equation} \phi(x) \land \psi(x) \end{equation}
\end{answer}
So, what {\em is} the benefit of studying classes? Simple: they help make
some of the more complicated notions of set theory simpler.
Look at the Axiom of Replacement, given last section. In class theory, the
same notion can be replaced with the following:\\
Define the class $F$ as follows:
\begin{equation} F = \{ (a,b) | \phi(a,b) \} \end{equation}
Notice that the class $F$ looks just like a function in sets. Now, for any
set $x$, the class:
\begin{equation} \{\,F(a)\,|\,a \in x\} \end{equation}
is a set. And that is the Axiom of Replacement in class theory.\\
To summarize class theory:
\begin{enumerate}
\item Classes are just abbreviations for defining sets using formulas of
LAST.
\item Proper classes are `big collections' that are {\em not} sets.
\item Proper classes can be handled similar to sets, except that they are
not a completed whole.
\item All sets are classes, but not all classes are sets.
\end{enumerate}
%%% exercise 2.4.3
\begin{exercise}
Let $On$ be the class of all ordinals. Prove that $On$ is a proper class.
\end{exercise}
\begin{answer}
The proof follows the outline given in the book. We show that if $On$ is
the {\em set} of all ordinals, then it too is an ordinal. With that, we
would have $On \in On$ which violates the axiom of foundation (how?).
\begin{proof}
Suppose not. That is, suppose $On$ is not a proper class and is indeed
a set. On page 18 of our text, we define $x$ to be an ordinal iff $x$
is well-ordered and $X_a = a$ for all $a \in X$. We want to show that
$On$ is an ordinal. To do this, we have to prove that $On$ is reflexive,
antisymmetric, transitive, connected, and well-founded. We omit the
proofs of all of these except well-foundedness since they are trivial
(they are simple applications of their definitions which we provided
in exercise 2.1.1.) So, let us prove that $On$ is well-founded\ldots\\
Let $z \subseteq On$ and $z \not= \emptyset$. Assume $z$ does {\em not}
have a minimum element, that is, there is no $a \in z$ such that
$\forall_{b \in z} (a \not< z)$. Pick some $a \in z$. We know $a$ is
an ordinal.\\
Case 1: $a \cap z$ is empty. Then $a$ is less than all elements of $z$!
That is, $a$ is the minimum element of $z$, which contradicts our
assumption about $z$.\\
Case 2: $a \cap z$ is not empty. Then $a \cap z$ is the set of all
ordinals in $z$ that are $< a$. So, $a \cap z$ has a minimum element.
Let $b$ be the minimum element. Now we prove that $b$ is the minimum
element of $z$. Pick some other element $c \in z$.\\
Case 2.1: $c \in a$. Then, $b < c$ by our choice of $b$.\\
Case 2.2: $c \not\in a$. Then $c \ge a$ since $b \subseteq c$. So,
$b < c$.\\
{\em So, $z$ does have a minimum element!}
And $On$ is well-founded. Well-foundedness together with the other
properties listed above imply that $On$ is itself an ordinal. Thus,
$On \in On$, which is a contradiction.\\
Thus, $On$ {\em is} a proper class.
\end{proof}
\end{answer}
\end{document}