\documentclass{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{enumerate}

\usepackage{hyperref}

\usepackage{ifthen}
\usepackage{ulem} % for strikethrough \sout{...} command
\usepackage{color}

\usepackage{wasysym}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.25in}
\setlength{\evensidemargin}{-0.25in}
\setlength{\topmargin}{-0.45in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.65in}
\setlength{\textwidth}{7in}

\newcommand{\bdot}{\, {\scriptstyle{\bullet}} \,}
\newcommand{\B}[1]{{\bf {#1}}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}

\newcommand{\myspace}{\parbox[c][0.25in]{0.25in}{\hfill}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}
\newcommand{\force}{{\noindent $\mbox{\;}$}}

\newcommand{\diagquotient}[2]{\displaystyle{{#1 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} \hspace*{0.1in} {\; \atop #2}}}


\newcommand{\F}{\mathbb{F}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}

\newcommand{\LEMMA}{\vspace{0.05in} \noindent \fbox{\large\bf Lemma:}  }
\newcommand{\COR}{\vspace{0.05in} \noindent \fbox{\large\bf Corollary:}  }
\newcommand{\DEF}{\vspace{0.05in} \noindent \fbox{\large\bf Definition:}  }
\newcommand{\THM}{\vspace{0.05in} \noindent \fbox{\large\bf Theorem:}  }
\newcommand{\EX}{\vspace{0.05in} \noindent \fbox{\large\bf Example:}  }
\newcommand{\bproof}{\vspace{0.1in} \noindent {\bf Proof:} }
\newcommand{\eproof}{$\blacksquare$ \vspace{0.05in}}


\begin{document}

\pagestyle{empty}

\noindent
\force \hfill {\large\bf Zermelo-Fraenkel Set Theory with The Axiom of Choice} \hfill \force

\vspace{0.15in}

\noindent
``To choose one sock from each of infinitely many pairs of socks requires the Axiom of choice,\\ \force \hfill but for shoes the Axiom is not needed.'' -- Bertand Russell

\vspace{-0.05in}

\noindent
``Give me reason, but don't give me choice.\\ \force \hfill 'Cause I'll just make the same mistake again.'' -- James Blunt (\href{https://youtu.be/b3c32wBYdU0}{Same Mistakes})

\vspace{0.1in}

\noindent Zermelo-Fraenkel set theory is a standard axiomization of set theory. These axioms were proposed by Ernst Zermelo around 1907
and then tweaked by Abraham Fraenkel (and others) around 1922. Without Axiom 9, these axioms form ``ZF'' set theory. If we add Axiom 9 (i.e., the axiom of choice)
we have ``ZFC'' set theory. ZFC forms a foundation for most of modern mathematics. While there are other axiom systems and different ways 
to set up the foundations of mathematics, no system is as widely used and as well accepted as ZFC. 

\vspace{0.1in}

\noindent \force \hfill {\large\bf The Axioms of ZFC} \hfill \force

%\vspace{-0.1in}

\begin{description} \setlength\itemsep{-2pt}
   \item[Axiom 0: ``Set Existence''] $\exists x\,(x=x)$ 
             \quad This axiom simply states that ``something exists.'' Without it we might have an vacuous (very uninteresting) theory.

   \item[Axiom 1: ``Extensionality''] $\forall x\, \forall y\, (\forall z\, (z \in x \leftrightarrow z \in y) \to x=y)$
            \quad Equality asserts that if two objects are the same, then anything we can say about one should be true of the other. Thus if two sets
            are equal, they must have the same elements. Extensionality simply states that the converse is also true -- that is -- sets
            are completely determined by their elements.

   \item[Axiom 2: ``Foundation''] $\forall x\, [\exists y\,(y \in x) \to \exists z (z \in x \wedge \neg \exists w \,( w \in x \wedge w \in z))]$
            \quad This axiom makes sure we don't have infinite regresses for the ``$\in$'' relation. In particular, this makes sure things like 
            $x = \{ x \}$ (so that $x\in x \in x \in \cdots$) and $(x \in y) \wedge (y \in z) \wedge (z \in x)$  (so $x \in y \in z \in x$) cannot happen. 

   \item[Axiom 3: ``Comprehension Scheme''] For each formula $\phi$ with free variables among $x$, $z$, $w_1$, $\dots$, $w_n$, \quad\\
           $\forall z \,\forall w_1, \dots, w_n\, \exists y\, \forall x\, (x \in y \leftrightarrow x \in z \wedge \phi)$ \quad
           This axiom scheme simply asserts that the set $y = \{ x \in z \,|\, \phi \}$ exists (as long as $\phi$ does not have $y$ as a free variable -- to
           avoid self-referential definitions). Notice that comprehension only allows us to build new sets as subsets of existing sets. So we avoid asserting
           the existence of the set of all sets, $\{ x \,|\, x=x \}$, or other paradoxical entities. 

   \item[Axiom 4: ``Pairing''] $\forall x\, \forall y\, \exists z\, (x \in z \wedge y \in z)$ 
           \quad This axiom allows us to build up sets from a pair of elements. In particular, this along with comprehension and extensionality
           asserts that there is a unique set whose elements are $x$ and $y$, we call this set $\{ x,y \}$. 

   \item[Axiom 5: ``Union''] $\forall \mathcal{F}\, \exists A\, \forall Y\, \forall x\, (x \in Y \wedge Y \in \mathcal{F} \to x \in A)$
           \quad As indicated by its name, this axiom (when used with comprehension) guarantees the existence of the union of sets. Notice that
           ``$A$'' in this axiom will contain $\cup \mathcal{F}$. Comprehension then allows us to pair down $A$ to be exactly $\cup \mathcal{F}$.

   \item[Axiom 6: ``Replacement Scheme''] For each formula $\phi$ with free variables among $x$, $y$, $A$, $w_1$, $\dots$, $w_n$, \quad\\
           $\forall A\, \forall w_1, \dots, w_n\, [\forall x\in A\, \exists ! y\, \phi \to \exists Y\, \forall x\in A\, \exists y\in Y\, \phi]$ \quad
           This is another axiom scheme which allows us to build new sets. Essentially if we have a relation $\phi(x,y)$ which associates a $y$ to each $x$, then
          this axiom allows us to form the set of all $y$'s. Thus $\{ y \,|\, \exists x \in A \mbox{ such that } \phi(x,y) \}$ exists. We might be concerned that $y$ is allowed
          to be anything, but keep in mind that we have one $y$ per $x$, so this set is no bigger than $A$.

   \item[Axiom 7: ``Infinity''] $\exists x\,(0 \in x \wedge \forall y \in x\, (S(y) \in x))$ 
            \quad where $S(y) = y \cup \{ y \}$ (which exists using union, paring, and comprehension) and $0 = \{ x \,|\, x \not= x\}$ is the empty set (which exists
            using set existence and comprehension). Notice if we let $1=S(0)$, $2=S(1)$, etc. then this axiom asserts that we have a set which contains 
            $\mathbb{N}$ (the natural numbers). Less specifically, this axiom asserts the existence of an infinite set.

   \item[Axiom 8: ``Power Set''] $\forall x\, \exists y\, \forall z\,(z \subseteq x \to z \in y)$
           \quad Note that $z \subseteq x$ is an abbreviation for $\forall a\, (a \in z \to a \in x)$. As its name indicates, this axiom says that given a 
           set $x$ there is another set $y$ which contains all of the subsets of $x$. So power set plus comprehension give us the existence of the power set
           of any set.

   \item[Axiom 9: ``Choice''] $\forall A\, \exists R\, (R \mbox{ well-orders } A)$
           \quad The axiom of choice needs some explaination. First, using pairing and comprehension we can form the set $\{x, \{x,y\}\}$ given any sets $x$ and $y$.
            Denote $\{x, \{x,y\}\} = (x,y)$ and then use replacement, comprehension and union to rig up the cartesian product 
           $A \times B = \{ (x,y) \,|\, x \in A \wedge y \in B \}$ of any two sets $A$ and $B$. Next, we call any subset $R$ of $A \times A$ a {\it relation} on $A$.
           A {\it transitive relation} is a relation such that $\forall x,y,z \in A,\, (x,y) \in R \wedge (y,z) \in R \to (x,z) \in R$. $R$ is {\it irreflexive} if 
           $\forall x \in A,\, (x,x) \not\in R$. Finally, we say {\it trichotomy} holds if $\forall x,y,z \in A\, (x=y) \vee (x,y) \in R \vee (y,x) \in R$. If $R$ is an irreflexive
           transitive relation for which trichotomy holds, we call $R$ a {\it total ordering} of $A$ [For example: $R = \{ (x,y) \,|\, x<y \}$ is a total ordering of
           $\mathbb{R}$.] We say that a relation $R$ is a {\it well-ordering} of $A$ (or $R$ {\it well-orders} $A$) if $R$ is a total order such that  every non-empty
           subset of $A$ has an $R$-least element. In other words, given $B \subseteq A$ such that $B \not= 0$, then $\exists x \in B$ such that $(x,y) \in R$
           for all $y \in B$. [For example: $<$ does not well order $\mathbb{R}$ -- there's no ``least'' real number. On the other hand $<$ does well order 
           $\mathbb{N}$ (the natural numbers) because given a non-empty set of natural numbers, there is a smallest one in that set.]

\end{description}

\vspace{0.1in}

As a note, many of these axioms are {\it independent} of each other. For example, one could do set theory with ZFC minus the infinity axiom. Such a set theory would 
be agnostic about infinite sets. In fact, one could take a negation of the infinity axiom and have a theory which only deals with finite sets. In general, if we have an 
axiom system with axioms A and consider a new axiom B. We say that B is {\bf independent} from A if given the consistency of axiom system A, we have that both 
A+B and A+($\neg$B) are also consistent. 
In other words, A really has nothing to say about B. Of course, not all of these axioms are independent. Several really require others for their statements to make sense.
Even more, our very first axiom is actually redundant (it follows from the other axioms)!

\vspace{0.1in}

After you get to know the axioms pretty well, they all seem quite reasonable with the exception of the Axiom of Choice (AC). Being able to well order any set seems 
like asking a lot. Think of the real numbers, for example, how would you go about well-ordering them? In fact, it turns out that one cannot construct any such ordering.
AC asserts such a well ordering must exist, but we can never get our hands on it in any concrete way (this is one of Cohen's earliest set forcing results).
Historically, some 
mathematicians have rejected AC because it leads to a few counter-intuitive results such as the ``Banach-Tarski Paradox'' (which isn't a paradox in the
logical sense, but a very odd theorem which at face value seems like it shouldn't be true). On the other hand, most mathematicians just accept AC and go on with 
life. A few reasons for this are: 
\begin{enumerate}
   \item Many mathematicians don't know or don't care much about foundational issues, so they just blindly use AC without thinking about it. 
   \item It turns out that AC is equivalent to some very nice statements that seem like they ought to be true. For example, AC is equivalent to\dots
   \begin{itemize}
      \item Every vector space has a basis.
      \item Given a collection of non-empty sets, it is possible to pick out an element from each one of those sets (this is where the axiom gets its name). 
      \item The cartesian product of (possibly infinitely many) non-empty sets is itself non-empty.
      \item Any partially ordered set (whatever that means) in which each chain (totally ordered subsets) has an upper bound, must have at least one maximal element. 
               This statement is called ``Zorn's Lemma'' and is encountered in many branches of mathematics.
   \end{itemize}
       If one wants to use these results, one must accept AC as true.
   \item G\"odel showed that given ZF (Zermelo-Fraenkel set theory without AC) is self-consitent, then so is ZFC. This means that AC doesn't introduce any
            inconsistencies (if ZF is consistent itself). Later Cohen showed that ZF plus $\neg\mbox{AC}$ is consistent if ZF is. In other words, AC is independent from ZF.
            Thus the truth of AC is unknowable from within ZF. ZF doesn't know whether it's true or not. So you can ``take it or leave it''.
\end{enumerate}

{\it Note:} You may have picked up on some annoying contingencies in the final point above: ``If XXX is consistent, then YYY is consistent''. Why don't we just state ZF and/or ZFC is consistent?
It turns out that this is essentially impossible. One of G\"odel's incompleteness theorems states that given any sufficiently complicated axiom system (basically one that can encode
certain number theoretic statements -- like ZF can), such a axiom system cannot prove its own consistency. Thus if con(ZF) is the statement that ``ZF is consistent'', then ZF cannot 
prove con(ZF). 



\end{document}
