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

\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}{6}
\section{Axiomatic Set Theory}

\subsection{Introduction to Axiomatic Set Theory}
\hfill


Prompted by the appearance of the set paradoxes, mathematicians sought to put set theory on a more solid foundation by axiomatizing it, as geometry had been axiomatized by Euclid.  This involves boiling down the entire body of knowledge to the fewest possible:
\begin{itemize}
\item undefined expressions, called \emph{primitive terms}; 
\item unproved statements about these terms, called \emph{axioms}.
\end{itemize} 
All non-primitive terms are defined in terms of the primitive ones; all other statements, called \emph{theorems}, must be derived from the axioms.  To state new definitions and deduce new theorems, we use the language of \emph{formal logic}; like the primitive terms and axioms, the expressions and laws of logic are simply accepted without explanation or proof of validity.

The primitive terms of set theory are:
\begin{itemize}
\item \textbf{sets}, represented symbolically by $a, b, x, y, \dots$ etc.; these symbols can either be \emph{variables}, referring to arbitrary sets, or \emph{names}, referring to specific sets;
\item the \textbf{membership relation} between two sets, represented symbolically by  $\in$; although not formally defined, `$a \in b$'  is intended to mean  `$a$ is an element of $b$'  or  `$a$ belongs to $b$'.
\end{itemize}

\begin{note}
The \textbf{only} objects of our study are sets; every element of a set is itself a set.  For this reason, we no longer distinguish between sets and elements by using uppercase and lowercase letters.\end{note}

We import from formal logic the usual symbols: 	
\begin{itemize}
\item the logical connectives: $\lnot$ (`not'),  $\land$ (`and'), $\lor$ (`or'), $\implies$ (`implies'), $\iff$ (`if and only if');
\item the logical quantifiers: $\exists$ (`there exists'), $\forall$ (`for all').
\end{itemize}

\begin{defn}
A \emph{well-formed formula} (or formula, for short) in set theory is a `grammatical' arrangement of finitely many of these symbols.  It can be built up \textbf{only} in the following ways:
\begin{enumerate}
\item  any expression of the form $a \in b$ is a 
formula;
\item if $\phi, \, \psi$ are formulas, then so are $\lnot \phi, \, \phi \land \psi, \, \phi \lor \psi, \, \phi \Rightarrow \psi, \, \phi \iff \psi$;
\item if $\phi$ is a formula involving the variable $v$, then $\exists v ( \phi)$ and $\forall v ( \phi)$ are also formulas.
\end{enumerate}
\end{defn}

\begin{note}
Round and square parentheses of various sizes are often used for clarification. 
\end{note}

\begin{defn}
A variable $v$ occurring in a formula $\phi$ is \emph{bound} iff it is quantified by either $\exists v$ or $\forall v$ appearing somewhere in the formula $\phi$; otherwise, $v$ is a \emph{free} variable.
\end{defn}

\begin{xbox}
\begin{example}
$\forall x \, \forall y \, \Big[ (x \in y) \lor \lnot (x \in y)\Big]; \: \exists x \,  \Big[ \lnot (x \in a ) \Big]$ (Explain why each of these strings satisfies the definition of a formula. Which are the bound variables and which are the free variables in each formula?)
\end{example}
\end{xbox}

\begin{notation}
The notation $\phi (v)$ indicates that  $v$ is a free variable in formula $\phi$; $\phi$ may or may not have other free variables.  A formula may also involve one or more names of specific sets; note that names cannot be quantified in a formula. The notation $\phi_a(v)$ indicates that $a$ is a name and $v$ is a free variable in formula $\phi$.
\end{notation}

\begin{defn}
A \emph{statement} is a formula with no free variables.
\end{defn}

\begin{xbox}
\begin{example}
(Which formula(s) in the previous example is/are statements?)
\end{example}
\end{xbox}

%\begin{note}
A statement can be read as an assertion about sets which is either `true' or `false'.  The axioms of the system are the fundamental `true' statements about sets; since the process of logical deduction is assumed to be `truth-preserving', any theorems derived from the axioms will also be `true' statements about sets.
%\end{note}

A  formula with one free variable defines a set property or \emph{predicate}; a formula with two free variables defines a relationship between sets.

\begin{example}
The formula $\eta(v) : = \exists x\,  \big[ x \in v \big]$ asserts that $v$ has the property of being nonempty;  the formula $\sigma(v, w) := \forall x \, \big[ x \in v \Rightarrow x \in w \big]$ asserts that  $v$ is a subset of $w$, and can be taken as the definition of the notation ``$v \subseteq w$".  
\end{example}

When specific set names are substituted in for the free variables, we get an assertion \textbf{about those specific sets} which is either `true' or `false'.  In the example above, $\sigma(a, b)$ is `true' if and only if the specific set $a$ is in fact a subset of the specific set  $b$.

\begin{defn}
The \emph{extension} of a formula with one free variable, $\phi(v)$, is the collection of all sets $x$  for which $\phi(x)$  is `true', denoted by $\{ x \mid\phi(x) \}$.
\end{defn}

\textbf{Attempted Definition.}  A \emph{set}  is the extension of a formula with one free variable.  Thus, for any set $a$, there is a formula $\phi$ with one free variable such that $a =\{ x \mid \phi(x) \}$;  symbolically,  $\forall x \big[ x \in a \iff \phi(x) \big]$.  
%Sets can therefore be  identified with predicates.

\begin{xbox}
\begin{example}
 (Express $\mathcal{Z}$, the set of all sets that are not elements of themselves, as the extension of a formula with one free variable. Why does this doom this attempted definition?)
\end{example}
\end{xbox}


\subsection{The Zermelo-Fraenkel Axioms}

\hfill

We wish to rework the definition of a set to exclude collections which lead to the set paradoxes. The Zermelo-Fraenkel axioms (first proposed by Ernest Zermelo in 1908, refined by Abraham Fraenkel and Thoralf Skolem in 1922) are designed to limit which collections are to be considered `sets'.  The set theory determined by following nine axioms is denoted ZF.  The Axiom of Choice is usually thrown in as a tenth axiom, and the resulting system is denoted ZFC. 

\begin{enumerate}
\item \textbf{Axiom of Extensionality.}  If two sets have the same elements, then they are identical. (This can be taken as the definition of the notation ``$a = b$".)
\begin{itemize}
\item $\forall a \, \forall b \, \forall x \, \Big[ ( x \in a \iff x \in b) \implies a = b \Big]$
\end{itemize}

\item \textbf{Null Set Axiom.}  There exists a set with no elements (denoted by $\emptyset$).
\begin{itemize}
\item
\begin{xbox} \end{xbox}
\end{itemize}


\item \textbf{Pair Set Axiom.}  If  $a$ and  $b$  are sets, then there exists a set  $\{a, b\}$  whose only elements are  $a$  and  $b$.  (If  $a = b$,  this means there exists a set  $\{a\}$.)
\begin{itemize}
\item $\forall a \, \forall b \, \exists z \,  \forall w \, \Big[ w \in z \iff (w = a \lor w = b ) \Big]$
\end{itemize}

\item \textbf{Axiom of Union.}  If $a$ is a set, then there exists a set $\bigcup a$ whose elements are all elements of elements of $a$.
\begin{itemize}
\item $\forall a \, \exists y \, \forall z\,  \Big[ z \in y \iff \exists w \, (w \in a \land z \in w) \Big]$
\end{itemize}

\item \textbf{Axiom of Infinity.}  There exists a set $x$ such that $\emptyset \in x$ and if $a \in x$, then $a \cup \{ a \} \in x$.
\begin{itemize}
\item $\exists x \, \bigg[ (\emptyset \in x) \land \forall a \, \Big( a \in x \implies \exists y \, \big[ y \in x 
\land \forall z ( z \in y \iff z = a \lor z \in a) \big] \Big) \bigg]$
\end{itemize}

\item \textbf{Axiom of Foundation.}  If $x$ is a nonempty set, then there exists a set $a$ such that $a \in x$ and $a \cap x = \emptyset$.
\begin{itemize}
\item 
\begin{xbox} \end{xbox}
\end{itemize}

\item \textbf{Subset Axiom.}  If $a$ is a set and $\phi(v)$ is a formula with one free variable, then there exists a set $x$ whose elements are the elements $z$ of  $ a$ for which $\phi(z)$ is true.
\begin{itemize}
\item 
\begin{xbox} \end{xbox}
\end{itemize}

\item \textbf{Axiom of Replacement.}  Let $\phi(v, w)$ be a formula with exactly two free variables such that for every set $v$ there exists a unique set $w$ for which $\phi(v, w)$ is true.  If $x$ is a set, then there is a set $y$ whose elements are all sets $b$ such that $\phi(a, b)$ is true for some $a \in x$.
\begin{itemize}
\item $\forall x \, \bigg[ \forall v \, \exists w \, \Big( \phi(v, w) \land \forall z \, \big( \phi(v, z) \implies w = z\big) \Big) \implies \exists y \, \forall b\Big( b \in y \iff \exists a \big[ a \in x \land \phi(a, b) \big] \Big) \bigg]$
\end{itemize}

\item \textbf{Power Set Axiom.}  If $a$ is a set, then there exists a set $\wp (a)$ whose elements are all subsets of $a$.
\begin{itemize}
\item 
\begin{xbox}  \end{xbox}
\end{itemize}
\end{enumerate}


\textbf{Commentary on the ZF axioms} 

\begin{enumerate}

\item The Axiom of Extensionality states that a set is wholly determined by its elements, not by the manner in which it is defined. 
\begin{example}
$\{-1, 0, 1 \} = \{\sin(n \pi / 2) \, | \, n \in \mathbb{N} \}$
\end{example}

\item The Null Set Axiom is the only axiom that asserts the existence of a wholly determined set. 

\item The Pair Set Axiom is the first step in creating new sets.  Once the existence of $\emptyset$   is asserted, we can use this axiom to construct the set $\{ \emptyset\}$.  Once we have both   $\emptyset$  and $\{ \emptyset\}$, we can construct $\big\{ \{ \emptyset\}\big \}$    and$\big\{ \emptyset, \{ \emptyset\} \big\}$,  etc.  Note that each application of this axiom results in a set with only one or two elements.

\item The Axiom of Union  can be used to create sets containing any finite number of elements.
\begin{example} 
$\bigcup \bigg\{ \Big\{ \emptyset, \{\emptyset \} \Big\}, \Big\{ \big\{ \{ \emptyset \} \big\} \Big\} \bigg\} = \bigg\{ \emptyset, \{ \emptyset \}, \Big\{ \{ \emptyset \} \Big\} \bigg\}$ is a set containing three elements.
 \end{example}
 
 \item  The Axiom of Infinity asserts the existence of an infinite set, for once we know $\emptyset = a_0 \in x$, 
 then we know $a_0 \cup \{ a_0 \} =\emptyset \cup \{ \emptyset \} = \{ \emptyset \} \in x$.  If  $a_1 =  \{ \emptyset \}$, then  $a_1 \cup \{ a_1\} = \{ \emptyset \} \cup  \Big\{ \{ \emptyset \} \Big\} = \Big\{ \emptyset, \{ \emptyset \} \Big\} \in x$.  Setting $a_2 = \Big\{ \emptyset, \{ \emptyset \} \Big\} $, we get 
 \[
 a_2 \cup \{ a_2\}  = \Big\{ \emptyset, \{ \emptyset \} \Big\} \cup \bigg\{ \Big\{ \emptyset, \{ \emptyset \} \Big\} \bigg\} = \bigg\{ \emptyset, \{ \emptyset \}, \Big\{ \emptyset, \{ \emptyset\} \Big\} \bigg\} =a_3 \in x.
 \]
Continuing in this manner, we get a sequence $a_0, a_1, a_2, \dots$ of elements of $x$ that can be put into one-to-one correspondence with $\mathbb{N}$.  Thus $x$ contains a denumerable subset and is therefore infinite. We don't know what other elements $x$ might have.
 
 \item The Axiom of Foundation asserts that in any nonempty set  $x$, there is an element which is minimal with respect to the membership relation.  That is,  $x$  cannot contain elements $x_1, x_2, x_3, \dots$    satisfying  $\dots x_3 \in x_2 \in x_1 \in x$, for then the subset $y = \{x_1, x_2, x_3, \dots  \}$ violates this axiom. This axiom also rules out the possibility of a set belonging to itself.  For suppose $a \in a$.  Then $x=\{ a \}$   is a set (by the Pair Set Axiom) whose only element is $a$.  Since $a \in a \cap x$, $a \cap x  \neq \emptyset$ and this  violates the Axiom of Foundation.
 
  \begin{xbox}
 This prevents both Cantor's Paradox and Russell's Paradox from occurring in ZF.
 \end{xbox}
 \begin{xbox}
 In addition, this axiom shows that it can never be the case that both  $x \in y$   and  $y \in x$.  More generally, \\
 there can never  be any finite `cycles' of the form $x \in y_1 \in y_2 \in \dots \in y_n \in x$.
 \end{xbox}
 
 \item The Subset Axiom places a restriction on the notion that the extension of any formula with one free variable, $\phi(v)$,  defines a set.  This method can only define subsets of `pre-existing' sets; that is, we can only construct sets of the form  $\big\{ x \in a \, | \, \phi(x) \big\}$  where  $a$  is \emph{already known to be a set}.  This axiom is included to prevent the remaining set paradoxes from occurring in ZF.  For example, with enough patience, the definition of a well-ordered set can be translated into a formula with one free variable $\varpi(v)$, yet we cannot form the set of all well-ordered sets.
 
\begin{note} In the symbolic notation for the Subset Axiom, there is no universal quantifier $\forall$ in front of the formula $\phi$. That is because  the definition of a formula specifies that we can only put logical quantifiers in front of variables that appear within formulas; that is, we can `quantify over' sets, but not over formulas.  Technically, we have a Subset Axiom for every possible (finite) formula $\phi$ with one free variable; the Subset Axiom is in fact what is called an \textbf{axiom schema}.
\end{note}

\begin{note}
The Subset Axiom is also sometimes called the \textbf{Axiom (Schema) of Separation}.
\end{note}
 
 \item The Axiom of Replacement means that if we replace each set-element in a set with another set,  in a well-defined way, then the resulting collection will still be a set.  Another way of thinking of this is that if we apply a function to every element of a set -- its domain -- then  the resulting collection of elements -- its range -- will also be a set. 
 
 \begin{note}
 The Axiom of Replacement is also an axiom schema, with one axiom for each formula in two free variables.
 \end{note}
 
 \item The Power Set Axiom asserts the existence of the set of all subsets of a given set, without specifying how those subsets are formed.  In particular, they need not be extensions of a formula with one free variable, $\phi(v)$, as in the Subset Axiom.  In other words, for any set  $a$, the existence of  $\wp(a)$ is asserted, but the elements of  $\wp(a)$  are `underdetermined'.  The reason for including this axiom is to retain Cantor's Theorem (\emph{i.e.} $|a| < |\wp(a)|$ for all sets $a$) in ZF. 

\end{enumerate}

Although the ZF axioms replace our original paradox-ridden definition of a set as the extension of a formula with one free variable, we will still want to refer to such collections and so we give them a name.

\begin{defn}
A \emph{class} is the extension of a formula with one free variable.  That is, for any formula $\phi(v)$, the corresponding class  $\mathcal{F}$ is given by $\forall x \big[x \in \mathcal{F} \iff \phi(x)\big ]$; in our previous notation, 
$\mathcal{F} = \big\{ x  \, | \, \phi(x) \big\}$. A class that is not a set is a \emph{proper class}.
\end{defn}

\begin{xbox}
\begin{note}
Any set $a$ will be  class.
\end{note}
\end{xbox}

\begin{xbox}
\begin{example}
$\mathcal{Z} = \big\{ x \, | \, \lnot (x \in x ) \big\}$?
\end{example}
\end{xbox}

A proper class $\mathcal{C}$ does not exist as a `completed whole'. Therefore, $\mathcal{C}$ is not eligible to be an element of other collections, either sets or other proper classes.    Moreover,  we cannot form $\wp(\mathcal{C})$.  However, in many ways, proper classes can be handled like sets 
 simply by translating statements involving classes into statements in the language of ZF.  For example, if  $\mathcal{A} = \big\{ x  \, | \, \phi(x) \big\}$ and $\mathcal{B} = \big\{ x  \, | \, \psi(x) \big\}$ are proper classes, then:
\begin{itemize}
\item $\mathcal{A}=\mathcal{B}$ if and only if $\forall x \, \big[ \phi(x) \iff \psi(x) \big]$;
\item $\mathcal{A} \subseteq \mathcal{B}$ if and only if $\forall x \, \big[ \phi(x) \Rightarrow \psi(x) \big]$.
\end{itemize}

\subsection{Development of Set Theory from the Axioms}

\hfill

While one criterion of any axiomatization of set theory is avoidance of the famous set paradoxes, another is retention of as much as possible of naive set theory.

 
 \begin{prop}
 If $a$ and $b$ are sets, then so are $a \cup b$ and $a \cap b$.
 \end{prop}
 
 \begin{xbox}
 \begin{proof}
 (\emph{Hint.}  Note that we cannot \emph{just} use the Axiom of Union for the first case.  For the second, let $\alpha(v) := (v \in a)$; note that this formula has one free variable and one name.)
 \end{proof}
 \end{xbox}
 

\begin{note}
If $a$ is a set, $\bigcup a$ denotes the set of all sets that are elements of {\it some} element of $a$. This is a set by the Axiom of Union.
The notation $\bigcap a$ represents the set of all sets that are elements of {\it every} element of $a$.
\end{note}

\begin{xbox}
\begin{example}
Let $a = \{ p, q, r\}$, where $p = \{ t, u, v, x, y \}$, $q = \{t, v, x, y, z\}$, $r= \{s, t, w, x\}$ and $x = \{ m, n\}$.  Then  $\bigcup a = \dots $ and $\bigcap a = \dots$.
\end{example}
\end{xbox}

\begin{xbox}
\begin{prop}
If $a$ is a set, then $\bigcap a$ is a set.
\end{prop}
\end{xbox}

\begin{xbox}
\begin{notation}
If $x$ and $y$ are sets, then $(x, y)$ denotes the set $\Big\{ \{x\}, \{x, y \} \Big\}$. [Why is this a set? What is $(x,x)$?]
\end{notation}
\end{xbox}

\begin{prop}
If $a$ and $b$ are sets, then $a \times b = \big\{ (x, y) \, | \, x \in a \land y \in b \big\}$ is a set.
\end{prop}

\begin{proof}
If either $a$ or $b$ is $\emptyset$, then so is $a \times b$.  So assume both are nonempty.  Let $y \in b$.  By the Axiom of Replacement, we can replace each $x \in a$ with $(x, y)$ and the result will still be a set, which we denote by $y_a = \big\{ (x, y) \, | \, x \in a \big\}$.  Using the Axiom of Replacement again, we can replace each $y \in b$ with $y_a$ and the result will still be a set, call it $c = \big\{ y_a \, | \, y \in b \big\}$.  Now apply the Axiom of Union to $c$ to get  $\bigcup c = a \times b$.
\end{proof}

Many definitions from naive set theory can be rephrased as formulas with one free variable.


\begin{xbox}
\begin{defn}
Let  $a$ and $b$ be specific sets.  Then:
\begin{enumerate}
\item set $r$ is a \emph{relation from $a$ to $b$} iff $\rho_{a,b}(r) := r \in \wp(a \times b)$; 
\item set $e$ is an \emph{equivalence relation on $a$} iff $\varepsilon_a(e) := \rho_{a,a}(e) \land \forall x \big( x \in a  \Rightarrow (x,x) \in e \big) \land \dots$; 
\item set $f$ is a \emph{function from $a$ to $b$} iff $\zeta_{a,b}(f): = \dots$;
\item set $g$ is an \emph{injection from $a$ to $b$} iff  $\iota_{a,b}(g) := \dots$;
\item set $h$ is a \emph{surjection from $a$ to $b$} iff  $\gamma_{a,b}(h) := \dots$;
\item set $k$ is a \emph{bijection from $a$ to $b$} iff  $\beta_{a,b}(k) := \dots$.
\end{enumerate}
\end{defn}
\end{xbox}

\begin{xbox}
\begin{example}
Let $a$ be a set; [express the collection $\mathcal{A}$ of all sets equipotent to $a$ as a class.]  If $\mathcal{A}$ is a set, then by the Power Set Axiom, we can form $\wp(\mathcal{A})$ and then we run into the fourth set paradox in Chapter 6.  Hence, $\mathcal{A}$ must be a proper class. Recall that if it is a proper class, we cannot form $\wp(\mathcal{A})$ and so the paradox is avoided. 
\end{example}
\end{xbox}

\end{document}