\documentclass[10pt]{article}
%\input mymacros
%\nopagenumbers
\def\bix{\fbox{$\,^{\,}$}}
\setlength{\textwidth}{5.8in}
\setlength{\topmargin}{-.5in}
\oddsidemargin=0.5in
\setlength{\textheight}{9in}
\newcommand{\sepa}{\medbreak
\begin{center}$\,$\hbox to5cm{\hrulefill}$\,$\end{center}
\medbreak}
\raggedbottom
\def\pline#1{#1}
%\def\plin#1#2{\mbox{\hbox to 1.5cm\hfill(#1)}}#2}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\def\rr{{\rm I}\kern-.2em{\rm R}}
\def\nn{{\rm I}\kern-.2em{\rm N}}
\def\eps{\varepsilon}
\def\imply{\Rightarrow}
\font\mymagtworm=cmr10 scaled\magstep 2
\font\mymagonebf=cmbx10 scaled\magstep 1
\font\mymagtwobf=cmbx10 scaled\magstep 2
\font\mymagtwoit=cmti10 scaled\magstep 2
\begin{document}
\centerline{{\mymagtwobf MATHEMATICS 300 --- FALL 1998}}
\bigbreak
\centerline{{\mymagtwoit Introduction to Mathematical Reasoning}}
\medbreak
\centerline{Instructor: H. J. Sussmann} 

\medbreak
\centerline{{\bf HANDOUT NO. 11.}  November 4, 1998}

\medbreak
\centerline{{\it Revised and expanded, November 9, 1998. Revised again
Nov. 16, 1998}}

\raggedbottom
\def\rrbf{{\bf R}}
\def\rr{{\bf R}}
\def\mitem{\medbreak\item}
\def\ste{$\qquad$}
\def\stef{$\qquad\qquad\qquad\qquad$}
\def\stetw{$\qquad\qquad$}
\newcount{\statco}
\newcount{\quesco}
\newcount{\defco}
\newcount{\notco}
\newcount{\remco}
\newcount{\rulco}
\newcount{\drulco}
%\def\co#1{#1}
\def\rulo{\global\advance\rulco by 1
\medbreak\noindent{\bf  RULE
\the\rulco.}\ }
\def\drulo{\global\advance\drulco by 1
\medbreak\noindent {\bf DERIVED RULE
\the\drulco.}\ }
\def\justo{
\medbreak\noindent {\bf JUSTIFICATION$\,$:}\ \ }
\def\co#1{}
\def\ep{\varepsilon}
\def\lto{\Leftrightarrow}
\def\clo{{\rm Clos}}
\defco=0
\statco=0
\remco=0
\rulco=0
\drulco=0
\notco=0
\quesco=1
\def\ino{{\rm Int}}

\medbreak\noindent{\sl NOTE: This is the second (and, I hope, final)
version of this handout. The first version was just 6 pages. In this second
version, the first 6 pages are still more or less the same as in the first
version, except that I have corrected some typos, made a change in the list
of problems for Homework No. 8, following what I said in class on November
4, and also made a few other changes.}

\bigbreak
\begin{center}
{\bf CONTENTS}
\end{center}

\noindent HOMEWORK ASSIGNMENT NO. 8, DUE ON MONDAY, NOVEMBER 16\ \hrulefill
\ \ \pageref{ho8}

\noindent TYPOS IN HANDOUT NO. 10\ \hrulefill\ \ \pageref{typosha10}

\noindent TYPOS IN THE BOOK\ \hrulefill\ \  \pageref{typobook}

\noindent READING FOR NOVEMBER 9 AND 11\ \hrulefill\ \ \pageref{reading}

\noindent SOME EXAMPLES OF PROOFS IN ``PURE LOGIC''\ \hrulefill\ \ \pageref{pure}

\noindent AXIOMS FOR EQUALITY\ \hrulefill\ \ \pageref{equaxi}

\noindent ABBREVIATIONS\ \hrulefill\ \ \pageref{abbrevi}

\noindent THE ABBREVIATIONS $\neq$ and $\exists!$\ \hrulefill\ \
\pageref{twoaabre}  

\noindent USING ABBREVIATIONS\ \hrulefill\ \ \pageref{usingabre}

\noindent SET THEORY\ \hrulefill\ \ \pageref{setth}

\noindent THE ABBREVIATION ``$\{\ldots\}$''\ \hrulefill\ \ \pageref{abbbraces}

\noindent THE AXIOMS OF NA\"IVE SET THEORY\ \hrulefill\ \ \pageref{axnaive}

\noindent SOME SET-THEORY DEFINITIONS\ \hrulefill\ \ \pageref{setdefs}

\noindent EXAMPLES  OF SET-THEORY PROOFS\ \hrulefill\ \ \pageref{exaset}

\noindent A CATASTROPHE\ \hrulefill\ \ \pageref{cata}

\noindent THE RUSSELL PARADOX\ \hrulefill\ \ \pageref{russell}

\noindent FREGE\ \hrulefill\ \ \pageref{frege}

\noindent RUSSEL'S ARGUMENT\ \hrulefill\ \ \pageref{russellarg}

\noindent WHY IS A SINGLE CONTRADICTION SO BAD?\ \hrulefill\ \ \pageref{whyone}

\noindent AXIOMATIC SET THEORY\ \hrulefill\ \ \pageref{exasetaxi}

\noindent THE BASIC AXIOMS OF AXIOMATIC SET THEORY\ \hrulefill\ \ \pageref{axaxio} 

\noindent SOME OTHER AXIOMS OF AXIOMATIC SET THEORY\ \hrulefill\ \
\pageref{someother} 

\noindent HOW DO WE KNOW THAT THERE ARE ANY SETS AT ALL?\ \hrulefill\ \ \pageref{exiset}

\bigbreak
\begin{center}
{\large{\bf HOMEWORK ASSIGNMENT NO. 8, DUE ON MONDAY, NOVEMBER 16}}\label{ho8}
\end{center}

\bi
\item[1.] Problems 8, 9, 10, 13, 14, and 15  in pages 94-95-96,
nonstarred parts only, but do Problem 15(a) even though it is starred. 

\item[2.] Problems 4(b), 5(b), (c), 6 (including part (d)), 12, and 
15 in pages 102-103-104.

\item[3.] Prove or disprove:  the product of 728 consecutive natural numbers
is always divisible by 728!.   (Recall: $n!$ is the {\it factorial} of $n$,
defined inductively by $1!=1$, $(n+1)!=(n+1).n!$ for $n\in\nn$.) 

\item[4.] Do problem 12 of page 72 using the rules of Handout 10, 
the definitions of $\subseteq$, $\cup$, $\cap$, $\emptyset$ and 
$=$ (given in the book) {\bf and nothing else}. {\sl (NOTE: this problem 

was originally part of homework assignment No. 7, due on November 4. 
On November 4, I announced in class that (a)~the deadline for homework
assignment No. 7 was extended to November 9, and (b)~this particular
problem, which was No. 3 of homework assignment No. 7, was now moved to 
homework assignment No. 8.)}

\ei

\sepa

\begin{center}
{\large{\bf TYPOS IN HANDOUT NO. 10}} \label{typosha10}
\end{center}

\medbreak\noindent Please correct the following two typos in Handout No. 10
(revised version):

\bi
\item{} In page 1, line 5, where it says ``Revised November 22, 1998,'' it
should say ``Revised November 2, 1998.''

\item{} In page 10, line 3, where it says 
``Rule 3 or Rule 4 or Rule 5,'' it should say ``Rule 3 or Rule 5 or Rule
6.''    
\ei

\sepa

\begin{center}
{\large{\bf TYPOS IN THE BOOK}}\label{typobook}
\end{center}

\medbreak
\bi
\item{} In page 86, line 5 (right below statement (ii)), where it says
``$S\in\nn$'' it should say ``$S=\nn$.''

\item{} In page 88, box, the title should be 
``PROOF OF $(\forall n\in\nn)P(n)$ BY INDUCTION'' rather than
``PROOF OF $(\forall x\in\nn)P(n)$ BY INDUCTION.'' 

\item{} In page 88, box, the ``basic step'' should be 
``Show that $P(1)$ is true'' rather than 
``Show that $1\in S$.'' 

\item{} In page 103, 2nd line of part (d) of problem 6, 
where it says ``$\alpha=\frac{1-\sqrt{5}}{2}$,'' it should say 
``$\beta=\frac{1-\sqrt{5}}{2}$.'' 
\ei

\sepa

\begin{center}
{\large{\bf READING FOR NOVEMBER 9 AND 11}}\label{reading}
\end{center}

\bi
\item{} Book, sections 2.4 and 2.5. 

\item{} Handouts No. 10 and 11. 
\ei


\sepa

\begin{center}
{\large{\bf SOME EXAMPLES OF PROOFS IN ``PURE LOGIC''}}\label{pure}
\end{center}

\medbreak\noindent Let $p(x)$ be a formula that has no quantifiers 
in $x$ and has no free variables other than $x$.

\medbreak\noindent {\bf THEOREM I.}\ $(\exists x)p(x)\lto
(\sim(\forall x)(\sim p(x)))$. 

\medbreak\noindent {\bf INFORMAL PROOF:} Suppose 
that $(\exists x)p(x)$. Let us show that 
$\sim(\forall x)(\sim p(x))$ by contradiction. 
Assume $(\forall x)(\sim p(x))$. Pick an $a$ such that $p(a)$, which is
possible because we are assuming that such an $a$ exists. 
Since $(\forall x)(\sim p(x))$, we get $\sim p(a)$, contradicting the fact
that $p(a)$. Therefore the assumption that 
$(\forall x)(\sim p(x))$ leads to a contradiction. So 
$\sim(\forall x)(\sim p(x))$, as desired.

Now suppose that $\sim(\exists x)p(x)$. Let us show that 
$(\forall x)(\sim p(x))$. 
Pick an arbitrary $a$.  We want to prove that $\sim p(a)$. Suppose
this was false, i.e. suppose that $p(a)$.  Then it would follow that 
$(\exists x)p(x)$, contradictiong our assumption that 
$\sim(\exists x)p(x)$. So $p(a)$ leads to a contradiction. Therefore
$\sim p(a)$. Since $a$ was arbitrary, we have established that 
$(\forall x)(\sim p(x))$, as desired. 

So we have shown that 
$(\exists x)p(x)$ implies $\sim(\forall x)(\sim p(x))$, and 
also that $\sim(\exists x)p(x)$ implies $(\forall x)(\sim p(x))$.
Therefore 
$(\exists x)p(x)\lto(\sim(\forall x)(\sim p(x)))$. \hfill{\bf QED}

\medbreak\noindent {\bf FORMAL PROOF:}

\noindent(1.\&)\stetw Assume $(\exists x)p(x)\,.$\hfill[Preparation to apply
Rule 3]

\noindent(2.\&.\&)\stetw Let $a$ be such that $p(a)\,.$\hfill[From (1), 
preparation to apply Rule 6]

\noindent(3.\&.\&.\&)\stetw Assume $(\forall x)(\sim
p(x))\,.$\hfill[Preparation to apply Rule 3]

\noindent(4.\&.\&.\&)\stetw $\sim p(a)\,.$\hfill[Rule 4, from (3)]

\noindent(5.\&.\&.\&)\stetw $(\sim p(a))\imply(p(a)\imply
(\sim(\forall x)(\sim p(x))))\,.$\hfill[Tautology
$(\sim\alpha)\imply(\alpha\imply\beta)$]

\noindent(6.\&.\&.\&)\stetw $p(a)\imply
(\sim(\forall x)(\sim p(x)))\,.$\hfill[Modus Ponens from 
(4) and (5)]

\noindent(7.\&.\&.\&)\stetw $\sim(\forall x)(\sim p(x))\,.$\hfill[Modus Ponens
from (2) and (6)] 

\noindent(8.\&.\&)\stetw $(\forall x)(\sim p(x))
\imply(\sim(\forall x)(\sim p(x)))\,.$\hfill[Rule 3, from 
(3) and (7)]

\noindent(9.\&.\&)\stetw $((\forall x)(\sim p(x))
\imply(\sim(\forall x)(\sim p(x))))\imply
(\sim(\forall x)(\sim p(x)))\,.$

\hfill[Tautology $(\alpha\imply(\sim\alpha))\imply(\sim\alpha)$] 

\noindent(10.\&.\&)\stetw $\!\!\!\!\!\!\sim(\forall x)(\sim
p(x))\,.$\hfill[Modus Ponens, from (8) and (9)] 

\noindent(11.\&)\stetw 
$\!\!\!\sim(\forall x)(\sim p(x))\,.$\hfill[Rule 6, from (2) and (10)]

\noindent(12)\stetw 
$\!\!\!(\exists x)p(x)\imply(\sim(\forall x)(\sim p(x)))\,.$\hfill[Rule 3,
from (1) and (11)]

\noindent(13.\&)\stetw 
$\!\!\!{\rm Assume}$ $\sim(\exists x)p(x)\,.$\hfill[Preparation to apply
Rule 3] 

\noindent(14.\&.\&)\stetw 
$\!\!\!{\rm Let }$ $a$ be arbitrary.\hfill[Preparation to apply Rule 5] 

\noindent(15.\&.\&.\&)\stetw 
$\!\!\!{\rm Assume }$ $p(a)$.\hfill[Preparation to apply Rule 3] 

\noindent(16.\&.\&.\&)\stetw $(\exists x)p(x)\,.$\hfill[Rule 7, from (15)] 

\noindent(17.\&.\&.\&)\stetw 
$((\sim\exists x)p(x))\imply((\exists x)p(x)\imply(\sim p(a)))\,.$\hfill
[Tautology $(\sim \alpha)\imply(\alpha\imply\beta)$] 

\noindent(18.\&.\&.\&)\stetw 
$(\exists x)p(x)\imply(\sim p(a))\,.$\hfill
[Modus Ponens from (13) and (17)] 

\noindent(19.\&.\&.\&)\stetw 
$\sim p(a)\,.$\hfill[Modus Ponens from (16) and (18)] 

\noindent(20.\&.\&)\stetw 
$\!\!\!p(a)\imply(\sim p(a))\,.$\hfill[Rule 3, from (15) and (19)] 

\noindent(21.\&.\&)\stetw 
$\!\!\!(p(a)\imply(\sim p(a)))\imply(\sim p(a))\,.$\hfill[Tautology
$(\alpha\imply(\sim \alpha))\imply(\sim \alpha)$] 

\noindent(22.\&.\&)\stetw 
$\!\!\!\sim p(a)\,.$\hfill[Modus Ponens from (20) and (21)]

\noindent(23.\&)\stetw 
$\!\!\!(\forall x)(\sim p(x))\,.$\hfill[Rule 5, from (14) and (22)]

\noindent(24)
\stetw $\!\!\!(\sim(\exists x)p(x))\imply(\forall x)(\sim p(x))\,.$\hfill
[Rule 3, from (13) and (23)] 


\noindent(25) \stetw $\!\!\!((\exists x)p(x)\imply(\sim(\forall x)(\sim p(x))))
\imply$


\hfill $(((\sim(\exists x)p(x))\imply(\forall x)(\sim p(x)))
\imply((\exists x)p(x)\lto(\sim(\forall x)(\sim p(x)))))\,.$

\hfill[Tautology $(\alpha\imply(\sim\beta))\imply(((\sim\alpha)\imply\beta)
\imply(\alpha\lto(\sim\beta)))$]

\noindent(26) \stetw $\!\!\!
((\sim(\exists x)p(x))\imply(\forall x)(\sim p(x)))
\imply((\exists x)p(x)\lto(\sim(\forall x)(\sim p(x))))\,.$

\hfill[Modus Ponens from (12) and (25)]

\noindent(27) \stetw $\!\!\!
(\exists x)p(x)\lto(\sim(\forall x)(\sim p(x)))\,.$
\hfill[Modus Ponens from (24) and (26)]

\hfill{\bf QED}

\bigbreak\noindent{\sl Read the above proofs carefully, and make sure you
see that the ``informal proof'' and the ``formal proof'' really say the
same thing. The formal proof is the detailed execution of the outline given
in the informal proof. The informal proof can be thought of as an
abbreviated narrative describing, or outlining, the formal proof.}


\bigbreak
\begin{center}
{\bf ANOTHER ``PURE LOGIC'' EXAMPLE}
\end{center}

\medbreak\noindent Let $p(x)$, $q(x)$ be formulas having no quantifiers in
$x$ and having no free variables other than $x$. 

\medbreak\noindent {\bf THEOREM II.}  $(\forall x)(p(x)\wedge q(x))\lto
((\forall x)p(x)\wedge(\forall x)q(x))$. 

\medbreak\noindent{\bf INFORMAL PROOF}:  Suppose 
$(\forall x)(p(x)\wedge q(x))$. We prove that $(\forall
x)p(x)\wedge(\forall x)q(x)$. Pick an arbitrary $a$. Then 
$p(a)\wedge q(a)$. So, in particular, $p(a)$, and, since $a$ was arbitrary,
we have shown that $(\forall x)p(x)$. A similar argument shows that 
$(\forall x)q(x)$. So $(\forall x)p(x)\wedge(\forall x)q(x)$, as desired. 

We now prove the converse. Suppose that 
$(\forall x)p(x)\wedge(\forall x)q(x)$. We prove that 
$(\forall x)(p(x)\wedge q(x))$. Let $a$ be arbitrary. 
Since we are assuming that $(\forall x)p(x)\wedge(\forall x)q(x)$, it
follows in particular that $(\forall x)p(x)$, so $p(a)$ holds, by
specialization. A smilar argument shows that $q(a)$ holds. 
So $p(a)\wedge q(a)$. Since $a$ was arbitrary, we have 
shown that $(\forall x)(p(x)\wedge q(x))$, as desired. \hfill{\bf QED}


\medbreak\noindent{\bf FORMAL PROOF}:

\noindent(1.\&) \stetw Assume $(\forall x)(p(x)\wedge
q(x))\,.$\hfill[Preparation to apply Rule 3]

\noindent(2.\&.\&) \stetw Let $a$ be arbitrary. 
\hfill[Preparation to apply Rule 5]

\noindent(3.\&.\&) \stetw $p(a)\wedge q(a)\,.$
\hfill[Rule 4, from (1)]

\noindent(4.\&.\&) \stetw $(p(a)\wedge q(a))\imply p(a)$
\hfill[Tautology $(\alpha\wedge\beta)\imply\alpha$]

\noindent(5.\&.\&) \stetw $p(a)\,.$
\hfill[Modus Ponens from (3) and (4)]

\noindent(6.\&) \stetw $(\forall x)p(x)\,.$\hfill[Rule 5, from (2) and 
(5)] 

\noindent(7.\&.\&) \stetw Let $a$ be arbitrary. 
\hfill[Preparation to apply Rule 5]

\noindent(8.\&.\&) \stetw $p(a)\wedge q(a)\,.$
\hfill[Rule 4, from (1)]

\noindent(9.\&.\&) \stetw $(p(a)\wedge q(a))\imply q(a)\,.$
\hfill[Tautology $(\alpha\wedge\beta)\imply\beta$]

\noindent(10.\&.\&) \stetw $\!\!\!q(a)\,.$
\hfill[Modus Ponens from (8) and (9)]

\noindent(11.\&) \stetw $\!\!\!(\forall x)q(x)\,.$\hfill[Rule 5, from
(7) and  (10)] 

\noindent(12.\&) \stetw $\!\!\!(\forall x)p(x)\imply(
(\forall x)q(x)\imply((\forall x)p(x)\wedge
(\forall x)q(x)))\,.$\hfill[Tautology
$\alpha\imply(\beta\imply(\alpha\wedge\beta))$]

\noindent(13.\&) \stetw $\!\!\!(\forall x)q(x)\imply((\forall
x)p(x)\wedge (\forall x)q(x))\,.$\hfill[Modus Ponens from (6) and (12)]

\noindent(14.\&) \stetw $\!\!\!(\forall x)p(x)\wedge (\forall x)q(x)
\,.$\hfill[Modus Ponens from (11) and (13)]

\noindent(15) \stetw $\!\!\!
(\forall x)(p(x)\wedge q(x))\imply
((\forall x)p(x)\wedge (\forall x)q(x))
\,.$\hfill[Rule 3, from (1) and (14)]

\noindent(16.\&) \stetw $\!\!\!{\rm Assume}$ 
$(\forall x)p(x)\wedge (\forall x)q(x)\,.$\hfill[Preparation to apply 
Rule 3]

\noindent(17.\&) \stetw $\!\!\!((\forall x)p(x)\wedge (\forall x)q(x))
\imply(\forall x)p(x)\,.$\hfill[Tautology
$(\alpha\wedge\beta)\imply\alpha$] 

\noindent(18.\&) \stetw $\!\!\!(\forall x)p(x)\,.$\hfill[Modus Ponens
from (16) and (17)]

\noindent(19.\&) \stetw $\!\!\!((\forall x)p(x)\wedge (\forall x)q(x))
\imply(\forall x)q(x)\,.$\hfill[Tautology
$(\alpha\wedge\beta)\imply\beta$] 

\noindent(20.\&) \stetw $\!\!\!(\forall x)q(x)\,.$\hfill[Modus Ponens
from (16) and (19)]

\noindent(21.\&.\&) \stetw $\!\!\!{\rm Let}$ $a$ be
arbitrary.\hfill[Preparation to apply Rule 5]

\noindent(22.\&.\&) \stetw $\!\!\!p(a)\,.$\hfill[Rule 4, from 
(18)]

\noindent(23.\&.\&) \stetw $\!\!\!q(a)\,.$\hfill[Rule 4, from 
(20)]

\noindent(24.\&.\&) \stetw $\!\!\!p(a)\imply(q(a)\imply(p(a)\wedge
q(a)))\,.$\hfill[Tautology $\alpha\imply(\beta\imply(\alpha\wedge\beta))$] 

\noindent(25.\&.\&) \stetw $\!\!\!q(a)\imply(p(a)\wedge
q(a))\,.$\hfill[Modus Ponens from (22) and (24)]


\noindent(26.\&.\&) \stetw $\!\!\!p(a)\wedge
q(a)\,.$\hfill[Modus Ponens from (23) and (25)]

\noindent(27.\&) \stetw $\!\!\!(\forall x)(p(x)\wedge q(x))\,.$\hfill
[Rule 5, from (21) and (26)]

\noindent(28) \stetw $\!\!\!((\forall x)p(x)\wedge (\forall x)q(x))
\imply(\forall x)(p(x)\wedge q(x))\,.$\hfill[Rule 3, from (16) and (27)]


\noindent(29) \stetw $\!\!\!
((\forall x)(p(x)\wedge q(x))\imply
((\forall x)p(x)\wedge (\forall x)q(x)))$

\stetw $\,\,\,\imply((((\forall x)p(x)\wedge (\forall x)q(x))
\imply(\forall x)(p(x)\wedge q(x)))$

\stetw $\,\,\,\imply((\forall x)(p(x)\wedge q(x))\lto
((\forall x)p(x)\wedge (\forall x)q(x))))\,.$

\hfill[Tautology
$(\alpha\imply\beta)\imply((\beta\imply\alpha)\imply(\alpha\lto\beta))$] 

\noindent(30) \stetw $\!\!\!(((\forall x)p(x)\wedge (\forall x)q(x))
\imply(\forall x)(p(x)\wedge q(x)))$

\ste $\qquad\imply((\forall x)(p(x)\wedge q(x))\lto
((\forall x)p(x)\wedge (\forall x)q(x)))\,.$\hfill[Modus Ponens, from (15) and (29)]

\noindent(31) \stetw $\!\!\!(\forall x)(p(x)\wedge q(x))\lto
((\forall x)p(x)\wedge (\forall x)q(x))\,.$\hfill[Modus Ponens, from (28) and (30)]

\hfill{\bf QED}


\bigbreak\noindent{\sl Once again, you should read the above proofs
carefully, and make sure you 
see that the ``informal proof'' and the ``formal proof'' really say the
same thing. The formal proof is the detailed execution of the outline given
in the informal proof. The informal proof can be thought of as an
abbreviated narrative describing, or outlining, the formal proof.}

\bigbreak\noindent{\bf QUESTION:} Can you prove using the same technique 
that 
$$
(\forall x)(p(x)\vee q(x))\lto((\forall x)p(x)\vee(\forall x)q(x))\,\,?
$$






\bigbreak
\centerline{\hbox to5cm{\hrulefill}}

\bigbreak
\centerline{{\bf TWO MORE EXAMPLES OF ``PURE LOGIC'' PROOFS}}

\medbreak\noindent
Let $q(x)$ be a formula having no quantifiers in $x$ and having no free
variables other than $x$, and let $r$ be a sentence (that is,
a formula without any open variables).

\medbreak\noindent{\bf THEOREM III:} 
$(\exists x)(r\wedge q(x))\imply (r\wedge  (\exists x)q(x))\,.$ 


\medbreak\noindent{\bf THEOREM IV:} $(\forall x)(r\vee
q(x))\imply(r\vee  (\forall x)q(x))\,.$ 

\def\po{\phantom{1}}


\bigbreak\noindent{\bf INFORMAL PROOF OF THEOREM III:}  Suppose 
$(\exists x)(r\wedge q(x))$. We will prove that $r\wedge(\exists x)q(x)$. 
Pick $a$ such that $r\wedge q(a)$.   Then $r$ and $q(a)$ hold. 
Since $q(a)$ is true, we have $(\exists x)q(x)$. Since we also have $r$, we
can conclude that  $r\wedge(\exists x)q(x)$. 

Now let us prove the converse. Assume that $r\wedge(\exists x)q(x)$. 
We will prove that $(\exists x)(r\wedge q(x))$. 
Since $r\wedge(\exists x)q(x)$, it follows that  
both $r$ and $(\exists x)q(x)$ hold. Pick $a$ such that 
$q(a)$. Then $r$ and $q(a)$ are true, so $r\wedge q(a)$ is true. 
Therefore  $(\exists x)(r\wedge q(x))$. \hfill{\bf QED}


\bigbreak\noindent{\bf FORMAL PROOF OF THEOREM III:}

\noindent (1.\&)\stetw  Assume $(\exists x)(r\wedge q(x))$. 
\hfill[Preparation to apply Rule 3]

\noindent (2.\&.\&)\stetw Let $a$ be such that $r\wedge q(a)$. 
\hfill[Rule 6, from (1)]

\noindent(3.\&.\&)\stetw $(r\wedge q(a))\imply r$ \hfill [Tautology  
$(\alpha\wedge\beta)\imply\alpha$]

\noindent(4.\&.\&)\stetw $(r\wedge q(a))\imply q(a)$ \hfill [Tautology  
$(\alpha\wedge\beta)\imply\beta$]
 
\noindent(5.\&.\&)\stetw $r$. \hfill[Modus Ponens, from (2) and (3)]

\noindent(6.\&.\&)\stetw $q(a)$. \hfill[Modus Ponens, from (2) and (4)]

\noindent(7.\&.\&)\stetw $(\exists x)q(x)$. \hfill[Rule 7, from (6)]

\noindent(8.\&.\&)\stetw $r\imply((\exists x)q(x)\imply(r\wedge
(\exists x)q(x)))$. \hfill [Tautology $\alpha\imply
(\beta\imply (\alpha\wedge\beta))$]

\noindent(9.\&.\&)\stetw $(\exists x)q(x)\imply(r\wedge (\exists
x)q(x))$.  \hfill [Modus Ponens, from (5) and (8)]

\noindent(10.\&.\&)\stetw $\!\!\!r\wedge (\exists x)q(x)$. \hfill [Modus Ponens,
from (7) and (9)]

\noindent(11.\&)\stetw $\!\!\!r\wedge (\exists x)q(x)$. \hfill[Rule 6, from (2)
and (10)]

\noindent(12)\stetw  $\!\!\!(\exists x)(r\wedge q(x))\imply(r\wedge (\exists
x)q(x))$. \hfill[Rule 3, from (1) and (11)]

\noindent(13.\&)\stetw $\!\!\!{\rm Assume}$  $r\wedge (\exists x)q(x)$. 
\hfill[Preparation to apply Rule 3]

\noindent(14.\&)\stetw $\!\!\!(r\wedge (\exists x)q(x))\imply r$.
\hfill[Tautology $(\alpha\wedge\beta)\imply\alpha$]
 
\noindent(15.\&)\stetw $\!\!\!(r\wedge(\exists x)q(x))\imply (\exists x)q(x)$. 
\hfill[Tautology  $(\alpha\wedge\beta)\imply\beta$]
 
\noindent(16.\&)\stetw $\!\!\!r$. \hfill[Modus Ponens, from (13) and (14)]

\noindent(17.\&)\stetw $\!\!\!(\exists x)q(x)$. \hfill[Modus Ponens, from (13)
and (15)]

\noindent(18.\&.\&)\stetw $\!\!\!{\rm Let}$  $a$ be such that $q(a)$.\hfill
[Rule 6, from (17)]

\noindent(19.\&.\&)\stetw $\!\!\!r\imply (q(a)\imply(r\wedge q(a)))$. \hfill
[Tautology  $\alpha\imply (\beta\imply (\alpha\wedge\beta))$]

\noindent(20.\&.\&)\stetw $\!\!\!q(a)\imply(r\wedge q(a))$. \hfill
[Modus Ponens, from (16) and (19)]

\noindent(21.\&.\&)\stetw $\!\!\!r\wedge q(a)$. \hfill[Modus Ponens, from
(18) and (20)] 

\noindent(22.\&.\&)\stetw $\!\!\!(\exists x)(r\wedge q(x))$. \hfill 
[Rule 7, from (21)]

\noindent(23.\&)\stetw $\!\!\!(\exists x)(r\wedge q(x))$. \hfill 
[Rule 6, from (18) and (22)]

\noindent(24)\stetw $\!\!\!(r\wedge (\exists x)q(x))\imply
(\exists x)(r\wedge q(x))$.  \hfill 
[Rule 3, from (13) and (23)]

\medbreak Now let us write $A$ and $B$ as abbreviations 
for $(\exists x)(r\wedge q(x))$ and $r\wedge (\exists x)q(x)$, respectively. 

\medbreak\noindent(25)\stetw $\!\!\!(A\imply B)\imply((B\imply A)\imply
(A\lto B))$. \hfill[Tautology]

\noindent(26)\stetw $\!\!\!(B\imply A)\imply (A\lto B)$. \hfill [Modus Ponens,
from (12)---which says $A\imply B$---and (25)]


\noindent(27)\stetw $\!\!\!A\lto B$.\hfill[Modus Ponens, from (24)---which says
$B\imply A$---and (26)]

\hfill{\bf QED}


\bigbreak\noindent{\bf INFORMAL PROOF OF THEOREM IV:}  Suppose 
$(\forall x)(r\vee q(x))$. We will prove that $r\vee(\forall x)q(x)$. 
We consider two cases: Case 1 is when $r$ is true, and Case 2 is when $r$
is false. In Case 1, $r$ holds, so $r\vee(\forall x)q(x)$ holds as well. 
Now consider Case 2, that is, suppose $r$ is not true. 
Let $a$ be arbitrary. Since $(\forall x)(r\vee q(x))$, we can conclude that
$r\vee q(a)$. Since $r$ is not true, $q(a)$ must hold. But $a$ is
arbitrary, so $(\forall x)q(x)$ is true, and then 
$r\vee(\forall x)q(x)$ is also true. So we have shown that 
$r\vee(\forall x)q(x)$ holds in both cases. 

Now let us prove the converse. Assume that $r\vee(\forall x)q(x)$. 
We will prove that $(\forall x)(r\vee q(x))$. 
Let $a$ be arbitrary. We want to prove that 
$r\vee q(a)$. Since $r\vee(\forall x)q(x)$, it follows that  
either $r$ or $(\forall x)q(x)$ is true. If $r$ is true, then 
$r\vee q(a)$ is true, and we are done. If 
$(\forall x)q(x)$ is true, then we can specialize and conclude that 
$q(a)$ is true, so $r\vee q(a)$ is true as well. So we 
have shown that $r\vee q(a)$ is true in both cases. Since $a$ was
arbitrary, we have proved that $(\forall x)(r\vee q(x))$. \hfill{\bf QED}

\bigbreak\noindent{\bf FORMAL PROOF OF THEOREM IV:}  

\noindent(1.\&)\stetw Assume  $(\forall x)(r\vee q(x))\,.$ \hfill
[Preparation to apply Rule 3]

\noindent(2.\&.\&)\stetw Assume $\sim r\,.$\hfill [Preparation to apply Rule 3]

\noindent(3.\&.\&.\&)\stetw ${\rm Let}$ $a$ be arbitrary.
\hfill[Preparation to apply Rule 5]

\noindent(4.\&.\&.\&)\stetw $r\vee q(a)\,.$ \hfill[Rule 4, from (1)]

\noindent(5.\&.\&.\&)\stetw $(\sim r)\imply
((r\vee q(a))\imply q(a))\,.$\hfill[Tautology
$(\sim\alpha)\imply((\alpha\vee\beta)\imply\beta)$]

\noindent(6.\&.\&.\&)\stetw $(r\vee q(a))\imply q(a)\,.$\hfill[Modus Ponens from
(2) and (5)]

\noindent(7.\&.\&.\&)\stetw $q(a)\,.$\hfill[Modus Ponens from
(4) and (6)]

\noindent(8.\&.\&)\stetw $(\forall x)q(x)\,.$\hfill[Rule 5, from 
(3) and (7)]

\noindent(9.\&)\stetw $(\sim r)\imply(\forall x)q(x)\,.$\hfill[Rule 3, from 
(2) and (8)]

\noindent(10.\&)\stetw $\!\!\!((\sim r)\imply(\forall x)q(x))
\imply(r\vee(\forall x)q(x))\,.$\hfill[Tautology
$((\sim \alpha)\imply\beta)\imply(\alpha\vee\beta)$]

\noindent(11.\&)\stetw $\!\!\!r\vee(\forall x)q(x)\,.$\hfill[Modus Ponens from 
(9) and (10)]

\noindent(12)\stetw $\!\!\!(\forall x)(r\vee q(x))\imply (r\vee(\forall
x)q(x))\,.$\hfill[Rule 3 from  (1) and (11)]


\noindent(13.\&)\stetw $\!\!\!{\rm Assume}$ $r\vee(\forall x)q(x)\,.$ \hfill
[Preparation to apply Rule 3]

\noindent(14.\&.\&)\stetw $\!\!\!{\rm Let}$ $a$ be arbitrary.
\hfill[Preparation to apply Rule 5]

\noindent(15.\&.\&.\&)\stetw $\!\!\!{\rm Assume}$ $\sim r\,.$\hfill
[Preparation to apply Rule 3] 

\noindent(16.\&.\&.\&)\stetw $\!\!\!(\sim r)\imply
((r\vee(\forall x)q(x))\imply(\forall x)q(x))\,.$\hfill
[Tautology $(\sim\alpha)\imply((\alpha\vee\beta)\imply\beta)$]

\noindent(17.\&.\&.\&)\stetw $\!\!\!(r\vee(\forall x)q(x))\imply(\forall
x)q(x)\,.$\hfill[Modus Ponens from (15) and (16)]

\noindent(18.\&.\&.\&)\stetw $\!\!\!(\forall x)q(x)\,.$\hfill[Modus
Ponens from (11) and (17)] 

\noindent(19.\&.\&.\&)\stetw $\!\!\!q(a)\,.$\hfill[Rule 4, from
(18)]

\noindent(20.\&.\&)\stetw $\!\!\!(\sim r)\imply q(a)\,.$\hfill[Rule 3, from
(15) and (18)]

\noindent(21.\&.\&)\stetw $\!\!\!((\sim r)\imply q(a))
\imply(r\vee q(a))\,.$\hfill[Tautology $((\sim\alpha)\imply\beta)
\imply(\alpha\vee\beta)$]

\noindent(22.\&.\&)\stetw $\!\!\!r\vee q(a)\,.$\hfill[Modus Ponens from 
(2) and (21)]

\noindent(23.\&)\stetw $\!\!\!(\forall x)(r\vee q(x))\,.$\hfill[Rule 5, 
from (14) and (22)]

\noindent(24)\stetw $\!\!\!
(r\vee(\forall x)q(x))\imply(\forall x)(r\vee q(x))\,.$\hfill[Rule 3, 
from (13) and (23)]


\medbreak Now let us write $A$, $B$ as abbreviations for
$(\forall x)(r\vee q(x))$ and $r\vee(\forall x)q(x)$, respectively.

\medbreak\noindent(25)\stetw $\!\!\!(A\imply B)\imply((B\imply A)\imply
(A\lto B))$. \hfill[Tautology]

\noindent(26)\stetw $\!\!\!(B\imply A)\imply (A\lto B)$. \hfill [Modus Ponens,
from (12)---which says $A\imply B$---and (26)]


\noindent(27)\stetw $\!\!\!A\lto B$.\hfill[Modus Ponens, from (24)---which says
$B\imply A$---and (25)]

\hfill{\bf QED}

\sepa

\label{equaxi}
\begin{center}
\fbox{
\begin{minipage}{5in}
\vspace{1mm}
\begin{center}
{\large{\bf AXIOMS FOR EQUALITY}}
\end{center}

\noindent A {\bf predicate calculus with equality} contains the binary 
function symbol $=$. If $t,s$ are terms, We write $t=s$ rather than 
$=(t,s)$. 

The following three {\bf axioms} are automatically adopted in a predicate
calculus with equality.

\bi\bi
\item[{\bf (EQ.1)}] $\qquad(\forall x)(x=x)$.

\item[{\bf (EQ.2)}] $\qquad(\forall x)(\forall y)(x=y\imply y=x)$.

\item[{\bf (EQ.3)}] $\qquad(\forall x)(\forall y)(\forall z)((x=y\wedge
y=z)\imply x=z)$. 
\ei\ei

\vspace{1mm}
\end{minipage}
}
\end{center}

\newpage 

\label{abbrevi}
\begin{center}
{\large{\bf ABBREVIATIONS}}
\end{center}

\noindent Often, we end up writing formnulas that are too long. 
So it is convenient to introduce {\bf abbreviations}. 
For example, suppose we are working with a predicate calculus 
with equality.  We would like to introduce the symbol 
$\neq$ to stand for ``not equal to,'' so that, for example, 
instead of writing ``$\sim 3=5$,'' we would write ``$3\neq 5$.''

One possibility would be to think of $\neq$ as a symbol of the given
language. In that case, if we want $\neq$ to have its true meaning, we
would have to include an {\bf axiom} for it, for example: 
$$
(\forall x)(\forall y)(x\neq y\lto(\sim x=y))\,.
$$
Another possibility would be to think of an expression 
such as $3\neq 5$ as an abbreviation of $\sim 3=5$. With this
interpretation, we would think that $\neq$ is {\bf not} a symbol of our
language, and that when we write $3\neq 5$ this is just a ``name,''
or abbreviation, for the formula $\sim 3=5$.    

We will use the ``axiom'' approach in some cases, and the ``abbreviation''
approach in others. A detailed discussion of these two approaches and 
their pros and cons will be given later. 


\label{twoaabre}
\begin{center}
\fbox{
\begin{minipage}{5in}
\vspace{1mm}
\begin{center}
{\large{\bf THE ABBREVIATIONS $\neq$ and $\exists!$}}
\end{center}
In a first-order predicate calculus with equality, we introduce the
abbreviation $\neq$ to stand for ``not equal to.''  Precisely: 

\medbreak\noindent {\bf ABBR.1:} If $t$ and $s$ are terms, then 
``$t\neq s$'' is an abbreviation of ``$\sim t=s$.'' 

\medbreak\noindent Also, we will use $\exists!$ as an abbreviation for 
``there is one and only one.'' Precisely: 

\medbreak\noindent {\bf ABBR.2:} If $p(x)$ is a formula not containing the
variable $y$, then ``$(\exists !x)p(x)$'' is an abbreviation of 
``$(\exists x)(p(x)\wedge(\forall y)(p(y)\imply y=x))$.'' 

\vspace{1mm}
\end{minipage}
}
\end{center}

\label{usingabre}
\begin{center}
\fbox{
\begin{minipage}{5.3in}
\vspace{1mm}
\begin{center}
{\large{\bf USING ABBREVIATIONS}}
\end{center}
When we have abbreviations, we need {\bf rules} telling us how to work with
them.  There are two such rules: 

\medbreak\noindent
{\bf EXPAND:} If $A$ is an abbreviation for $B$, then we can write 
$B$ wherever we have $A$. 

\medbreak\noindent
{\bf ABBREVIATE:} If $A$ is an abbreviation for $B$, then we can write 
$A$ wherever we have $B$. 

\medbreak\noindent
For example: suppose that at some point we have arrived at

\medbreak\noindent(35) $(\exists x)((x.x=2\wedge x\ge 0)\wedge
(\forall y)((y.y=2\wedge y\ge 0)\imply y=x))\,.$\hfill[$\ldots$]

\medbreak\noindent Then we can write:

\medbreak\noindent(36) $(\exists! x)(x.x=2\wedge x\ge 0)\,.$\hfill[Abbreviate
(35); ABBR.2]  

\medbreak\noindent Conversely, if at some point we have 

\medbreak\noindent(87) $(\exists! x)(x.x=2\wedge x\ge 0)\,,$\hfill[$\ldots$]

\medbreak\noindent then we can write:

\medbreak\noindent(88) $(\exists x)((x.x\!=\!2\wedge x\!\ge\! 0)\wedge
(\forall y)((y.y\!=\!2\wedge y\!\ge\!0)\imply y\!=\!x)).$\hfill[Expand (87); ABBR.2]   

\vspace{1mm}
\end{minipage}
}
\end{center}

\sepa 

\newpage

\begin{center}
{\large{\bf SET THEORY}}\label{setth}
\end{center}

\medbreak\noindent In {\bf Set Theory}, we use a first-order predicate
calculus with equality, containing the binary predicate symbols $=$ and
$\in$ and the reserved constant\footnote{\baselineskip=7pt A {\bf reserved
constant} is a symbol---such as $1$ or $\pi$ or $\emptyset$---that is taken
to be a constant once and for all (so the symbol can {\bf never} be used as
a variable) and has a ``fixed meaning,'' in the sense that a definition or
axiom is adopted that assigns it a meaning that will never change. Reserved
constants can never be used as new constants in the application of Rule 5
and Rule 6.  (For example, as explained before, if we were allowed to take
the expression ``$1+1$'' and call it ``$1$,'' then you would be able to
prove that $1+1=1$, and this would lead to a disaster.)} $\,\emptyset$.

The symbol $\emptyset$ is supposed to denote ``the empty set.''
The symbol $\in$ is thought of as saying ``belongs to,'' and written
between its two arguments.  So we write ``$x\in y$'' rather than
``$\in(x,y)$,'' exactly as in arithmetic we write ``$x<y$'' rather than
``$<(x,y)$.'' Naturally, the $=$ symbol is also written in the middle. 
The three axioms for equality hold.

\medbreak In addition, the language of Set Theory contains the 
expression ``$\{\ldots\}\,,$'' used to introduce new sets. So, for example,
if $p(x)$ is a one-variable predicate, then 
$\{x:p(x)\}$ stands for ``the set of all $x$ for which $p(x)$ is true.''

This creates some minor difficulties. For example, the introduction of the
``$\{\ldots\}$'' notation would mean that {\bf we are no longer dealing with a
first-order predicate calculus.} (Reason: in a first-order predicate
calculus, we combine individuals\footnote{\baselineskip=7pt
An ``individual symbol,''  or ``individual,'' for short, is a 
symbol, usually a letter, that is either a variable or a constant. 
For example, $3$ is an individual symbol in arithmetic,
$\emptyset$ is an individual symbol in Set Theory, 
the letter $x$ is an individual symbol in the formula 
$(\forall x)(x.x\ge 0)$ and in the formula $x.x\ge 0$. In the former case,
i.e. in $(\forall x)(x.x\ge 0)$, $x$ is 
a variable. In the latter case, i.e. for $x.x\ge 0$,
if such a formula ever shows up in a
proof, then $x$ will have to have been declared to be a constant earlier,
e.g. by saying something like ``let $x$ be arbitrary'' or 
``let $x$ be such that $x>0$,'' or ``let $x=5$'' (which is just an
alternative way of saying ``let $x$ be such that $x=5$'').}
and function symbols to make {\bf terms}, and then we combine terms to make
{\bf formulas}, but we never ``go back'' and use formulas to make terms. In
Set Theory, with the ``$\{\ldots\}$'' notation, we can use individuals and
function symbols to make terms, then terms can be used to make formulas,
but then we can make bigger terms from the formulas. For example, we can
use the individual letter $x$ as a term, then this term can be used in
formulas, e.g. $x=x$ and $\sim x=x$, and then from these formulas we can
make the ``terms'' $\{x:x=x\}$ and $\{x:\sim x=x\}$.)

To avoid these problems, we will treat all expressions involving
``$\{\ldots\}$'' as just abbreviations of expressions in the first-order 
predicate calculus with $=$ and $\in$ but {\bf without}
``$\{\ldots\}$.'' This means that:

\label{abbbraces}
\begin{center}
\fbox{
\begin{minipage}{5in}
\vspace{1mm}
\begin{center}
{\large{\bf THE ABBREVIATION ``$\{\ldots\}$''}}
\end{center}

{\bf ABBR.3:} If, $x$ is a variable, $p(x)$ is a formula not containing
quantifiers  in $x$, and $t$ is a term not containing $x$, then the
equality  
$$
t=\{x:p(x)\}
$$
is an alternative way of writing 
$$
(\forall x)(x\in t\lto p(x))\,.
$$
\end{minipage}
}
\end{center}

\medbreak\noindent Moreover, we will only introduce the 
``$\{\ldots\}$'' notation in one way, namely, by means of equalities such as 
$a=\{x:p(x)\}$. This means that {\bf every formula involving 
``$\{\ldots\}$''-expressions can be rewritten as a formula without 
the ``$\{\ldots\}$s.''  In this way, the formulas of Set Theory 
``really'' do not have any ``$\{\ldots\}$s'' at all, so they are {\it bona
fide} formulas of a first-order predicate calculus.}

\medbreak Here are the basic axioms of ``Na\"\i{}ve'' Set Theory:

\label{axnaive}
\begin{center}
\fbox{
\begin{minipage}{5in}
\vspace{1mm}
\begin{center}
{\large{\bf THE AXIOMS\footnote{\baselineskip=7pt NOTE: 
A completely precise statement of  Axiom-scheme NST.1 
needs {\sl formulas with parameters}, as will be explained
later, when we introduce {\sl Axiomatic Set
Theory.}} OF NA\"IVE SET THEORY}}
\end{center}

\medbreak\noindent AXIOM-SCHEME\footnote{\baselineskip=7pt 
Why do we call this an
``axiom-scheme'' rather than an ``axiom''?  Because an axiom is supposed to
be a fixed formula, and NST.1 is not a fixed formula. It is a 
collection of formulas, one for each choice of $p(x)$. For example,
NST.1 tells us that $(\exists S)(S=\{x:x=x\})$ is an axiom, 
that  $(\exists S)(S=\{x:x\in x\})$ is an axiom, 
that  $(\exists S)(S=\{x:\sim x\in x\})$ is an axiom, 
that  $(\exists S)(S=\{x:\emptyset\in x\})$ is an axiom, 
that  $(\exists S)(S=\{x:(\forall y)(\emptyset\in y\imply y\in x)\})$ is an
axiom,  and so on.  So for each $p(x)$ NST.1 gives us an axiom. 
So NST.1 is a {\sl procedure---or ``scheme''--for generating axioms} rather
than a single axiom.} NST.1: If 
$p(x)$ is any formula containing the
variable $x$, no quantifiers involving $x$, and no other free variable,
and $S$ is a variable that does not occur in $p(x)$, then 
then $(\exists S)(S=\{x:p(x)\})$ is an axiom. 

\medbreak 
AXIOM NST.2: $(\forall S)(\forall T)(S=T\lto(\forall x)(x\in
S\lto x\in T))\,.$ 

\medbreak AXIOM-DEFINITION NST.3: $\emptyset=\{x:\sim x=x\}\,.$

\vspace{1mm}
\end{minipage}
}
\end{center}

\sepa

\begin{center}

{\large{\bf SOME SET-THEORY DEFINITIONS}}\label{setdefs}
\end{center}

\noindent In addition to the basic symbols $\emptyset$, $\in$ and $=$, we
also want to use some other symbols, such as:

\bi
\item{} the two-argument function symbols $\cup$, $\cap$,
$-$ and $\Delta$  (union, intersection, set difference and 
symmetric difference); these symbols are written between 
the two arguments, so we write $A\cup B$, $A\cap B$, $A-B$, $A\Delta B$
rather than $\cup(A,B)$, $\cap(A,B)$, $-(A,B)$, 
$\Delta(A,B)$; we read $A\cup B$ as ``$A$ union $B$,''
$A\cap B$ as ``$A$ intersection $B$,'' $A-B$ as ``$A$ minus $B$,'' and
$A\Delta B$ as ``$A$ symmetric difference $B$,'' or 
``the symmetric difference of $A$ and $B$;'' 

\item{} the one-argument function symbols ${\cal P}$ and
$\widetilde{\,\,}$ (set of subsets of, and complement of); the ``complement''
symbol is written {\sl on top} of the argument, so we write
$\widetilde{A}$ rather than $\widetilde{\,\,}(A)$;

\item{} the two-argument predicate  symbol $\subseteq$ (subset of),
written between its two arguments, so that we write 
$A\subseteq B$ (and read ``$A$ is a subset of $B$'') instead
of writing $\subseteq(A,B)$.
\ei

The basic axioms only talk about $\emptyset$, $=$ and $\in$, so using these
axioms alone we would have no idea of what $\cup$, $\cap$, etc. mean, and
we would not be able to prove anything involving these new symbols. This
means that we need, in addition, statements involving the new symbols so we
can prove things about them. You can think of these statements as new
axioms---giving us the basic properties of $\cup$, $\cap$, etc.---or as
definitions, telling us what $\cup$, $\cap$, etc. mean.

\bigbreak\noindent{\bf AXIOM-DEFINITION NST.AD.1} (union): 
\fbox{$(\forall A)(\forall B)(A\cup B=\{x:x\in A\vee x\in B\})$. }

\medbreak\noindent{\bf INFORMAL VERSION OF THE DEFINITION OF ``UNION'':}
If $A$, $B$ are sets, then the {\bf union} of $A$ and $B$ is the set 
$A\cup B$ given by $A\cup B=\{x:x\in A\vee x\in B\}$. 

\bigbreak\noindent{\bf AXIOM-DEFINITION NST.AD.2} (intersection): 
\fbox{$(\forall A)(\forall B)(A\cap B\!=\!\{x:x\!\in\!A\wedge x\!\in\!B\})$.}

\medbreak\noindent{\bf INFORMAL VERSION OF THE DEFINITION OF ``INTERSECTION'':}
If $A$, $B$ are sets, then the {\bf intersection} of $A$ and $B$ is the set 
$A\cap B$ given by $A\cap B=\{x:x\in A\wedge x\in B\}$. 

\bigbreak\noindent{\bf AXIOM-DEFINITION NST.AD.3} (set inclusion): 

\fbox{$(\forall A)(\forall B)(A\subseteq B\lto(\forall x)(x\in A\imply x\in
B))$.} 

\medbreak\noindent{\bf INFORMAL VERSION OF THE DEFINITION OF ``INCLUSION'':}
If $A$, $B$ are sets, then we say that $A$ is a {\bf subset} of $B$ 
if, whenever $x$ belongs to $A$, it follows that $x$ belongs to $B$. 

\bigbreak\noindent{\bf AXIOM-DEFINITION NST.AD.4} (the ``power set''---or
set of subsets---of a set):

\fbox{$(\forall A)({\cal P}(A)=\{X:X\subseteq A\})$.}

\medbreak\noindent{\bf INFORMAL VERSION OF THE DEFINITION OF ``POWER SET'':}
The {\bf power set} of a set $A$ is the set ${\cal P}(A)$ of all subsets of
$A$. 

\bigbreak\noindent{\bf AXIOM-DEFINITION NST.AD.5} (the complement of a set): 
\fbox{$(\forall A)(\widetilde{A}=\{x:\sim x\in A\})$.}   

\medbreak\noindent{\bf INFORMAL VERSION OF THE DEFINITION OF ``COMPLEMENT'':}
The {\bf complement} of a set $A$ is the set of all things that do not
belong to $A$. 

\bigbreak\noindent{\bf AXIOM-DEFINITION NST.AD.6} (set difference):

\fbox{$(\forall A)(\forall B)(A-B=\{x:x\in A\wedge(\sim x\in B)\})$.}

\medbreak\noindent{\bf INFORMAL VERSION OF THE DEFINITION OF ``SET
DIFFERENCE'':} The {\bf difference} of two sets $A$, $B$ is the set 
$A-B$ of all things that belong to $A$ but do not belong to $B$. 

\bigbreak\noindent{\bf AXIOM-DEFINITION NST.AD.7} (symmetric difference):

\fbox{$(\forall A)(\forall B)(A\,\Delta\,B=(A-B)\cup(B-A))$.}

\medbreak\noindent{\bf INFORMAL \ VERSION \ OF \ THE \ DEFINITION \ OF \
``SYMMETRIC DIFFERENCE'':} The {\bf symmetric difference} of two sets $A$,
$B$ is the set  $A\,\Delta\,B$ of all things that belong to one of the sets but do not
belong to both of them. 

\bigbreak\noindent{\bf COMMENTS}: 

\bi
\item{} You will often find in books the statement that
``the definition of equality of sets is that two sets $S$ and $T$ are {\bf
equal} if $(\forall x)(x\in S\lto x\in T)$.''  We are taking this
``definition'' to be an {\bf axiom} instead but, as was explained earlier,
this is not much of a distinction, because axioms and definitions function
exactly the same way in proofs, so one cannot really tell a definition from
an axiom.

\item{} A more serious problem is the following: shouldn't we have said in
Axiom NST.2 that $S=T\lto(\forall x)(x\in S\lto x\in T)$ {\it if $S$ and
$T$ are sets}?  If $S$ and $T$ are not sets, then presumably $S$ and $T$
can have the same members without being the same things. For example: I am
not a set, so nothing belongs to me in the set-theory sense. If we let
$\emptyset$ denote the empty set, and use $S$ to denote me, then $(\forall
x)(x\in S\lto x\in \emptyset)$ is true.  (Proof: let $x$ be arbitrary. Then
$\sim x\in S$, because nothing belongs to me in the set-theory sense.
Also, $\sim x\in\emptyset$, because nothing belongs to the empty set. So
both $x\in S$ and $x\in\emptyset$ are false, and therefore the equivalence
$x\in S\lto x\in \emptyset$ is true. Since $x$ was arbitrary, $(\forall
x)(x\in S\lto x\in \emptyset)$ is true.)  Does this mean that I am the
empty set?  I would very much want to believe that the answer is ``no,''
but in that case it seems that we have contradicted Set Axiom NST.2.

\item{} The reason that we stated the axiom as we did is that we want to
think of set theory as being {\sl just about sets}, which means that we
want to interpret it in a universe of discourse where {\bf everything is a
set}. So, when I write $(\forall S)\ldots$ in set theory, this
automatically means ``for all sets $S$ $\ldots$''.

\item{} At this point, you will obviously come up with the following
powerful objection: we definitely {\bf do} want to use sets to study things
other than sets, for example, numbers.  We want to talk about sets of real
numbers, such as, for example, intervals.  So not everything is a set, even
in Mathematics, because there are other things such as, for example,
numbers and functions.

\item{} This objection will be taken care of later, in two ways:

\bi
\item{} First, we will discuss at a later point a ``hybrid'' set theory in
which there are sets and there are also other things. In that theory, some
variables will take values over sets, and some other variables will take
non-set values, such as numbers. When we develop the ``hybrid'' theory, we
will have to be careful to make sure that Set Axiom NST.2 is stated so as to
apply only to sets $S$ and $T$.

\item{} The second way is harder to describe right now, but happens to be
much nicer. Mathematicians have managed to construct a ``mathematical
universe'' in which {\bf there is nothing other than sets.}  In this
universe, numbers and functions are just special kinds of sets. (For
example, the number $0$ is the empty set, the number $1$ is the one-element
set whose only member is the empty set, that is, $1=\{\emptyset\}$, the
number $2$ is the two-element set whose members are $0$ and $1$, the number
$3$ is the three-element set whose members are $0$, $1$, and $2$, and so
on.  One can easily obtain $0$ and all the natural numbers this way. To get
the other integers, such as $-1$, $-2$, and so on, and all the rational
numbers, as special sets, is also possible, though a bit more work is
required.  Finally, one can get the real numbers, functions, and everything
else.)  Once we reach this point, you will see that in Mathematics we can
always work with {\bf just sets and nothing but sets, because it's all sets
and there is nothing else.}

\ei\ei

\sepa

\begin{center}
{\large{\bf EXAMPLES  OF SET-THEORY PROOFS}}\label{exaset}
\end{center}

\medbreak\noindent{\bf THEOREM 1:}  $(\forall A)(\emptyset\subseteq A)$. 

\medbreak\noindent{\bf INFORMAL STATEMENT OF THEOREM 1:}  If $A$ is a 
set, then the empty set is a subset of $A$. 

\medbreak\noindent{\bf INFORMAL PROOF:}  Let $A$ be an arbitrary set.
We want to prove that $\emptyset\subseteq A$, i.e. that 
whenever $x\in\emptyset$ it follows that $x\in A$. Let $a$ be arbitrary. 
Assume $a\in\emptyset$. Since $\emptyset$ is, by definition, the set of
those $x$ such that $\sim x=x$, the fact that $a\in\emptyset$
implies $\sim a=a$. But $x=x$ for all $x$ by Axiom Eq.1,  so in particular
$a=a$. So we have shown that $\sim a=a$ and $a=a$. So we have the
contradiction $(\sim a=a)\wedge a=a$. From this anything follows, in
particular $a\in A$. So assuming that $a\in\emptyset$ we got $a\in
A$. Since $a$ was arbitrary, this implies the desired conclusion 
$\emptyset\subseteq A$. \ \ {\bf QED}

\medbreak\noindent{\bf FORMAL PROOF:}  

{\parindent=0pt

(1) \stetw $(\forall X)(\forall Y)(X\subseteq Y\lto(\forall x)(x\in X\imply
x\in Y))\,.$\hfill[Axiom-Definition NST.AD.3]

(2) \stetw $(\forall Y)(\emptyset\subseteq Y\lto(\forall x)(x\in\emptyset\imply
x\in Y))\,.$\hfill[Rule 4, from (1)]

(3.\&) \stetw Let $\bar A$ be arbitrary.\hfill[Preparation to apply Rule 5] 

(4.\&) \stetw $\emptyset\subseteq \bar A\lto(\forall x)(x\in\emptyset\imply
x\in \bar A)\,.$\hfill[Rule 4, from (2)]

(5.\&.\&) \stetw Let $a$ be arbitrary.\hfill[Preparation to apply Rule 5] 

(6.\&.\&.\&) \stetw Assume $a\in\emptyset\,.$\hfill[Preparation to apply
Rule 3]  

(7.\&.\&.\&) \stetw $\emptyset=\{x:\sim x=x\}\,.$\hfill[Axiom-definition
NST.3]

(8.\&.\&.\&) \stetw $(\forall x)(x\in \emptyset\lto\sim
x=x)\,.$\hfill[Expand (7) using ABBR.3] 

(9.\&.\&.\&) \stetw $a\in \emptyset\lto(\sim a=a)\,.$\hfill[Rule 4, from (8)]

(10.\&.\&.\&) \stetw $\!\!\!(a\in \emptyset\lto(\sim a=a))\imply
(a\in\emptyset\imply(\sim a=a))\,.$

\hfill[Tautology $(\alpha\lto\beta)\imply(\alpha\imply\beta)$]

(11.\&.\&.\&) \stetw $\!\!\!a\in\emptyset\imply(\sim a=a)\,.$\hfill
[Modus Ponens from (9) and (10)]

(12.\&.\&.\&) \stetw $\!\!\!\sim a=a\,.$\hfill
[Modus Ponens from (6) and (11)]

(13.\&.\&.\&) \stetw $\!\!\!(\forall x)(x=x)\,.$\hfill
[Axiom Eq.1]

(14.\&.\&.\&) \stetw $\!\!\!a=a\,.$\hfill[Rule 4, from (13)] 

(15.\&.\&.\&) \stetw $\!\!\!a=a\imply((\sim a=a)\imply a\in \bar
A)\,.$

\hfill[Tautology $\alpha\imply((\sim\alpha)\imply\beta)$]

(16.\&.\&.\&) \stetw $\!\!\!(\sim a=a)\imply a\in \bar
A\,.$\hfill[Modus Ponens from (14) and (15)]

(17.\&.\&.\&) \stetw $\!\!\!a\in \bar A\,.$\hfill[Modus Ponens from 
(12) and (16)]

(18.\&.\&) \stetw $\!\!\!a\in\emptyset\imply a\in \bar A\,.$\hfill[Rule 
3 from (6) and (17)]

(19.\&) \stetw $\!\!\!(\forall x)(x\in\emptyset\imply x\in \bar
A)\,.$\hfill[Rule  4 from (5) and (18)]

(20.\&) \stetw $\!\!\!(\emptyset\subseteq \bar A\lto
(\forall x)(x\in\emptyset\imply x\in \bar A))\imply
((\forall x)(x\in\emptyset\imply x\in \bar A)\imply
\emptyset\subseteq \bar A)\,.$

\hfill[Tautology $(\alpha\lto\beta)\imply(\beta\imply\alpha)$]

(21.\&) \stetw $\!\!\!(\forall x)(x\in\emptyset\imply x\in \bar A)\imply
\emptyset\subseteq \bar A\,.$
\hfill[Modus Ponens from (4) and (20)]

(22.\&) \stetw $\!\!\!\emptyset\subseteq \bar A\,.$
\hfill[Modus Ponens from (19) and (21)]

(23) \stetw $\!\!\!(\forall A)(\emptyset\subseteq A)\,.$
\hfill[Rule 5, from (3)and (22)]

\hfill{\bf QED} 


}




\medbreak\noindent{\bf THEOREM 2:}  
$(\forall A)(\forall B)(A\subseteq A\cup B)$. 

\medbreak\noindent{\bf INFORMAL STATEMENT OF THEOREM 2:}  If $A$ and $B$
are sets, then $A$ is a subset of the union of $A$ and $B$. 

\medbreak\noindent{\bf INFORMAL PROOF:}  Let $A$, $B$ be arbitrary sets.
We want to prove that $A\subseteq A\cup B$, i.e. that 
whenever $x\in A$ it follows that $x\in A\cup B$. Let $a$ be arbitrary. 
Assume $a\in A$. Then $a\in A\vee a\in B$. Since $A\cup B$ is, by
definition, the set of those $x$ such that $x\in A\vee x\in B$, the fact
that $a\in A\vee a\in B$  implies $a\in A\cup B$. 
So we have shown that $a\in A\imply a\in A\cup B$. 
Since $a$ was arbitrary, this implies the desired conclusion
that $(\forall x)(x\in A\imply x\in A\cup B)$.\ \ {\bf QED}

\medbreak\noindent{\bf FORMAL PROOF:}  

{\parindent=0pt

(1) \stetw $(\forall X)(\forall Y)(X\subseteq Y\lto(\forall x)(x\in X\imply
x\in Y))\,.$\hfill[Axiom-Definition NST.AD.3]

(2) \stetw $(\forall X)(\forall Y)(X\cup Y=\{x:x\in X\vee x\in Y\})\,.$
\hfill[Axiom-Definition NST.AD.1]

(3.\&) \stetw Let $\bar A$ be arbitrary.\hfill[Preparation to apply Rule 5]

(4.\&.\&) \stetw Let $\bar B$ be arbitrary.\hfill[Preparation to apply Rule 5]

(5.\&.\&) \stetw $(\forall Y)(\bar A\cup Y=\{x:x\in\bar A\vee x\in Y\})\,.$
\hfill[Rule 4, from (2)]

(6.\&.\&) \stetw $\bar A\cup\bar  B=\{x:x\in\bar A\vee x\in\bar
B\}\,.$\hfill[Rule 4, from (5)] 

(7.\&.\&) \stetw $(\exists S)(S=\{x:x\in\bar A\vee x\in\bar
B\})\,.$\hfill[Set Axiom  NST.1]

(8.\&.\&.\&) \stetw Let $C$ be such that $C=\{x:x\in\bar A\vee x\in
\bar B\}\,.$\hfill[From (7), prep. for Rule 6]

(9.\&.\&.\&) \stetw $C=\bar A\cup\bar B\,.$\hfill[Rule 8, from (6) and (8)]

(10.\&.\&.\&) \stetw $\!\!\!(\forall Y)(\bar A\subseteq Y\lto(\forall
x)(x\in\bar A\imply x\in Y))\,.$\hfill[Rule 4, from (1)]

(11.\&.\&.\&) \stetw $\!\!\!\bar A\subseteq C\lto(\forall x)(x\in\bar
A\imply x\in C)\,.$\hfill[Rule 4, from (10)]

(12.\&.\&.\&) \stetw $\!\!\!\bar A\subseteq\bar A\cup\bar B\lto
(\forall x)(x\in\bar A\imply x\in\bar A\cup\bar B)\,.$\hfill
[Rule 8, from (9) and (11)]

(13.\&.\&) \stetw $\!\!\!\bar A\subseteq\bar A\cup\bar B\lto
(\forall x)(x\in\bar A\imply x\in\bar A\cup\bar B)\,.$\hfill
[Rule 6, from (8) and (12)]

(14.\&.\&.\&) \stetw $\!\!\!{\rm Let}$ $a$ be
arbitrary.\hfill[Preparation to apply Rule 5]

(15.\&.\&.\&.\&) \stetw $\!\!\!{\rm Assume}$ $a\in\bar A\,.$ 
\hfill[Preparation to apply Rule 3]

(16.\&.\&.\&.\&) \stetw $\!\!\!a\in\bar A\imply(a\in\bar A\vee a\in\bar
B)\,.$ \hfill[Tautology $\alpha\imply(\alpha\vee\beta)$]

(17.\&.\&.\&.\&) \stetw $\!\!\!a\in\bar A\vee a\in\bar B\,.$
\hfill[Modus Ponens from (15) and (16)]

(18.\&.\&.\&.\&) \stetw $\!\!\!(\forall x)(x\in\bar A\cup\bar
B\lto(x\in\bar A\vee x\in\bar B))\,.$\hfill[Expand (6) using ABBR.3] 

(19.\&.\&.\&.\&) \stetw $\!\!\!a\in\bar A\cup\bar B\lto(a\in\bar A\vee
a\in\bar B)\,.$ \hfill[Rule 4, from (18)] 

(20.\&.\&.\&.\&) \stetw $\!\!\!(a\in\bar A\vee a\in\bar B)\imply
((a\in\bar A\cup\bar B\lto(a\in\bar A\vee a\in\bar B))\imply a\in\bar
A\cup\bar  B)\,.$ 

\hfill[Tautology $\alpha\imply((\beta\lto\alpha)\imply\beta)$]

(21.\&.\&.\&.\&) \stetw $\!\!\!(a\in\bar A\cup\bar B\lto(a\in\bar A\vee
a\in\bar B))\imply a\in\bar A\cup\bar B\,.$

\hfill[Modus Ponens from (17) and (20)]

(22.\&.\&.\&.\&) \stetw $\!\!\!a\in\bar A\cup\bar B\,.$\hfill[ModusPonens
from (19) and (21)] 

(23.\&.\&.\&) \stetw $\!\!\!a\in\bar A\imply a\in\bar A\cup\bar
B\,.$\hfill[Rule 3, from (15) and (22)] 

(24.\&.\&) \stetw $\!\!\!(\forall x)(x\in\bar A\imply x\in\bar
A\cup\bar B)\,.$\hfill[Rule 5, from  (14) and (23)]

(25.\&.\&) \stetw $\!\!\!(\bar A\subseteq\bar A\cup\bar B\lto
(\forall x)(x\in\bar A\imply x\in\bar A\cup\bar B))$

$\qquad\qquad\qquad
\imply((\forall x)(x\in\bar A\imply x\in\bar A\cup\bar B)\imply
\bar A\subseteq\bar A\cup\bar B)\,.$
\hfill[Tautology $(\alpha\lto\beta)\imply(\beta\imply\alpha)$]

(26.\&.\&) \stetw $\!\!\!(\forall x)(x\in\bar A\imply x\in\bar A\cup\bar
B)\imply \bar A\subseteq\bar A\cup\bar B\,.$
\hfill[Modus Ponens from (13) and (25)]

(27.\&.\&) \stetw $\!\!\!\bar A\subseteq\bar A\cup\bar B\,.$
\hfill[Modus Ponens from (24) and (26)]

(28.\&) \stetw $\!\!\!(\forall B)(\bar A\subseteq\bar A\cup B)\,.$
\hfill[Rule 5, from (4) and (27)]

(29) \stetw $\!\!\!(\forall A)(\forall B)(A\subseteq A\cup B)\,.$
\hfill[Rule 5, from (3) and (28)]

\hfill{\bf QED}

}


\medbreak\noindent{\bf THEOREM 3:}  
$(\forall A)(\forall B)(A\subseteq B\lto A=A\cap B)$. 

\medbreak\noindent{\bf INFORMAL STATEMENT OF THEOREM 3:}  If $A$ and $B$
are sets, then $A\subseteq B$ if and only if $A=A\cap B$.

\medbreak\noindent{\bf INFORMAL PROOF:}  Let $A$, $B$ be arbitrary sets.
Assume that $A\subseteq B$. We want to prove that $A=A\cap B$. 
Let $a\in A$. Then $a\in B$ as well, because $A\subseteq B$. So
$a\in A\cap B$. Conversely, assume $a\in A\cap B$. Then 
$a\in A$ and $a\in B$. In particular, $a\in A$. So we have shown that 
$a\in A$ implies $a\in A\cap B$ and $a\in A\cap B$ implies $a\in A$. 
Therefore $a\in A\lto a\in A\cap B$. Since $a$ was arbitrary, 
$A=A\cap B$. 

We now prove the converse, that is, we assume that $A=A\cap B$ and prove
that $A\subseteq B$. Let $a\in A$. Then $a\in A\cap B$, because 
$A=A\cap B$. So $a\in A$ and $a\in B$. In particular, $a\in B$. So we have
shown that $a\in A\imply a\in B$. Sicne $a$ was arbitrary, 
$a\subseteq B$, as desired.\ \ {\bf QED}

\medbreak\noindent{\bf FORMAL PROOF:}  

{\parindent=0pt

(1) \stetw $(\forall X)(\forall Y)(X\cap Y=\{x:x\in X\wedge x\in Y\})\,.$ 
\hfill[Axiom-definition NST.AD.2]

(2) \stetw $(\forall X)(\forall Y)(X\subseteq Y\lto(\forall x)(x\in X\imply
x\in Y))\,.$  \hfill[Axiom-definition NST.AD.3]

(3) \stetw $(\forall S)(\forall T)(S=T\lto(\forall x)(x\in S\lto
x\in T))\,.$  \hfill[Set Axiom NST.2]

(4.\&) \stetw Let $\bar A$ be arbitrary.\hfill[Preparation to apply Rule 5]

(5.\&.\&) \stetw Let $\bar B$ be arbitrary.\hfill[Preparation to apply Rule 5]

(6.\&.\&) \stetw $(\forall Y)(\bar A\subseteq Y\lto(\forall x)(x\in\bar A\imply
x\in Y))\,.$  \hfill[Rule 4, from (2)] 

(7.\&.\&) \stetw $\bar A\subseteq\bar B\lto(\forall x)(x\in\bar A\imply
x\in\bar B)\,.$  \hfill[Rule 4, from (6)] 

(8.\&.\&) \stetw $(\forall Y)(\bar A\cap Y=\{x:x\in\bar A\wedge x\in Y\})\,.$ 
\hfill[Rule 4, from (1)] 

(9.\&.\&) \stetw $\bar A\cap\bar B=\{x:x\in\bar A\wedge x\in\bar B\}\,.$ 
\hfill[Rule 4, from (8)] 

(10.\&.\&) \stetw $\!\!\!(\exists S)(S=\{x:x\in\bar A\wedge x\in\bar B\})\,.$ 
\hfill[Set Axiom NST.1] 

(11.\&.\&.\&) \stetw $\!\!\!{\rm Let}$ $C$ be such that 
$C=\{x:x\in\bar A\wedge x\in\bar B\}\,.$ \hfill
[From (10), prep. for Rule 6]

(12.\&.\&.\&) \stetw $\!\!\!C=\bar A\cap\bar B\,.$\hfill
[Rule 8, from (9) and (11)]

(13.\&.\&.\&) \stetw $\!\!\!(\forall T)(\bar A=T\lto(\forall x)(x\in\bar A\lto
x\in T))\,.$  \hfill[Rule 4, from (3)]

(14.\&.\&.\&) \stetw $\!\!\!\bar A=C\lto(\forall x)(x\in\bar A\lto
x\in C)\,.$  \hfill[Rule 4, from (13)]

(15.\&.\&.\&) \stetw $\!\!\!\bar A=\bar A\cap\bar B\lto(\forall
x)(x\in\bar A\lto x\in \bar A\cap\bar B)\,.$  \hfill[Rule 8, from (12) and
(14)]  

(16.\&.\&.\&) \stetw $\!\!\!(\forall x)(x\in\bar A\cap\bar
B\lto(x\in\bar A\wedge x\in\bar B))\,.$\hfill[Expand (9) using ABBR.3]  

(17.\&.\&.\&.\&) \stetw $\!\!\!{\rm Assume}$ 
$(\forall x)(x\in\bar A\lto x\in\bar A\cap\bar B)\,.$  \hfill[Preparation
to apply Rule 3] 

(18.\&.\&.\&.\&.\&) \stetw $\!\!\!{\rm Let}$ $a$ be arbitrary.
\hfill[Preparation to apply Rule 5]

(19.\&.\&.\&.\&.\&) \stetw $\!\!\!
a\in\bar A\lto a\in\bar A\cap\bar B\,.$  \hfill[Rule 4, from (17)]

(20.\&.\&.\&.\&.\&) \stetw $\!\!\!
a\in\bar A\cap\bar B\lto(a\in\bar A\!\wedge\!a\in\bar B)\,.$\hfill[Rule 4,
from (16)]  

(21.\&.\&.\&.\&.\&) \stetw $\!\!\!
(a\in\bar A\lto a\in\bar A\cap\bar B)$

$\qquad\qquad\qquad\qquad\qquad
\imply((a\in\bar A\cap\bar B\lto(a\in\bar A\!\wedge\!a\in\bar
B)) \imply(a\in\bar A\imply a\in\bar B))\,.$

\hfill[Tautology
$(\alpha\lto\beta)\imply((\beta\lto(\gamma\wedge\delta)\imply
(\alpha\imply\delta))$]

(22.\&.\&.\&.\&.\&) \stetw $\!\!\!
(a\in\bar A\cap\bar B\lto(a\in\bar A\!\wedge\!a\in\bar
B)) \imply(a\in\bar A\imply a\in\bar B)\,.$

\hfill[Modus Ponens from (19) and (21)]

(23.\&.\&.\&.\&.\&) \stetw $\!\!\!
a\in\bar A\imply a\in\bar B\,.$
\hfill[Modus Ponens from (20) and (22)]

(24.\&.\&.\&.\&) \stetw $\!\!\!
(\forall x)(x\in\bar A\imply x\in\bar B)\,.$\hfill[Rule 5, from (18) and (23)]

(25.\&.\&.\&) \stetw $\!\!\!
(\forall x)(x\!\in\!\bar A\!\lto\!x\!\in\!\bar A\!\cap\!\bar B)\!\imply\!
(\forall x)(x\!\in\!\bar A\!\imply\! x\!\in\!\bar B)\,.$\hfill[Rule 3, from
(17) and (24)] 

(26.\&.\&.\&.\&) \stetw $\!\!\!{\rm Assume}$
$(\forall x)(x\in\bar A\imply x\in\bar B)\,.$\hfill[Preparation to apply
Rule 3]

(27.\&.\&.\&.\&.\&) \stetw $\!\!\!{\rm Let}$ $a$ be arbitrary.
\hfill[Preparation to apply Rule 5]

(28.\&.\&.\&.\&.\&) \stetw $\!\!\!a\in\bar A\imply a\in\bar B\,.$\hfill
[Rule 4, from (26)]

(29.\&.\&.\&.\&.\&) \stetw $\!\!\!(a\in\bar A\imply a\in\bar B)
\imply(a\in\bar A\lto(a\in\bar A\wedge a\in\bar B))\,.$

\hfill[Tautology $(\alpha\imply\beta)\imply(\alpha\lto(\alpha\wedge\beta))$]

(30.\&.\&.\&.\&.\&) \stetw $\!\!\!
a\in\bar A\lto(a\in\bar A\wedge a\in\bar B)\,.$\hfill
[Modus Ponens from (28) and (29)]  

(31.\&.\&.\&.\&.\&) \stetw $\!\!\!a\in\bar A\cap\bar B\lto(a\in\bar A
\wedge a\in\bar B)\,.$\hfill[Rule 4, from (16)]

(32.\&.\&.\&.\&.\&) \stetw $\!\!\!(a\in\bar A\cap\bar B\lto(a\in\bar A
\wedge a\in\bar B))$

$\qquad\qquad\qquad\qquad\qquad\qquad\imply
((a\in\bar A\lto(a\in\bar A\wedge a\in\bar B))
\imply(a\in\bar A\lto a\in\bar A\cap\bar B))\,.$

\hfill[Tautology
$(\alpha\lto\beta)\imply((\gamma\lto\beta)\imply(\gamma\lto\alpha))$]

(33.\&.\&.\&.\&.\&) \stetw $\!\!\!(a\in\bar A\lto(a\in\bar
A\wedge a\in\bar B)) 
\imply(a\in\bar A\lto a\in\bar A\cap\bar B)\,.$

\hfill[Modus Ponens from (31) and (32)]

(34.\&.\&.\&.\&.\&) \stetw $\!\!\!a\in\bar A\lto a\in\bar A\cap\bar B\,.$
\hfill[Modus Ponens from (30) and (33)]

(35.\&.\&.\&.\&) \stetw $\!\!\!(\forall x)(x\in\bar A\lto x\in\bar A\cap\bar
B)\,.$\hfill[Rule 5, from (27) and (34)]

(36.\&.\&.\&) \stetw $\!\!\!
(\forall x)(x\!\in\!\bar A\!\imply\!x\!\in\!\bar B)\!\imply\!
(\forall x)(x\!\in\!\bar A\!\lto\!x\!\in\!\bar A\!\cap\!\bar
B)\,.$\hfill[Rule 3, from (26) and (35)]

\medbreak
Now use $P$ as an abbreviation for $(\forall x)(x\in\bar A\imply x\in\bar
B)$ and use $Q$ as an abbreviation for $(\forall x)(x\in\bar A\lto x\in\bar
A\cap\bar B)$.

\medbreak

(37.\&.\&.\&) \stetw $\!\!\!(P\imply Q)\imply((Q\imply P)\imply(P\lto Q))\,.$
\hfill[Tautology] 

(38.\&.\&.\&) \stetw $\!\!\!(Q\imply P)\imply(P\lto Q)\,.$\hfill[Modus
Ponens from  (36) and (37)]

(39.\&.\&.\&) \stetw $\!\!\!P\lto Q\,.$\hfill[Modus Ponens from 
(25) and (38)]

(40.\&.\&.\&) \stetw $\!\!\!(\bar A\subseteq\bar B\lto P)\imply
((P\lto Q)\imply(\bar A\subseteq\bar B\lto Q))\,.$

\hfill[Tautology
$(\alpha\lto\beta)\imply((\beta\lto\gamma)\imply(\alpha\lto\gamma))$] 

(41.\&.\&.\&) \stetw $\!\!\!(P\lto Q)\imply(\bar A\subseteq\bar B\lto
Q)\,.$\hfill
[Modus Ponens from (7) and (40)] 

(42.\&.\&.\&) \stetw $\!\!\!\bar A\subseteq\bar B\lto Q\,.$\hfill
[Modus Ponens from (39) and (41)] 


(43.\&.\&.\&) \stetw $\!\!\!(\bar A\subseteq\bar B\lto Q)
\imply((\bar A=\bar A\cap\bar B\lto Q)\imply
(\bar A\subseteq\bar B\lto
\bar A=\bar A\cap\bar B))\,.$

\hfill[Tautology
$(\alpha\lto\beta)\imply((\gamma\lto\beta)\imply(\alpha\lto\gamma))$] 

(44.\&.\&.\&) \stetw $\!\!\!(\bar A\!=\!\bar A\!\cap\!\bar B\!\lto\! Q)
\!\imply\!(\bar A\!\subseteq\!\bar B\!\lto\!\bar A\!=\!\bar A\!\cap\!\bar
B)\,.$ \hfill[Modus Ponens from (42) and (43)] 

(45.\&.\&.\&) \stetw $\!\!\!\bar A\subseteq\bar B\lto\bar A=\bar A\cap\bar
B\,.$\hfill[Modus Ponens from (15) and (44)] 


(46.\&.\&) \stetw $\!\!\!\bar A\subseteq\bar B\lto\bar A=\bar A\cap\bar
B\,.$\hfill[Rule 6, from (11) and (45)] 


(47.\&) \stetw $\!\!\!(\forall B)(\bar A\subseteq B\lto\bar A=\bar A\cap
B)\,.$\hfill[Rule 5, from (5) and (46)] 

(48) \stetw $\!\!\!(\forall A)(\forall B)(A\subseteq B\lto A=A\cap
B)\,.$\hfill[Rule 5, from (4) and (47)] 

\hfill{\bf QED}

}

\sepa

\label{cata}
\begin{center}
{\large{\bf A CATASTROPHE}}
\end{center}

\medbreak\noindent{\bf THEOREM 4:}  
$\emptyset=\emptyset\wedge(\sim\emptyset=\emptyset)$

\medbreak\noindent{\bf INFORMAL STATEMENT OF THEOREM 4:}  The empty set
is both equal to itself and not equal to itself. 

\medbreak\noindent{\bf INFORMAL PROOF:}  Let $C$ be the set 
of all $x$ such that $x$ does not belong to $C$, that is 
$$
C=\{x:\sim x\in x\}\,.
$$
Then, if $x$ is arbitrary, we have $x\in C\lto(\sim x\in x)$. 
Specialize this to $x=C$. We get 
$C\in C\lto(\sim C\in C)$. Now 
$C\in C\lto(\sim C\in C)$ is an instance of the contradiction 
$\alpha\lto(\sim\alpha)$. So, if $P$ is any statement whatsoever, then 
$(C\in C\lto(\sim C\in C))\imply P$ is an instance of the tautology
$(\alpha\lto(\sim\alpha))\imply\beta$. Now we can take $P$ to be any
statement we want, for example 
$\emptyset=\emptyset\wedge(\sim\emptyset=\emptyset)$. Then 
$(C\in C\lto(\sim C\in C))\imply P$ is an instance of a tautology, and 
we have proved $C\in C\lto(\sim C\in C)$. So we get $P$ by Modus 
Ponens.\ \  {\bf QED} 

\medbreak\noindent{\bf FORMAL PROOF:}  

{\parindent=0pt

(1) \stetw $(\exists S)(S=\{x:\sim x\in x\})\,.$\hfill[Set Axiom NST.1]

(2.\&) \stetw Let $C$ be such that $C=\{x:\sim x\in
x\})\,.$\hfill[From (1), in preparation to apply Rule 6] 

(3.\&) \stetw $(\forall x)(x\in C\lto(\sim x\in x))\,.$\hfill[
Expand (2) using ABBR.3]

(4.\&) \stetw $C\in C\lto(\sim C\in C)\,.$\hfill[
Rule 4, from (3)] 

(5.\&) \stetw $(C\in C\lto(\sim C\in C))\imply
(\emptyset=\emptyset\wedge(\sim\emptyset=\emptyset))\,.$\hfill[
Tautology $(\alpha\lto(\sim\alpha))\imply\beta$] 

(6.\&) \stetw $\emptyset=\emptyset\wedge(\sim\emptyset=\emptyset)\,.$\hfill[
Modus Ponens from (4) and (5)] 

(7) \stetw $\emptyset=\emptyset\wedge(\sim\emptyset=\emptyset)\,.$\hfill[
Rule 6, from (2) and (6)] 

\hfill{\bf QED}

}

\label{russell}
\begin{center}
\fbox{
\begin{minipage}{5.4in}
\vspace{1mm}
\begin{center}
{\large{\bf THE RUSSELL PARADOX}}
\end{center}

\medbreak\noindent Theorem 4 has catastrophic consequences, because
{\bf its conclusion is a contradiction}. So Theorem 4 tells us that 

\begin{center}
\fbox{\fbox{
\begin{minipage}{3in}
\baselineskip=19pt
\begin{center}
{\huge{${\cal NA}\ddot{{\cal I}}{\cal VE}\quad{\cal SET}$
${\cal THEORY\quad  IS}$ ${\cal INCONSISTENT}$!!!}}
\end{center}
\vspace{0.3mm}
\end{minipage}
}}
\end{center}

This means that {\bf in Na\"\i{}ve Set Theory you can prove anything you want.}
For example, you can prove that $2+2=4$, that $2+2=7$, that the number
$5$ is prime, that the number $5$ isn't prime, that $\sqrt{2}$ is
irrational, that $\sqrt{2}$ is rational, that you are the Emperor 
of the Klingorns, anything you want. (We saw in one of the boxes in Handout
No. 10---in page 3---how, once you have prved one contradiction, it becomes
possible to prove absolutely anything.) This means that 
the whole idea of developing a mathematical theory based on Na\"\i{}ve
Set Theory is just pointless, because the notion of proof becomes useles,
since every statement is provable, so we can prove false things as well as
true ones, and if we prove something then we will still don't know that it
is true. 

The inconsistency of Na\"\i{}ve Set Theory was discovered by the British 
mathematician and philosopher {\bf Bertand Russell} (1872-1970$^1$): 

\medbreak
$\quad$$\quad$
\begin{minipage}{4.7in}
\baselineskip=9pt

\vspace{1mm}
Over a long and varied career, Bertrand Russell made ground-breaking
contributions to the foundations of mathematics and to the development of
contemporary formal logic, as well as to analytic philosophy. His
contributions relating to mathematics include his discovery of Russell's
paradox, his defense of logicism (the view that mathematics is, in some
significant sense, reducible to formal logic), his introduction of the
theory of types, and his refining and popularizing of the first-order
predicate calculus. Along with Kurt G\"odel, he is usually credited with
being one of the two most important logicians of the twentieth century.

Russell discovered the paradox which bears his name in May 1901, while
working on his Principles of Mathematics (1903). The paradox arose in
connection with the set of all sets which are not members of
themselves. Such a set, if it exists, will be a member of itself if and
only if it is not a member of itself. The significance of the paradox
follows since, in classical logic, all sentences are entailed by a
contradiction. In the eyes of many mathematicians (including David Hilbert
and Luitzen Brouwer) it therefore appeared that {\bf no proof could be trusted
once it was discovered that the logic apparently underlying all of
mathematics was contradictory.} A large amount of work throughout the early
part of this century in logic, set theory, and the philosophy and
foundations of mathematics was thus prompted.

Russell's paradox arises as a result of na\"\i{}ve set theory's so-called
unrestricted comprehension (or abstraction) axiom.  Originally introduced
by Georg Cantor, the axiom states that any predicate expression, $P(x)$,
which contains $x$ as a free variable, will determine a set whose members
are exactly those objects which satisfy $P(x)$. The axiom gives form to the
intuition that any coherent condition may be used to determine a set (or
class). Most attempts at resolving Russell's paradox have therefore
concentrated on various ways of restricting or abandoning this axiom.

\end{minipage}


\vspace{2mm}
NOTE: The above quotation is taken from the Web page 

$\qquad\qquad$ 
{\it http://www-groups.dcs.st-and.ac.uk/$\,\,\widetilde{\,\,}$history/ShortBiogs.html}

This Web site contains a lot of biographical information about 
mathematicians.   I strongly recommend that you pay it a visit. 

\vspace{0.6mm}
\noindent\hrulefill$\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad
\qquad\qquad\qquad\qquad\qquad\qquad$

\noindent{\small $^1$\ Yes, he lived 97 years! He was born on May 18, 1872,
and died on Feb 2, 1970.}

\end{minipage}
}
\end{center}

\label{frege}
\begin{center}
\fbox{
\begin{minipage}{5.4in}
\baselineskip=10.5pt
\vspace{1mm}
\begin{center}
{\large{\bf FREGE}}

\end{center}

\medbreak\noindent {\bf Gottlob Frege} (1848-1925) was one of the founders
of modern symbolic logic putting forward the view that mathematics is
reducible to logic.

Frege received his education at the universities of Jena (1869-71) and
G\"ottingen (1871-1873) where he studied mathematics, physics and
chemistry. He then taught at Jena in the department of mathematics where he
remained, first as a lecturer and then as a professor, for the rest of his
working life.

Frege lectured on all branches of mathematics although his mathematical
publications outside the field of logic are few. His writings on the
philosophy of logic, philosophy of mathematics, and philosophy of language
are of major importance. He once said:
``Every good mathematician is at least half a philosopher, and every good
philosopher is at least half a mathematician.''

He was the first to fully develop the main thesis of logicism, that
mathematics is reducible to logic. His works {\it The Foundations of
Arithmetic} (1884) and {\it The Basic Laws of Arithmetic, Volume 1} (1893)
are devoted to this project.

His work was not particularly well received, mainly it was ignored. While
Volume 2 of {\it The Basic Laws of Arithmetic} was at the printers he
received a letter (on June 16, 1902) from Bertrand Russell. Russell pointed
out, with great modesty, that the Russell paradox gave a contradiction in
Frege's system of axioms. After many letters between the two Frege modified
one of his axioms and explains in an appendix to the book that this was
done to restore the consistency of the system.  However with this modified
axiom, many of the theorems of Volume 1 do not go through and Frege must
have known this.  He probably never realized that even with the modified
axiom the system is inconsistent since this was not shown until after
Frege's death by Leshniewski.

\bigbreak {\small NOTE: This material is taken from the Web page

$\quad\qquad\qquad${\it http://www-groups.dcs.st-and.ac.uk/$\,\,\widetilde{\,\,}$history/ShortBiogs.html}

}


\vspace{1mm}

\end{minipage}
}
\end{center}





\label{russellarg}
\begin{center}
\fbox{
\begin{minipage}{5.4in}
\baselineskip=10.5pt
\vspace{1mm}
\begin{center}
{\large{\bf RUSSEL'S ARGUMENT}}
\end{center}

The argument used by Russell to get his paradox is as follows: 

\vspace{1mm}

$\quad\quad$
\begin{minipage}{4.8in}
\baselineskip=10pt
Form the set 
$$
S=\{x:x\notin x\}\,.
$$ 
Does $S$ belong to $S$ or not? If $S\in S$ then
$S$ must be one of the $x$'s that satisfy the condition defining $S$,
namely, $x\notin x$.  So $S\notin S$. If $S\notin S$ then $S$ is one of the
$x$'s that satisfy the condition defining $S$, namely, $x\notin x$, so
$S\in S$.  So we have proved $S\in S\Longleftrightarrow S\notin S$, which is a
contradiction. 
\end{minipage}

\vspace{1mm}
This belongs to a long tradition of ``paradoxes,'' going back to classical
Greece. For example: 

\bi
\item{} Suppose I say ``What I am saying now is a lie.'' Is this true of
false? You can see right away that if it is true then it has to be false,
and if it is false then it has to be true. 

\item{} Suppose there is a town where some men shave themselves 
and other do not. Suppose the town's barber shaves those people who do not
shave themselves, and nobody else.  Does he shave himself? 
\ei

The common denominator of all these paradoxes is {\bf self-reference}.  
``What I am saying now is a lie''  is a {\it self-referential statement},
because it talks about itself. (The statement says, essentially, 
``I am not true.'')    Similarly, if $S$ is the set of Russell's paradox,
then the statement $S\in S$ can only be true if it is not true, so the
statement says ``I am not true.'' 

\vspace{1mm}

\end{minipage}
}

\end{center}

\label{whyone}
\begin{center}
\fbox{
\begin{minipage}{5.4in}
\baselineskip=10.5pt
\vspace{1mm}
\begin{center}
{\large{\bf WHY IS A SINGLE CONTRADICTION SO BAD?}}
\end{center}

People who learn for the first time about the Russell paradox 
often fail to appreciate how devastating it is.  Sure, one can prove a
contradiction about some very weird set, but so what?  Nobody cares about 
weird sets anyhow, so this should not pose any problem when we want to
prove theorems about ``really important'' mathematical objects such as
natural numbers and real numbers. 

We already showed that this argument doesn't suffice. Indeed, once a
contradiction can be proved {\sl somewhere}, then the whole edifice of 
logic collapses, because {\bf everything} can be proved, so proofs become
worthless. 

It is said that Bertrand Russell was giving a lecture once on this topic,
and at the end someone asked, incredulously: 

\vspace{1mm}

$\quad\quad$
\begin{minipage}{4.8in}
I don't see how one can prove anything whatsoever from just one
contradiction.  For example, let us suppose that I allow you to assume that
$1=0$. Can you prove that you are the Pope?
\end{minipage}

\vspace{1mm}
Russel's response came quickly: 

\vspace{1mm}

$\quad\quad$
\begin{minipage}{4.8in}
Sure I can. Here is the proof. If $1=0$ then, adding $1$ to both sides, 
we get $2=1$. Now, let $A$ be the set consisting 
of two people, namely, myself and the Pope. Then $A$ has two members.
Since $2=1$, $A$ has exactly one member. Therefore the Pope and I are the 
same person. So I am the Pope.\ \ {\bf QED}

\vspace{1mm}

\end{minipage}

\vspace{1mm}

\end{minipage}
}

\end{center}

\sepa


\begin{center}
{\large{\bf AXIOMATIC SET THEORY}}\label{exasetaxi}
\end{center}

\medbreak\noindent{\bf Axiomatic Set Theory} arises as an effort to 
eradicate the Russell paradox from Set Theory.  If you look at the 
proof of Theorem 4, you will see that the real culprit appears to be Set
Axiom NST.1, which allowed us to bring in the set 
$\{x:\sim x\in x\}$.    This axiom is called the ``comprehension'' 
or ``abstraction'' axiom, because it allows us to
``abstract''\footnote{The verb ``to abstract'' means 
``to take out of; extract; remove; consider separately from something
else.''} a property---represented by a predicate $p(x)$---
and form the set of all the things that have this property. 
Axiom NST.2 is an {\bf unrestricted abstraction axiom}, because it allows
to manufacture a set for every property.   If this is allowed, then 
we can take the predicate $\sim x\in x$, and the result is unmitigated
disaster, as we have shown. 

The way to get around this problem is to restrict the validity 
of the abstraction axiom.  

\label{axaxio}
\begin{center}
\fbox{
\begin{minipage}{5in}
\vspace{1mm}
\begin{center}
{\large{\bf THE BASIC AXIOMS OF AXIOMATIC SET THEORY}}
\end{center}

In Axiomatic Set Theory, we use the same basic 
symbols as in Na\"\i{}ve Set Theory, namely, 
the binary predicate symbols $=$ and $\in$, and the reserved constant 
$\emptyset$.  The three basic axioms are: 

\medbreak\noindent AXIOM-SCHEME AST.1: If $S,T,x,y_1,\ldots,y_n$ are distinct
variables, and $p(x,y_1,\ldots,y_n))$ is any formula that has
no quantifiers involving $x,y_1,\ldots,y_n$, has
no free variables other than $x,y_1,\ldots,y_n$, does not contain 
$S$, and does not contain $T$, then 
$$
(\forall y_1)\ldots(\forall y_n)(\forall T)
(\exists S)(S=\{x:x\in T\wedge p(x,y_1,y_2,
\ldots,y_n)\})
$$
is an axiom.

\medbreak 
AXIOM AST.2: $(\forall S)(\forall T)(S=T\lto(\forall x)(x\in
S\lto x\in T))\,.$ 

\medbreak AXIOM-DEFINITION AST.3: $\emptyset=\{x:\sim x=x\}\,.$

\vspace{1mm}
\end{minipage}
}
\end{center}

\newpage

\medbreak\noindent COMMENTS: 

\bi
\item{} The second and third axioms (that is, the
``definitions'' of equality and the empty set) are exactly the same as in
Na\"\i{}ve Set Theory.  

\item{} The first axiom is quite different, however.  To understand the
difference, let us first forget about the variables $y_1,\ldots,y_n$ and
just focus on the main difference. In Na\"\i{}ve Set Theory we said 
that if $p(x)$ is a formula that does not contains the variable $S$, has
no free variables other than $x$, and contains no 
quantifiers in $x$, then 
$$
(\exists S)(S=\{x:p(x)\})
$$
is an axiom.  Now we are saying that 
$$
(\forall T)(\exists S)(S=\{x:x\in T\wedge p(x)\}) \eqno{(\%)} 
$$
is an axiom, if in addition $p(x)$ does not contain $T$ either. 

\item[] So, for example, in Na\"\i{}ve Set Theory we can take 
$p(x)$ to be the formula $\sim x\in x$, and conclude that 
$$
(\exists S)(S=\{x:\sim x\in x\})\eqno{(*)} 
$$
is an axiom. Then we can bring (*) into a proof, as we did in Step 1 of the
proof of Theorem 4, with disastrous consequences.  

\item[] In Axiomatic Set Theory, all we can conclude is that 
$$
(\forall T)(\exists S)(S=\{x:x\in T\wedge(\sim x\in x)\})\eqno{(\#)}
$$
is an axiom.  Then you can bring (\#) into a proof, but you will not be
able to do anything with it unless you get hold of some set $A$, 
so that you can specialize $T$ to $A$ is (\#) and go to 
$$
(\exists S)(S=\{x:x\in A\wedge(\sim x\in x)\})\,.
$$
This will give you new set whose members are all the 
$x$s such that $x\in A$ and $\sim x\in x$. Clearly, this set 
will be a subset of $A$.  The Russell paradox does not arise any more. 

\item[] Actually, Axiom-scheme AST.1 will only allow you to build new sets as
subsets of old sets. If $p(x)$ is a formula as before, then (\%) is an
axiom, but you will only be able to use this to produce the set $\{x:x\in
A\wedge p(x)\}$ out of a set $A$ already known to exist, and what you will 
get will be a subset of $A$. 

\item[] So Axiom-scheme AST.1 is a {\bf restricted abstraction axiom}, 
because it allows us to form new sets by ``abstraction,'' but it only 
does so under very restricted conditions. 
\ei



\sepa

\label{someother}
\begin{center}
{\large{\bf SOME OTHER AXIOMS OF AXIOMATIC SET THEORY}}
\end{center}

\noindent By introducing the restricted abstraction axiom of Axiomatic Set
Theory as a substitute for the unrestricted abstraction axiom of Na\"\i{}ve
Set Theory, we avoid the Russell paradox. But we have to pay a price.  If
we can only form new sets by ``extracting'' them from old sets, it would
seem that we can never a large set if we only have small sets.

For example: suppose we have a set $A$. How do we know 
that the power set ${\cal P}(A)$ exists?   Similarly, 
suppose we have two sets $A$ and $B$. How do we know 
that the union $A\cup B$ exists?   

In {\sl some} cases, we can prove existence.  For example, let us prove
that the intersection of two sets always exists.  (``Intersection''
is defined by Axiom-definition (NST.AD.2), exactly as in Na\"\i{}ve Set
Theory.) 

\medbreak\noindent{\bf THEOREM 5:} $(\forall A)(\forall B)(\exists C)
(C=A\cap B)$. 


\medbreak\noindent{\bf INFORMAL PROOF:} Let $A$, $B$ be sets. 
Then the restricted abstraction Axiom-scheme AST.1 tells us that 
there is a set $C$ such that $C=\{x:x\in A\wedge(x\in A\wedge x\in B)\}$. 
Since ``$x\in A\wedge(x\in A\wedge x\in B)$'' is obviously equivalent to 
``$x\in A\wedge x\in B$,'' $C$ is none other than 
$\{x:x\in  A\wedge x\in B\}$.  So $C=A\cap B$. \ \ {\bf QED}

\medbreak\noindent{\bf FORMAL PROOF:} 

{\parindent=0pt

(1) \stetw $(\forall X)(\forall Y)(X\cap Y=\{x:x\in X\wedge x\in Y\})\,.$
\hfill[Axiom-definition NST.AD.2]

(2) \stetw $(\forall X)(\forall Y)(\forall T)(\exists S)
(S=\{x:x\in T\wedge(x\in X\wedge x\in Y)\})\,.$
\hfill[Axiom-scheme AST.1]

\medbreak NOTE: We are applying AST.1 with $n=2$, using the formula 
$x\in X\wedge x\in Y$---which has three variables, namely, $x$, $X$, and
$Y$---in the role of $p$. 

\medbreak 
(3.\&) \stetw Let $\bar A$ be arbitrary.\hfill[Preparation to apply Rule 5]

(4.\&.\&) \stetw Let $\bar B$ be arbitrary.\hfill[Preparation to apply Rule 5]

(5.\&.\&) \stetw $(\forall Y)(\bar A\cap Y=\{x:x\in\bar A\wedge x\in Y\})\,.$
\hfill[Rule 4, from (1)]

(6.\&.\&) \stetw $(\forall Y)(\forall T)(\exists S)
(S=\{x:x\in T\wedge(x\in\bar A\wedge x\in Y)\})\,.$
\hfill[Rule 4, from (2)]

(7.\&.\&) \stetw $\bar A\cap\bar B=\{x:x\in\bar A\wedge x\in\bar B\}\,.$
\hfill[Rule 4, from (5)]

(8.\&.\&) \stetw $(\forall T)(\exists S)
(S=\{x:x\in T\wedge(x\in\bar A\wedge x\in\bar B)\})\,.$
\hfill[Rule 4, from (6)]

(9.\&.\&) \stetw $(\exists S)
(S=\{x:x\in\bar A\wedge(x\in\bar A\wedge x\in\bar B)\})\,.$
\hfill[Rule 4, from (8)]

(10.\&.\&.\&) \stetw $\!\!\!{\rm Let}$ $\bar C$ be such that 
$\bar C=\{x:x\in\bar A\wedge(x\in\bar A\wedge x\in \bar B)\}\,.$

\hfill[From (9), preparation to apply Rule 6] 

(11.\&.\&.\&) \stetw $\!\!\!(\forall x)(x\in\bar C\lto 
(x\in\bar A\wedge(x\in\bar A\wedge x\in \bar B)))\,.$
\hfill[Expand (10) using ABBR.3]

(12.\&.\&.\&) \stetw $\!\!\!(\forall x)(x\in\bar A\cap\bar B\lto(
x\in\bar A\wedge x\in \bar B))\,.$ 
\hfill[Expand (7) using ABBR.3]

(13.\&.\&.\&.\&) \stetw $\!\!\!{\rm Let}$ $a$ be
arbitrary.\hfill[Preparation to apply Rule 5] 

(14.\&.\&.\&.\&) \stetw $\!\!\!a\in\bar C\lto 
(a\in\bar A\wedge(a\in\bar A\wedge a\in \bar B))\,.$
\hfill[Rule 4, from (11)]

(15.\&.\&.\&.\&) \stetw $\!\!\!(a\in\bar C\lto 
(a\in\bar A\wedge(a\in\bar A\wedge a\in \bar B)))\imply
(a\in C\lto(a\in\bar A\wedge a\in \bar B))\,.$

\hfill[Tautology $(\alpha\lto (\beta\wedge(\beta\wedge\gamma)))\imply
(\alpha\lto(\beta\wedge\gamma))$]

(16.\&.\&.\&.\&) \stetw $\!\!\!a\in\bar C\lto(
a\in\bar A\wedge a\in \bar B)\,.$
\hfill[Modus Ponens from (14) and (15)]

(17.\&.\&.\&) \stetw $\!\!\!(\forall x)(x\in\bar C\lto
(x\in\bar A\wedge x\in \bar B))\,.$
\hfill[Rule (5) from (13) and (16)]

(18.\&.\&.\&) \stetw $\!\!\!\bar C=\{x:x\in\bar A\wedge x\in\bar B\}\,.$
\hfill[Abbreviate (17) using ABBR.3]

(19.\&.\&.\&) \stetw $\bar C=\bar A\cap\bar B\,.$\hfill[Rule 8, 
from (7) and (18)]

(20.\&.\&.\&) \stetw $\!\!\!(\exists C)(C=\bar A\cap \bar B)\,.$\hfill[Rule
7, from (19)] 

(21.\&.\&) \stetw $\!\!\!(\exists C)(C=\bar A\cap \bar B)\,.$\hfill[Rule
6, from (10) and (20)]  

(22.\&) \stetw $\!\!\!(\forall B)(\exists C)(C=\bar A\cap B)\,.$\hfill[Rule
5, from (4) and (21)]

(23) \stetw $\!\!\!(\forall A)(\forall B)
(\exists C)(C=A\cap B)\,.$\hfill[Rule
5, from (3) and (22)]

\hfill{\bf QED} 

}


\medbreak\noindent QUESTION: do you think you can prove in the same way
that the union $A\cup B$ of any two sets $A$, $B$, exists? How about the
difference $A-B$ and the symmetric difference $A\Delta B$?

\sepa

\label{exiset}
\begin{center}
{\large{\bf HOW DO WE KNOW THAT THERE ARE ANY SETS AT ALL?}}
\end{center}

If you think about it for a minute, we could even ask


\begin{center}
\fbox{\fbox{
\begin{minipage}{4in}
\baselineskip=17pt
\vspace{0.6mm}	
\begin{center}
{\Large{${\cal HOW}$ ${\cal DO}$ ${\cal  WE}$ 
${\cal KNOW}$ ${\cal THAT}$}}\\
{\Large{${\cal THERE}$ ${\cal ARE}$ ${\cal  ANY}$ ${\cal SETS}$
${\cal AT}$ ${\cal ALL}\,\,$?}}
\end{center}
%\vspace{0.1mm}	
\end{minipage} 
}}
\end{center}
Or, if you remember that we are thinking of set theory as describing a 
world where there is nothing but sets, the question becomes

\begin{center}
\fbox{\fbox{
\begin{minipage}{4in}
\baselineskip=17pt
\vspace{0.6mm}	
\begin{center}
{\Large{${\cal HOW}$ ${\cal DO}$ ${\cal  WE}$
${\cal KNOW}$ ${\cal IN}$}}\\
{\Large{${\cal AXIOMATIC}$ ${\cal SET}$ ${\cal THEORY}$ ${\cal THAT}$}}\\
{\Large{${\cal THERE}$ ${\cal  IS}$ ${\cal ANYTHING}$
${\cal AT}$ ${\cal ALL}\,\,$?}}
\end{center}
\end{minipage} 
}}
\end{center}
If you try to translate this into a formal statement, 
the question becomes 

\begin{center}
\fbox{\fbox{
\begin{minipage}{3in}
{\Large
\begin{center}
How do we know that $\,\,(\exists x)(x=x)\,\,$ is true?
\end{center}}
\end{minipage} 
}}
\end{center}
If you are baffled by the fact that we are translating ``something exists''
as ``$(\exists x)(x=x)$,'' try to figure out how else you might say that 
``something exists.''  You cannot say ``$(\exists x)$,'' because this 
is not a well-formed formula\footnote{There is a serious
philosophical 
issue underlying all this. In English, the verb ``exist'' functions very
much like other intransitive verbs such as ``sleep'' or ``work.'' 
You can talk about things (or people) that sleep and things that do not. 
In either case, the thing---or person---must exist, for otherwise who
would you be talking 
about when you say that so-and-so sleeps eight hours a day? 
This sometimes has led people to think that anything you could talk about
---e.g. unicorns, six-legged chickens, flying pigs, and round squares---
must exist. For example, even when we say that ``round squares do not
exist,'' this looks like a statement that talks about some things---round 
squares---and says that those things have a certain property, namely, that
of not existing.  Since that statement talks about something, there must be
something that the statement talks about, or else it would be talking 
about nothing, which looks ridiculous, since the statement clearly talks
about round squares. In the formal language called ``predicate calculus,''
this problem disappears, because ``exists'' is not a predicate at all.
``Exists'' is a {\bf quantifier}, which means that we can say things like
``$\sim(\exists x)(x\,\,\,{\rm is\,\,\,square}\wedge
x{\rm\,\,\,is\,\,\,round})$,'' 
but this does not in any way mean that we are talking about 
an existing object.  All it means is that there is no way
to fill the  square slot 
in the expression ``$\,\,\bix\,\,\,{\rm is\,\,\,square}\,\,\wedge
\,\,\bix{\rm\,\,\,is\,\,\,round}\,$'' 
so as to make the resulting statement true.}. All you can say 
is that ``there exists some $x$ such that $p(x)$,'' if $p(x)$ is a 
formula. Fortunately, we can use the formula $x=x$, which is true for every
$x$, so saying that ``something exists'' is exactly equivalent to saying 
``there exists some $x$ such that $x=x$.'' 

The answer to our existence question is easy, because our axioms are such
that the existence of at least one set, namely, the empty set, is
guaranteed.


\medbreak\noindent{\bf THEOREM 6:} $(\exists x)(x=x)$.

\medbreak\noindent{\bf INFORMAL STATEMENT OF THEOREM 6:} Something exists. 

\medbreak\noindent{\bf INFORMAL PROOF:} By Axiom AST.3, the empty set
exists. \ \ {\bf QED}

\medbreak\noindent{\bf FORMAL PROOF:} 

{\parindent=0pt

(1) \stetw $(\forall x)(x=x)\,.$\hfill[Axiom Eq.1]

(2) \stetw $\emptyset=\emptyset\,.$\hfill[Rule 4, from (1)]

(3) \stetw $(\exists x)(x=x)\,.$\hfill[Rule 7, from (2)]

\hfill{\bf QED} 

}

\medbreak\noindent So we have made some progress, but not much, really. We got
{\bf one} set, namely, the empty set. Can we do better?
\begin{center}
\fbox{\fbox{
\begin{minipage}{4in}
\baselineskip=16pt
\vspace{0.6mm}	
\begin{center}
{\Large{${\cal HOW}$ ${\cal DO}$ ${\cal  WE}$ ${\cal KNOW}$}}\\
{\Large{${\cal IN}$ ${\cal AXIOMATIC}$ ${\cal SET}$ ${\cal THEORY}$}}\\
{\Large{${\cal THAT}$ ${\cal THERE}$ ${\cal  ARE}$ ${\cal ANY}$
${\cal SETS}$}}\\
{\Large{${\cal OTHER}$ ${\cal THAN}$ ${\cal THE}$ ${\cal EMPTY}$ 
${\cal SET}\,\,$?}}
\end{center}
\end{minipage} 
}}
\end{center}

\bigbreak
\begin{center}
{\Large{\sl The answer to this and other fascinating 
\\
questions is coming in the next handout.}} 
\end{center}
\end{document}


The answer is 

\begin{center}
\fbox{\fbox{
\begin{minipage}{4in}
\baselineskip=18pt
\vspace{0.6mm}	
\begin{center}
{\Large{${\cal WE}$ ${\cal DON'T}$ ${\cal KNOW}\,,$}}\\
{\Large{${\cal UNLESS}$ ${\cal WE}$ ${\cal ADD}$ ${\cal MORE}$
${\cal  AXIOMS}$}}
\end{center}
\end{minipage} 
}}
\end{center}

To see this, imagine that the only object in the universe was the empty
set. Then all the axioms that we have so far would be true. (This is easy
to prove. Try it!) That means that there is no way to prove that there are
other sets {\bf from the axioms that we have so far.}  

This brings us to the most delicate part of Axiomatic Set Theory, namely, 
how to put in extra axioms so as to gurantee the existence of sufficiently
many sets to make the theory inetersting and useful, without going too far
and allowing so many sets that the Russell paradox creeps in and the theory
becomes inconsistent. 



\end{document}


