\documentclass[10pt]{article}
%\input mymacros
%\nopagenumbers
\def\proofend{\enspace\hfill $\diamondsuit$\bigskip}
\newcount{\quesco}
\def\quesno{\the\quesco \global\advance\quesco by 1}
\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{\longrightarrow}
\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 --- SPRING 2000}}
\bigbreak
\centerline{{\mymagtwoit Introduction to Mathematical Reasoning}}
\medbreak
\centerline{Instructor: H. J. Sussmann} 

\medbreak
\centerline{{\bf HANDOUT NO. 2.}  February 3, 2000}


\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{\longleftrightarrow}
\def\clo{{\rm Clos}}
\defco=0
\statco=0
\remco=0
\rulco=0
\drulco=0
\notco=0
\quesco=1
\def\ino{{\rm Int}}


\bigbreak
\sepa

\bigbreak

\centerline{{\bf HOMEWORK ASSIGNMENT NO. 3, DUE ON THURSDAY, FEBRUARY 10}}

\bi
\item[1.] Make a precise statement describing which natural numbers can be
expressed as the difference of the squares of two natural numbers, and then
prove your statement. (In case it is not clear to you what I mean by ``make
a precise statement,'' here is an example. Suppose I asked you to ``make a
precise statement describing which natural numbers can be expressed as the
sum of two odd natural numbers.'' Then a good answer could be: 

\bi
\item{} {\it the natural numbers that can be expressed as the sum of two 
odd natural numbers are precisely the even natural numbers}, 
\ei
or, if you prefer to say it more formally: 
\bi
\item{} {\it let $n$ be a natural number; then $n$ is expressible as a sum
of two odd natural numbers if and only if $n$ is even.}  \ei Just to make
sure that we understand each other, here are examples of answer that I
would {\bf not} consider satisfactory: 
\bi
\item{} {\it A natural number is expressible as a sum of two odd numbers 
if and only if $n$ is even.}
\item{} {\it If a natural
number $n$ is expressible as a sum of two odd numbers then $n$ is even.}
\ei
QUESTION: why are these two answers not right?)

\item[2.] Answer the question at the end of the statement of the 
previous problem. 

\item[3.] Prove:  the product of 5 consecutive natural numbers
is always divisible by 120.  

\item[4.] Problems A and B in page \pageref{gurgu} of this handout.

\ei

\sepa

\begin{center}
{\Large{\bf PROPOSITIONAL CALCULI\footnote{``Calculi'' is the plural 
of ``Calculus.''}}}\label{propca}
\end{center}

\bigbreak\noindent To specify precisely what a {\bf propositional calculus}
is, we have to begin by saying what are the {\bf basic symbols}.

\medbreak 

\begin{center}
\fbox{
\begin{minipage}{11cm}
\vspace{1mm}
\begin{center}
{\large{\bf 1. THE BASIC SYMBOLS OF  A PROPOSITIONAL CALCULUS}}
\end{center} 
A propositional calculus uses {\bf three} kinds of basic symbols: 

\bi
\item[1.] the {\it propositional variables} (usually letters such as $P$,
$Q$, $R$, $S$),

\item[2.] the {\it logical connectives} $\vee$, $\wedge$, $\imply$, $\lto$,
$\sim$,

\item[3.] the {\it parentheses} $\,\,\,(\,\,\,$ and $\,\,\,)\,\,\,$.
\ei

\end{minipage} 
}
\end{center} 

\medbreak\noindent The logical connectives have {\bf names}:

\begin{itemize}
\item{} ``$\,\,\wedge\,\,$'' is read as ``and,'' and is called ``and'' or ``conjunction;''
\item{} ``$\,\,\vee\,\,$'' is read as ``or,'' and is called ``or'' or ``disjunction;''
\item{} ``$\,\,\sim\,\,$'' is read as ``no,'' or ``not,'' or ``it's not the case that,''
and is called ``no'' or ``not'' or ``negation;''
\item{} ``$\,\,\imply\,\,$'' is read as ``implies,''  
and is called ``implication;''
\item{} ``$\,\,\lto\,\,$'' is read as ``if and only if,''  
and is called ``biconditional.''
\end{itemize}

\medbreak\noindent The previous list of various ways of reading the 
logical connectives is not complete. There are many other ways. For example,

\medbreak
\begin{itemize}
\item{} $P\imply Q$ can be read as ``$P$ implies $Q$,'' or 
``if $P$ then $Q$,'' or ``$Q$ if $P$.''

\item{} $P\lto Q$ can be read as ``$P$ if and only if $Q$,'' or 
``$P$ is equivalent to $Q$.''
\end{itemize}

\bigbreak
\begin{center}
{\large{\bf 2. WELL-FORMED FORMULAS}}
\end{center} 

\medbreak\noindent A propositional calculus is a {\em language}, exactly as 
English or French are languages.   In English or French, there are basic symbols
(the letters, the blank space, the punctuation marks), but not every string of such 
symbols is acceptable or meaningful. In English, for example

\medbreak
\begin{itemize}
\item{} ``gfeqpiqew'' is meaningless;
\item{} ``I am the greatest teacher in the whole world'' is meaningful (and obviously true);
\item{} ``the square invocation sleeps furiously but no so yesterday why I say'' is sort of borderline. 
(What do you think?)
\end{itemize}

One thing that distinguishes propositional calculi from ``natural languages'' such as English
is that in a propositional calculus there is a very precise way to tell 
the ``good'' strings apart from the ``bad'' ones. {\bf There are no borderline cases.}


The ``good'' (or ``acceptable,'' or ``meaningful'') strings of symbols of a 
propositional calculus are called {\bf well-formed formulas}\footnote{``Well-formed
formula'' is a generic expression to refer to the ``acceptable'' strings
of any formal language.   Sometimes, in a particular formal language, the well-formed
formulas of that language have a special name. For example, the well-formed formulas of a
propositional calculus are called ``propositional forms.''}.

The well-formed formulas are those
strings of symbols that can be obtained by applying certain {\bf rules}: 

\begin{center}
\fbox{
\begin{minipage}{12cm}
\null\vspace{1mm}
\begin{center}
{\large{\bf PRECISE DEFINITION OF ``PROPOSITIONAL FORM''}}
\end{center}

\medbreak\noindent {\bf Propositional forms} are the well-formed formulas
of a given propositional calculus.  The rules determining which strings are
well formed are as follows:

\medbreak\noindent RULE PF1: One-letter strings consisting of a propositional
variable are well-formed formulas. 

\medbreak\noindent RULE PF2: If $A$ is a well-formed formula consisting of a
single letter then $\sim A$ is a well-formed formula.

\medbreak\noindent RULE PF3: If $A$ is a well-formed formula consisting of
more than a single letter then $\sim(A)$ is a well-formed formula.

\medbreak\noindent RULE PF4: If $A$ and $B$ are well-formed formulas
consisting of a single letter then $A\wedge B$, $A\vee B$, $A\imply B$ 
and $A\lto B$ are  well-formed formulas.

\medbreak\noindent RULE PF5: If $A$ and $B$ are well-formed formulas
such that $A$ consists of a single letter but $B$ does not,
then $A\wedge(B)$, $A\vee(B)$, $A\imply(B)$ 
and $A\imply(B)$ are  well-formed formulas.

\medbreak\noindent RULE PF6: If $A$ and $B$ are well-formed formulas
such that $B$ consists of a single letter but $A$ does not,
then $(A)\wedge B$, $(A)\vee B$, $(A)\imply B$ 
and $(A)\imply B$ are  well-formed formulas.

\medbreak\noindent RULE PF7: If $A$ and $B$ are well-formed formulas
neither one of which consists of a single letter, 
then $(A)\wedge(B)$, $(A)\vee(B)$, $(A)\imply(B)$ 
and $(A)\imply(B)$ are  well-formed formulas.

\medbreak\noindent RULE PF8: Only those strings obtained by applying 
Rules PF1, PF2, PF3, PF4, PF5, PF6, and PF7 are well-formed formulas. 

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

\bigbreak\noindent Here are some examples of propositional forms (assuming
that the letters $P$, $Q$, $R$ are propositional variables):
\begin{itemize}
\item{} $\qquad P\,$
\item{} $\qquad Q\,$
\item{} $\qquad \sim P\,$
\item{} $\qquad (\sim P)\wedge Q\,$
\item{} $\qquad \sim((\sim P)\wedge Q)\,$
\item{} $\qquad (P\vee R)\imply(\sim((\sim P)\wedge Q))\,\qquad.$
\end{itemize}

\newpage

\medbreak\noindent And now let us look at a more complicated example of a  propositional form: 

\begin{center}
\fbox{
\begin{minipage}{5.4in}

\parindent=0pt

\null
\vspace{0.1mm}


\begin{center} 
{\bf AN EXAMPLE OF THE USE OF RULES PF1 TO PF9}
\end{center}

Let us look at the string
$$
(\sim Q)\imply(\sim(\sim(P\wedge(((\sim(\sim Q))\vee
R)\lto(R\imply(P\wedge Q))))))\,\,.
$$
\medbreak
Is this a well-formed formula? The answer is YES. To prove this, 
we exhibit a ``derivation'' of our string from the rules (using ``WFF'' to
stand for ``well-formed formula''); 

\medbreak

STEP $\,\,\,$1:$\,\,$ $P$ is a WFF by Rule PF1.

STEP $\,\,\,$2:$\,\,$ $Q$ is a WFF by Rule PF1.

STEP $\,\,\,$3:$\,\,$ $\sim Q$ is a WFF by Rule PF2.

STEP $\,\,\,$4:$\,\,$ $\sim(\sim Q)$ is a  WFF by Rule PF3.

STEP $\,\,\,$5:$\,\,$ $P\wedge Q$ is a WFF  by Rule PF4.

STEP $\,\,\,$6:$\,\,$ $R$ is a WFF by Rule PF1.

STEP $\,\,\,$7:$\,\,$ $R\imply(P\wedge Q)$ is a WFF  by Rule PF5.

STEP $\,\,\,$8:$\,\,$ $(\sim(\sim Q))\vee R$ is a  WFF by Rule PF6.

STEP $\,\,\,$9:$\,\,$ $((\sim(\sim Q))\vee R)\lto(R\imply(P\wedge Q))$ is a
WFF  by Rule PF6.

STEP $\,\,\,$10:$\,\,$ $P\wedge(((\sim(\sim Q))\vee R)\lto(R\imply(P\wedge
Q)))$ is a WFF  by Rule PF5.

STEP $\,\,\,$11:$\,\,$ $\sim(P\wedge(((\sim(\sim Q))\vee R)\lto(R\imply(P\wedge
Q))))$ is a WFF  by Rule PF3.

STEP $\,\,\,$12:$\,\,$ $\sim(\sim(P\wedge(((\sim(\sim Q))\vee
R)\lto(R\imply(P\wedge Q)))))$ is a WFF  by Rule PF3.


STEP $\,\,\,$13:$\,\,$ $(\sim Q)\imply(\sim(\sim(P\wedge(((\sim(\sim Q))\vee
R)\lto(R\imply(P\wedge Q))))))$ is a WFF  

\phantom{STEP $\,\,\,$13:$\,\,$} by Rule PF7.

\vspace{0.1mm}

\end{minipage}
}

\end{center}

\xdef\isitwff{\the\quesco}
\medbreak\noindent{\bf QUESTION \quesno:} Is $((P\wedge Q)\imply Q$ is
well-formed?  

\medbreak\noindent{\bf ANSWER:} NO. It is a good exercise to try to understand {\it why},
that is, 

\medbreak

\begin{center}
\fbox{\fbox{
\begin{minipage}{5.4in}

\parindent=0pt

\null
\vspace{0.1mm}


{\huge{\it How on Earth can anyone ever  possibly know for sure 
that the string $((P\wedge Q)\imply Q$ is not well-formed?}}

\end{minipage}}}

\end{center}


\medbreak\noindent First of all, you could try to produce $((P\wedge Q)\imply Q$ using the
three rules, and no matter how hard you try you will not be able to.  But,

\begin{center}
\fbox{\fbox{
\begin{minipage}{5.4in}

\parindent=0pt

\null
\vspace{0.1mm}

{\Large{\sl Just because you have not been able to do something it does not
follow that it cannot be done.}}
(Maybe God can say: ``if I cannot do something then it sure means it 
cannot be done.'' But certainly no limited, fallible, mortal human being 
would be entitled to make such a claim.)

\medbreak NOTE: In  Homework assignment No. 1 some students, in order to prove that the number 30 cannot
be expressed as the difference of the squares of two natural numbers,
wrote things like ``It cannot be done; reason: I tried several ways
and it did not work.''  Could those students really have meant what they 
said? If you are one of them, please think this over and do some 
soul-searching.  THIS IS IMPORTANT!
  
\end{minipage}}}

\end{center}


So, how do we know that $((P\wedge
Q)\imply Q$ {\bf cannot possibly} be obtained using the rules?  We need an
{\it argument}. We need {\it reasoning}.  We need a {\Huge{\bf proof.}}

\newpage
\noindent Here is a real proof. First, we prove a small theorem.

\medbreak\noindent THEOREM 1. {\sl In every well-formed formula the number
of left parentheses is equal to the number of right parentheses.}

\medbreak\noindent PROOF.  Call a string ``balanced'' if it has the same
number of left and right parentheses. Any string obtained using Rule 1 is
balanced, because it has zero left parentheses and zero right
parentheses. An application of Rules PF2 or PF4 will not produce any new
parentheses, so if the strings to which you applied these rules were balanced
then the new string will also be balanced.  An application of Rules PF3,
PF5, or PF6 will produce two new parentheses, one left and one right. So,
once again, if the strings you applied these rules to were balanced then
the new string will also be balanced.  Finally, if you apply Rules PF7 then
you will produce four new parentheses, two left and two right, and then in
this case too if the strings to which you applied the rule were balanced
then the new string will also be balanced.  So the application of Rules 
PF1 to PF7 can never yield unbalanced strings. END OF PROOF.

\medbreak\noindent{\bf PROOF THAT THE ANSWER TO QUESTION \isitwff{}
IS ``NO'':} The string $((P\wedge Q)\imply Q$ has two left parentheses
and one right parenthesis. So Theorem 1 tells us that it is not
well-formed. END OF PROOF.

\medbreak\noindent{\bf QUESTION \quesno:} Is the following 
``proof that $((P\wedge Q)\imply Q$ is not well-formed'' correct?

\medbreak\noindent{\bf PURPORTED PROOF THAT THE ANSWER TO QUESTION \isitwff{}
IS ``NO'':} The string $((P\wedge Q)\imply Q$ has two left parentheses
and one right parenthesis. So $((P\wedge Q)\imply Q$ is not balanced. 
But Theorem 1 tells us that a well-formed string has to be balanced. 
So $((P\wedge Q)\imply Q$ is not well-formed. END OF PROOF.

\medbreak\noindent{\bf ANSWER:} NOT REALLY\footnote{\baselineskip=7pt If
you wrote this in a paper then the people grading it might give you a very
high grade anyhow, because this argument shows that you got the point. But
they might not, because after all the proof does contain a serious
expository flaw, and if the greaders decide to be strict (for example,
because the instructor has told them to do so) then they might take
advantage of that flaw to give you a low grade, perhaps even a zero. The
best way to be sure that a grader will not use the logical flaws in your
reasoning to give you a lower grade is to {\bf write perfect proofs}, with
no flaws. {\bf Never rely on the kindness of graders!} It's much better to
rely on your own ability to be precise and clear and to give complete
arguments.}. If you think that this proof is correct, then please think
some more before you read the next paragraph. 

Why is this ``proof'' not really correct?  What is the problem?  
The problem is this: when you look at the statement of Theorem 
1, you will notice that it does not say anything about strings being
``balanced.'' Therefore, in the ``purported proof'' the author is talking
about ``balanced strings'' without having said what ``balanced'' means.   

Now, you may object that the meaning of ``balanced'' is explained quite
clearly in the proof of Theorem 1. That is indeed true, but the word ``balanced''
was introduced {\em within the proof}, for use within the proof, and
{\em outside the proof we do not know what ``balanced'' means.}

\medbreak\noindent{\bf Remark.}  Theorem 1 gives an example of a {\bf
necessary condition} for a string to be well formed.  (We say that $A$ is a
{\it necessary condition} for $B$ if $A$ happens whenever $B$ does, that
is, if $B$ implies $A$.  For example: ``he took the final exam'' is a
necessary condition for ``he passed the course,'' because if he passed the
course then he must have taken the final exam. But is of course not a
``sufficient condition.'' Just taking the final exam is not enough to pass
the course.)  The theorem says that if a string is well formed then it has
to have the same number of left and right parentheses. This condition is
not sufficient: there are many strings that have the same number of left
and right parentheses but are not well formed, as we will soon see. \proofend

\medbreak\noindent{\bf QUESTION \quesno:} Is the string
$P)($ well-formed?  

\medbreak\noindent{\bf ANSWER:} NO. This may look almost obvious to 
you but, once again, it is a good exercise to try to understand
{\it how we can know for sure that this string is not well-formed}.

Theorem 1 will not help us, because this string has one left parenthesis 
and one right parenthesis, so the necessary condition of Theorem 1 is
satisfied. So we need another theorem, giving us another necessary 
condition for well-formedness. 

\medbreak\noindent THEOREM 2. {\sl In every well-formed formula, if the
formula contains parentheses, then the first parenthesis---if you read the 
formula from left to right---must be a left parenthesis.}

\medbreak\noindent PROOF.  Call a string ``bad'' if it contains parentheses
and the first parenthesis from left to right is a right parenthesis. Call
a string ``good'' if it is not bad.  A string obtained using Rule 1 is good,
because it has no parentheses at all. An application of Rules PF2 or PF4
will not produce any new parentheses, so if the strings you applied these
rules to were good then the new string will also be good.  An application
of Rule PF3 will yield a string whose first symbol is $\sim$ and whose
second symbol is $(\,\,,$ so this string is clearly good.  An application
of Rule PF5 will yield a string whose first symbol is a letter, whose
second symbol is one of the logical connectives, and whose third symbol is
$(\,\,,$ so this string is clearly good.  An application of Rule PF6 or PF7
will yield a string whose first symbol is $(\,\,,$ so this string is
clearly good.  So the application of Rules PF1 to PF7 can never yield bad
strings. END OF PROOF.


\medbreak\noindent{\bf Remark.}  Theorem 2 gives another example of a {\bf
necessary condition} for a string to be well formed: it 
says that if a string is well formed and contains parentheses then 
it first parenthesis---goin from left to right---has to be
a left parenthesis. This condition is
not sufficient, even if you use it together with that of Theorem 1: there
are many strings that satisfy the conditions of Theorems 1 and 2 
but are not well formed. \proofend



\medbreak\noindent{\bf QUESTION \quesno:} Is the string
$P()$ well-formed?  

\medbreak\noindent{\bf ANSWER:} NO. Again, you may think 
this is obvious, but we want to have a real proof. 

Theorem 1 will not help us, because this string has one left parenthesis
and one right parenthesis, so the necessary condition of Theorem 1 is
satisfied. Theorem 2 will not help us either, because the first parenthesis
of our string is a left parenthesis. 

So we need another theorem, giving us another necessary 
condition for well-formedness. 

\medbreak\noindent THEOREM 3. {\sl A well-formed formula
cannot contain a left parenthesis immediately followed by a
right parenthesis.}

\medbreak\noindent PROOF.  Call a string ``bad'' if it contains a
left parentheses immediately followed by right parenthesis. Call  a string
``good'' if it is not bad.  A string obtained using Rule 1 is good, because
it has no parentheses at all. An application of Rules PF2 or PF4 will not
produce any new parentheses, so if the strings you applied these rules to
were good then the new string will also be good.  An application of Rule
PF3 will yield a string whose first symbol is $\sim$ and whose second
symbol is $(\,\,,$ so this string is clearly good.  An application of Rule
PF5 will yield a string whose first symbol is a letter, whose second symbol
is one of the logical connectives, and whose third symbol is $(\,\,,$ so
this string is clearly good.  An application of Rule PF6 or PF7 will yield
a string whose first symbol is $(\,\,,$ so this string is clearly good.  So
the application of Rules PF1 to PF7 can never yield bad strings. END OF
PROOF.


\medbreak\noindent{\bf Remark.}  Theorem 3 gives us a third example of a 
necessary condition for a string to be well formed. \proofend




\medbreak\noindent PROBLEM A. 
Is $((P\vee Q)\wedge\sim Q)\imply(P\vee Q)$ well formed?  Justify your
answer. 

\label{gurgu}

\medbreak\noindent PROBLEM B. 
Is $((P\vee Q)\wedge\sim Q)(\imply(P\vee Q))$ well formed?  Justify your
answer.   

\end{document}

\sepa

\bigbreak\noindent When we work with a propositional calculus, we usually
do not want to have to write too many parentheses. So we add the

\medbreak\noindent PARENTHESIS DELETION OPTION:   If there is only one way
to put the parentheses back in to produce a well-formed formula, then you
are allowed to omit them. 

\medbreak\noindent For example, you can write 
$P\wedge Q$ rather than $(P\wedge Q)$, or $\sim P$ rather than $(\sim P)$. 

\medbreak\noindent{\bf Remark}. The book, in the bottom half of page 6, 
gives you extra leeway to omit parentheses. For example, the book gives you
{\bf extra rules} so that, if you write $\sim P\wedge Q$, it is understood
that this stands for $((\sim P)\wedge Q))$. (In principle, it could also
have stood for $(\sim (P\wedge Q))$.  The rules given in the book exclude
this second possibility, because ``$\sim$ applies to the smallest
proposition following it.'')  

Notice that {\bf if you want to make the formulas simpler by allowing
deletion of lots of parentheses, as the book does, then the rules become
more complicated.} In my own personal view, it is better to keep the rules
simple, even at the cost of writing formulas with more parentheses. {\bf
You are free to do it my way, or the book's way, as you prefer, long as you
do it correctly.} \proofend

\sepa



\centerline{{\bf THE STRUCTURE OF A PROOF}}

\medbreak\noindent A {\bf formal proof} is going to be a sequence of
{\bf steps}. Each step consists of a {\bf statement}, 
accompanied by a {\bf justification}. The justification of a step
consists of showing that it is permitted by
the rules, given the previous steps. 

Let us recall that a {\bf statement} is a {\bf closed formula}. This 
means that a statement cannot have open variables. For example, 
$\diamond+3=7$ is {\bf not} a statement if $\diamond$ is a 
letter such as $x$, which is considered a {\bf variable}. 
If, on the other hand, $\diamond$ is a letter such as 
$a$, thought of as a {\bf constant}, then 
$\diamond+3=7$ {\bf is} a statement, but in that case 
the letter---say ``$a$''--- must have been introduced as
such. 

\begin{center}
\fbox{
\begin{minipage}{14cm}
\vspace{1mm}
\begin{center}
{\bf CONSTANTS MUST BE PROPERLY INTRODUCED} 
\end{center}

There will be exactly three ways to introduce a symbol such as 
the letter $a$ as a constant: 

\bi
\item[(C.1)] $a$ could be a {\bf reserved constant}, that is a special
symbol fixed once and for all to denote a particular object. For example,
in real-number arithmetic $0$, $1$, $2$, $\pi$, $e$, are resreved
constants. In set theory, $\emptyset$ is a reserved constant. 

\item[(C.2)] $a$ could be an ``arbitrary object.'' For example, 
the letter $a$ could be introduced as a constant by saying 
``Let $a$ be arbitrary.'' 

\item[(C.3)] $a$ could be an ``object that has a particular property.''
For example, we could say ``Let $a$ be such that 
$a.3=7$.''  From that moment on, we can freely use the fact that $a.3=7$. 
\ei 

\medbreak REMARK: Actually, (C.2) is not really that different from (C.3),
if you think about it for a minute. You can think of ``Let $a$ be
arbitrary'' as a way of saying ``Let $a$ be such that $a=a$.'' 
So, really, we could have dispensed with (C.2) altogether, and just 
used (C.3).  

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

\noindent In practice, any letter can be used as a constant or as a variable.
We can say things like 
$$
(\forall a)(\forall b)((a+b)^2=a^2+2a.b+b^2)\,,
$$
in which $a$ and $b$ are clearly variables. Also, we can use $x$ or $y$ as
constants, if we wish. For example, we can say ``Let $x=4$,'' or ``Let $x$
be arbitrary,'' and if we do that then we are starting a 
``proof within a proof'' (see below) within which
$x$ will play the role of a constant. 

To make things even more confusing (sorry!), we often use the same letter
in both capacities, in the same proof. For example, suppose I want to prove
$$
(\forall\varepsilon)(\varepsilon >0\imply(\exists
\delta)(0<\delta\wedge\delta<\varepsilon))\,.\eqno{(\%)} 
$$
(In other words, I want to prove that ``for every positive number there is 
another positive number which is smaller.'')

Then I could write 

\pline{(1.\&)\stef  Let $\varepsilon$ be arbitrary.}

\pline{(2.\&.\&)\stef Assume that $\varepsilon>0$.}

\pline{(3.\&.\&.\&)\stef Let $\delta=\frac{\varepsilon}{2}$.}

\pline{(4.\&.\&.\&)}{\stef $0<\delta\wedge \delta<\varepsilon$.}

\pline{(5.\&.\&)\stef $(\exists\delta)(0<\delta\wedge \delta<\varepsilon)$.}

\pline{(6.\&)}{\stef $\varepsilon>0\imply(\exists\delta)(0<\delta\wedge
\delta<\varepsilon)$.}

\pline{(7)}{\stef
$(\forall\varepsilon)(\varepsilon>0\imply(\exists\delta)(0<\delta\wedge 
\delta<\varepsilon))$.\hfill QED}  


\medbreak\noindent In this proof, in the first line I am introducing a new
{\bf constant}, but I am perversely calling it $\varepsilon$, exactly like
the variable $\varepsilon$ that occurs in Formula (\%). When I do so, I
start a subproof (or ``proof within a proof''), and I indicate this by
using an extra ``\&'', so the first line is (1.\&), meaning that this is 
step 1 and we are in a subproof, on level 2, one level down from the top
level.  Then in the
second line I go even deeper to a ``sub-subproof'', or ``proof within the
subproof,'' by introducing an assumption.  I indicate this by using another
``\&'', so the second line is (2.\&.\&), meaning ``step 2, and we
are in level 3, that is, in a sub-subproof.''.  Finally, in the third 
line I go even deeper to a ``sub-sub-subproof'', or ``proof within the
proof within the proof within the proof,'' by introducing a  constant
$\delta$ that satisfies a condition. I indicate this by using a third 
``\&'', so the third line is (3.\&.\&\.\&), meaning ``step 3 and
we are in level 4, that is, in 
sub-sub-subproof.''.  Moreover, I am being perverse here too, 
and I am using the letter $\delta$, which is a variable in ($\%)$,
as a constant in the level 4 sub-sub-subproof.  

\def\bix{\fbox{$\,^{\,}$}}

Now in (4)) I have established that, in the expression $0<\bix\,\wedge
\bix\,<\varepsilon$, there is something I can put in the box to make the
resulting statement true. So I make this statement (``the box in
$0<\bix\,\wedge\bix\,<\varepsilon$ can be filled with something that makes
the statement true'') which, as you can see, does not contain the constant
$\delta$ anywhere.  One of my eight inference rules (Rule 7, see below)
tells me that, since I have proved something not involving $\delta$, I can
go up one level. But then, perversely, I use the variable $\delta$ to
denote the ``box,'' so I end up with (5). This is in level 3, right
underneath ``Assume that $\varepsilon>0$.'' In other words, this has been
proved ``under\footnote{The word ``under'' is meant quite literally here!}
the assumption that $\varepsilon>0$.'' So one of my rules will tell me that
I can go up one level and assert (6). Now, finally, (6) is ``under''
the condition that ``$\varepsilon$ is arbitrary.''  In other words, I have
shown that, if I put a completely arbitrary $\varepsilon$ in the box, in
the expression
$$
\bix>0\imply(\exists\delta)(0<\delta\wedge\delta<\bix\,)\,,
$$
then what I get is true. So I use one my rules, and conclude that I can go
to the statement 
$$
\mbox{No matter what you put in the box,}\quad
\bix>0\imply(\exists\delta)(0<\delta\wedge\delta<\bix\,)\quad
\mbox{is true}\,, \eqno{(@)}
$$
in the next higher level. Moreover, I act perversely once again, and use
the variable $\varepsilon$ for the thing one can put in the box, so I end
up with (7). That is, I have landed in the top level
and with the statement to be proved. This is exactly
where I wanted to end up,  so at this point I declare victory, and write
{\bf QED}, which is the fancy way to say ``This is the end of the proof,''
using the Latin phrase ``quod erat demonstrandum'' (which means 
``which is what was to be proved'').

\medbreak If you think this is too messy because of the fact that the same
letters are used sometimes as constants and sometimes as variables, 
you might find it easier never to do that.  In other words, you could
choose to use different symbols for constants and for variables. 
Then the previous proof would look like this: 

\medbreak

\begin{center}
\begin{minipage}{14cm}

\pline{(1.\&)\stef  Let $\bar\varepsilon$ be arbitrary.}

\pline{(2.\&.\&)\stef Assume that $\bar\varepsilon>0$.}

\pline{(3.\&.\&.\&)\stef Let $\bar\delta=\frac{\bar\varepsilon}{2}$.}

\pline{(4.\&.\&.\&)}{\stef $0<\bar\delta\wedge\bar\delta<\bar\varepsilon$.}

\pline{(5.\&.\&)\stef $(\exists\delta)(0<\delta\wedge \delta<\bar\varepsilon)$.}

\pline{(6.\&)}{\stef $\bar\varepsilon>0\imply(\exists\delta)(0<\delta\wedge
\delta<\bar\varepsilon)$.}

\pline{(7)}{\stef
$(\forall\varepsilon)(\varepsilon>0\imply(\exists\delta)(0<\delta\wedge 
\delta<\varepsilon))$.\hfill QED}  
\end{minipage}
\end{center}

\medbreak

In this proof, $\bar\varepsilon$ and $\bar\delta$ are constants,
$\varepsilon$ and $\delta$ are variables, and no confusion is possible. 

\begin{center}
\fbox{
\begin{minipage}{14cm}
\vspace{1mm}
\begin{center}
{\bf CONSTANTS CAN ONLY NAME THINGS THAT EXIST} 
\end{center}

In the previous box, (C.3) looks like a very nice method for introducing a
constant.  You can take any conditions you want, and introduce an object 
that satisfies them.   For example, you can say:

\medbreak($\ldots)$ Let $a$ be the person who killed Polonius, 

\medbreak or

\medbreak($\ldots$) Let $a$ be a solution of the equation 
$x^5+6x^4-3x+8=0$.

\medbreak 
The catch is: {\bf you cannot introduce something if you don't know it
exists.}  For example, you cannnot introduce a constant $a$ with ``Let $a$
be such that $a.0=1$.''  (Once we state our axioms for the real numbers, we
will be able to prove from them that $(\forall x)(x.0=0)$.  If we could
introduce a constant $a$ such that $a.0=1$, then you could plug $a$ into
$x.0=0$---because $x.0=0$ is true for all $x$, so in particular is true for
$a$; this is called ``specialization''---and get $a.0=0$. But, since you
also have $a.0=1$, you would end up with $0=1$.  Since 
there also is an axiom saying that $\sim 0=1$, it will turn out 
that you have proved 
$$
0=1\,\wedge\,(\sim 0=1)\,,
$$
which is a {\bf CONTRADICTION}. And once you have one contradiction,
then it's a complete catastrophe! (See the next box.))

\vspace{1mm}

\end{minipage}
}

\end{center} 

\bigbreak

\begin{center}
\fbox{
\begin{minipage}{14cm}
\vspace{1mm}
\begin{center}
{\bf WHY IS A CONTRADICTION DISASTROUS?} 
\end{center}

Suppose you could prove a contradiction $C$.  Take any statement 
$S$ you want.   Then 
$C\imply S$ is an instance of a tautology, because 
$C\imply S$ always has the truth value $T$, since 
$C$ always has the truth value $F$.

So {\bf once you have proved one contradiction you can prove 
any statement you want, whether or not it is true.}

\vspace{1mm}

\end{minipage}
}

\end{center} 

\bigbreak

\begin{center}
\fbox{
\begin{minipage}{14cm}
\vspace{1mm}
\begin{center}
{\bf CONSISTENCY}
\end{center}

A mathematical theory where a contradiction can be proved 
is said to be {\bf inconsistent}. A theory which is not inconsistent 
is said to be {\bf consistent.} 

As we saw in a previous box, {\bf with an inconsistent theory you can prove
every statement.} So you can prove things that are false as well as things
that are true. Therefore the whole notion of ``proof'' and ``provability''
becomes useless. In a good theory you should not be able to prove false
things. Otherwise, the fact that you have proved something will not tell
you that it is true, and then the whole point of having proved it would be
lost. 

\vspace{1mm}

\end{minipage}
}

\end{center} 

\bigbreak

\begin{center}
\fbox{
\begin{minipage}{14cm}
\vspace{1mm}
\begin{center}
{\bf THE PEANO PARADOX}
\end{center}

\medbreak
THEOREM: $1$ is the largest natural number. 

\medbreak
PROOF: Let $n$ be the largest natural number. Then $n^2$ is a natural 
number too.  Since $n$ was the largest natural number, $n^2\le n$. 
On the other hand, $n\ge 1$, so $n^2=n.n\ge n.1=n$. So $n^2\le n$ and 
$n^2\ge n$. Therefore $n^2=n$. The only solutions $x$ of $x^2=x$ are 
$x=1$ and $x=0$.  So $n=1$ or $n=0$. But $0$ is not a natural number, so
$n$ cannot be $0$. Therefore $n$ has to be equal to $1$. {\bf QED}

\medbreak
QUESTION:  What is wrong with the above proof? ({\sl Something} must be
wrong! You don't really believe that 
$1$ is the largest natural number, do you?) 

\vspace{1mm}

\end{minipage}
}

\end{center} 




When we write a truly formal proof, it is a good idea to {\bf number the
steps}, so that every time you use some previous steps to justify a new
step, you can refere to them by number. 

For example, one of our rules (called \fbox{Modus Ponens}$\,$) 
will say that if you have two formulas  of the form $P$ and $P\Rightarrow
Q$, then you can go to $Q$.  So, for example, suppose that 
you are writing a proof, and you have just finished step 94. 
Suppose that earlier on, in the 25th step, you had the following 

\medbreak
\def\pline#1{#1}{(25)\ste $3>0\,\,.$ \hfill ($\ldots\ldots\ldots\ldots\ldots\ldots\ldots$)} 

\medbreak\noindent and in the 47th step you had

\medbreak
\pline{(47)\ste $3>0\Rightarrow(\exists x)(x^2=3)$. \hfill
($\ldots\ldots\ldots\ldots\ldots\ldots\ldots$).} 

\medbreak\noindent Then you are permitted to add a new Step 95 to your
proof, by saying: 

\medbreak
\pline{(95)\ste $(\exists
x)(x^2=3)$. \hfill (Modus Ponens,  from (25) and (47)).} 


\bigbreak  Of course,  if every step had to be justified by
invoking previous steps, then we would never be able to get started.  So
{\sl some} kinds of steps must be permitted that do not require any
previous step.  There will be {\bf three} such kinds of steps: we will
always be permitted to bring in an {\bf axiom} as a new step, 
or a {\bf definition}, or one of the {\bf hypotheses}.

\bigbreak In addition, one of our rules (Rule 1, to be precise) will tell
us that you are always allowed to bring in an \fbox{instance of a
tautology}.  For example, suppose that at some point of a proof you have

\medbreak\pline{(238)\ste $3>0\vee 3<0\,$.\hfill
($\ldots\ldots\ldots\ldots\ldots\ldots\ldots$)} 

\medbreak\noindent and then later you managed to get 

\medbreak\pline{(455)\ste $\sim 3<0$.   
\hfill($\ldots\ldots\ldots\ldots\ldots\ldots\ldots$)}

\medbreak\noindent Armed with these two facts, 
it should now be possible to go to ``$3>0$.''  (Intuitively, this is clear:
if you know that either $3>0$ or $3<0$, and also that it's not the case
that $3<0$, then the only remaining possibility is that $3>0$.)  Our rules
enable us to do this, as follows (assuming, say, that you have just written
Step 698):  

\medbreak
\pline{(699)\ste $(3>0\vee 3<0)\Rightarrow ((\sim 3<0)
\Rightarrow 3>0)$. \hfill (Tautology $(P\vee Q)\Rightarrow((\sim Q)\Rightarrow P)$)}

\pline{(700)\ste $(\sim 3<0)\Rightarrow 3>0$. \hfill (Modus Ponens 
from (238) and (699))}

\pline{(701)\ste $3>0$. \hfill (Modus Ponens from (455) and (700))}

\medbreak\noindent At this point, you may ask ``Why did we pick this
particular tautology in Step 699?''          This question has two 
answers, depending on what you mean when you ask {\bf why}. 

\medbreak
\bi
\item{(A)} If by ``{\bf why?}'' you mean ``what allows you to do it?'' then the
answer is quite simple: {\bf because it is a tautology}, and one of our
rules allows us to bring in any tautology we want at any time. (Maybe you
will ask: how do I know that $(P\vee Q)\Rightarrow((\sim Q)\Rightarrow P)$
is a tautology?  First of all, if you don't believe it, you can check it
with truth tables.  Second, you should be able to ``see'' directly that it
is a tautology because all it says is that ``if one of two things is true
and the second thing isn't true, then the first thing must be true,'' which
is clearly true.  Third, you can check that $(P\vee Q)\Rightarrow((\sim
Q)\Rightarrow P)$ is a tautology without using truth tables, by just asking
yourself ``when would $(P\vee Q)\Rightarrow((\sim Q)\Rightarrow P)$ be
false?''  For this to happen, $P\vee Q$ must be true but $(\sim
Q)\Rightarrow P$ must be false. But $(\sim Q)\Rightarrow P$ can only be
false if $\sim Q$ is true but $P$ is false. But if $\sim Q$ is true then
$Q$ is false. So if $\sim Q$ is true but $P$ is false then both $P$ and $Q$
must be false.  But then $P\vee Q$ is false, and we have already said that
it must be true.  So it is impossible for $(P\vee Q)\Rightarrow((\sim
Q)\Rightarrow P)$ to be false.)

\medbreak
\item{(B)} If by ``{\bf why?}'' you mean ``what for?'' (that is,
``what is the purpose of picking this particular tautology?''), then the asnwer
is {\bf because I had done some strategic planning and I figured that this
tautology was precise what I needed.}     You can see that my planning 
was O.K. because it worked, and in Step 701 I got exactly what I wanted. 
\ei

\begin{center}
\fbox{
\begin{minipage}{14cm}
\vspace{1mm}
\begin{center}
{\bf AXIOMS}
\end{center}

\noindent {\bf Axioms} are statements that we accept as true. They are the
starting points of any mathematical reasoning.

Mathematicians like to have the smallest possible number of axioms. 
If something can be {\bf proved} from other axioms, then it is not nice to
add it as an axiom. But {\bf some} axioms are necessary to get
started. Otherwise, you cannot move anywhere. 

You should think of axioms as being similar to the starting positions
of a game such as chess.  The steps of a proof are like {\bf moves}, 
and the theorems one proves are like the positions that one can 
attain from the starting position by making various moves.
\vspace{1mm}
\end{minipage}
}
\end{center}

\begin{center}

\fbox{
\begin{minipage}{14cm}
\vspace{1mm}
\begin{center}
{\bf DEFINITIONS}
\end{center}

\noindent {\bf Definitions} function very much like axioms, so much so that
often it does not make any difference whether you call something an
``axiom'' or a ``definition.'' 

For example, later on, when we introudce axioms for the real number system, 
we will have at some point the following ``axiom-definition'': 
$$
(\forall x)(\forall y)(\forall z)(x-y=z\lto y+z=x)\,.  \eqno{(SUB)} 
$$
Is this an ``axiom''? Is it a ``definition''?  Or maybe it does not matter?

Let us see. You might, for example, have started with a language for the
real numbers in which the given symbols include $+$ and $=$ but not $-$.
In such a case, ``we don't have the $-$ symbol'' to begin with, and
we have to introduce it. We do so by means of Formula (SUB). So this
formula tells us what ``$-$'' means. Then (SUB) is the {\bf definition} of
$-$. Once we have this formula, every time we have a statement involving 
``$-$,''  we can {\bf eliminate} the $-$ symbol altogether. (We will 
do that many times later.)

Another point of view is possible. We might have started with a language
for the real numbers in which the given symbols include $+$ and $=$ and
also $-$.  So in this case ``we do have the $-$ symbol'' from the very
beginning, and there is no need to introduce it.  But we still have to say
something about how this symbol is related to all the others. So we take
Formula (SUB) as an {\bf axiom}. From this perspective, formula tells us an
important fact about ``$-$,'' but is not the definition. 

The important thing is that, whether (SUB) is regarded as an axiom or as a
definition, {\bf it is a formula that we can bring in as a step into a
proof any time we want}. This is what really matters about (SUB), and the
question whether it ``really'' is an axiom or a definition is much less
important.

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

\begin{center}
\fbox{
\begin{minipage}{14cm}
\vspace{1mm}
\begin{center}
{\bf HYPOTHESES}
\end{center}

\noindent{\bf Hypotheses} are statements that we {\bf assume} to be true 
in a particular situation.   

If you compare this with what we said about ``axioms'' in a previous box, 
you will see that the difference appears to be very slight.  In fact,
{\bf within a particular proof, hypotheses function exactly like 
axioms and definitions: they are statements that you are free to bring in
any time you want.}

There is, however, a big difference. Axioms are things that we take to be
true forever, because we believe they are true. Hypotheses are taken to be
true not because we believe they are true, but {\bf because we want to know
the consequences of their being true.}  On other words: we might want to
know what else would have to be the case, for example, if pigs had wings.
So we make the hypotheses that ``pigs have wings,'' by saying

\medbreak\noindent($\ldots$) $\qquad$ Assume pigs have wings, 

\medbreak and we then set out to explore its consequences. Or, if you
prefer, we set out to study an imaginary world in which pigs have wings and
try to understand what that world would have to be like. We could then
``prove'' all kind of ``theorems,'' such as

\medbreak THEOREM 1: {\it Pigs can fly}.

\medbreak THEOREM 2: {\it If a pigsty does not have a roof, then the 
pigs will fly away}. 

\medbreak All these theorems would be proved {\bf under the hypothesis}
that pigs have wings.  That is, we would never be saying that we have
proved that pigs can fly.  All we would be saying is that {\bf IF} pigs
had wings {\bf THEN} pigs could fly.  In other words, all the facts
we would ``prove'' about pigs under the ``pigs have wings'' hypothesis would
be valid {\bf in the imaginary world of pigs with wings}, which, in principle,
is not our real world.

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

\medbreak

\begin{center}
\fbox{
\begin{minipage}{14cm}
\vspace{1mm}
\begin{center}
{\bf ENTERING AND LEAVING IMAGINARY WORLDS}
\end{center}

\noindent When you assume something, you are setting 
out to explore an {\bf imaginary world}, namely, a world in which that thing
you are assuming is true. When can you leave that world and go back to the
real world, taking with you the things you have discovered in your
imaginary world? The answer is simple: if the thing you assumed is actually
true in the real world, then everything you proved {\bf under that
assumption} is true, because in that case the imaginary world really 
is the real world.  

Our rules of inference will capture this very obvious idea as follows: 

\bi
\item{} You will  be always be allowed to introduce anything you want as an
asumption, any time you want. 

\item{} When you do that, whatever you have proved will have been proved 
{\bf under your assumption}.

\item{} If, assuming $P$, you prove some other statement $Q$, then you will
be allowed to go back to ``the real world'' and assert there that 
$P\imply Q$.  

\item{} If, in addition, you can prove $P$, then the Modus Ponens rule will
allow you to go to $Q$.
\ei

In simpler terms: whatever you prove under the assumption $P$ will be
valid unrestrictedly (that is, without having to assume that you are under
the assumption $P$) if you can also prove $P$. 

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

\medbreak

\begin{center}
\fbox{
\begin{minipage}{14cm}
\vspace{1mm}
\begin{center}
{\bf PROOFS BY CONTRADICTION}
\end{center}

One of the most common reasons for assuming something is to prove it cannot
happen. In other words, you set out to explore the consequences of
something in order to prove it is impossible. This is called ``proof by
contradiction.'' We have already seen examples before: 
when we proved by contradiction that $\sqrt{2}$ is irrational, we 
assumed that $\sqrt{2}$ was rational, and ended up with an impossible fact,
namely, that a certain natural number would have to be both even and odd. 
That is, {\bf we set out to explore an imaginary world in which 
$\sqrt{2}$ was rational, until we saw that in this world impossible 
things would happen, and then we concluded that such a world could not
exist, so $\sqrt{2}$ has to be irrational.}

This should answer once and for all one of the most frequently asked 
students' questions: {\large{\bf How can I assume something if I don't know
it is is true?}} Or, even worse, {\large{\bf how can I assume something if I
know it is not true?}}

The answer is very simple: you assume something that you don't know to be
true because you want to find out what would happen if it was true. 
And often you assume it {\bf precisely in order to prove it is not true.}

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

\medbreak

\begin{center}
\fbox{
\begin{minipage}{14cm}
\vspace{1mm}
\begin{center}
{\bf THE THREE ``PROPOSITIONAL'' RULES}
\end{center}

\noindent The first three of our eight rules will tell you

\bi
\item{} that you can always bring in an instance of a tautology,

\item{} that from $P$ and $P\imply Q$ you can go to $Q$ (Modus Ponens), 

\item{} that, if assuming $P$ you prove $Q$, then you can go to $P\imply
Q$.
\ei
Using these rules, you can justify formally all kinds of things we do
in mathematical reasoning.

\medbreak
EXAMPLE 1. Suppose you have proved two statements, say $P$ and $Q$, and now
you want to get to the statement $P\wedge Q$.  You just bring in the
instance of tautology

$P\imply(Q\imply(P\wedge Q))\,\,,$ 

then use Modus Ponens once to conclude that 

$Q\imply(P\wedge Q)\,\,,$ 

and then use Modus Ponens again to conclude that $P\wedge Q$. 

\medbreak
EXAMPLE 2. Suppose you have proved $P\wedge Q$ and now
you want to get to $P$.  You just bring in the
instance of tautology

$(P\wedge Q)\imply P\,\,,$

and then use Modus Ponens to get $P$. 

\medbreak
EXAMPLE 3. ({\sl Proof by contradiction}.) Suppose you are trying to 
prove $P$. You know that one way to do that is to assume $\sim P$ and get a
contradiction. How is that justifed with our rules?  It's very easy!
Let us say that assuming $\sim P$ you get the contradiction $C$. By one of
our propositional rules, you can now go to $(\sim P)\imply C$. 
But then you bring in the instance of  tautology 
$((\sim P)\imply C)\imply P$, and hit it with Modus Ponens (using 
$(\sim P)\imply C$), and you get $P$, as desired. 

\medbreak(You may ask: why did I bring in this particular tautology here? 
The answer is ``because it works!'' How do I know it is a tautology?
That's easy. If you want to, you can do it with truth tables, but 
you can also see it directly. Just ask yourself: could 
$((\sim P)\imply C)\imply P$ ever be $F$? This could only happen 
if $(\sim P)\imply C$ is $T$ and $P$ is $F$.  But then 
$\sim P$ would be $T$, and since $(\sim P)\imply C$ is $T$ it would follow
that $C$ is $T$. But this is out of the 
question because $C$ is a contradiction.)

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


\bigbreak
\centerline{{\bf PROOFS WITHIN PROOFS}}

\medbreak\noindent There is one more thing you need to know, which is quite
easy to understand but somehow confuses many people:

\medbreak
\bi
\item{} {\sl Whenever you want, you can start a ``subproof,'' or ``proof within
a proof,'' in which you can make {\bf any assumptions you want}}.  However,
when you do that then all the things you prove are proved {\bf under those
assumptions}.  
\ei


\medbreak\noindent 
For example, suppose we are reading a mystery novel, and I am trying to
prove to you that it was Bob that murdered Bill.  Suppose we got to a point
where I have established that the murderer must have been Bob or John.  Now
I want to convince you that it's not John, so it must have been Bob.

Here is one thing I could say: ``Suppose John murdered Bill.  We know that
Bill's body was found in his house, so the killing must have taken place in
the house itself, or nearby, because even if the body had been moved it
still couldn't have been moved very far. So John must have been in or near
Bill's house at the time of the murder. But Bill was killed on September 8
between 9 and 10 p.m.  EST.  So John must have been in or near Bill's house
on September 8 between 9 and 10 p.m.  EST.  On the other hand, we know that
John gave a public lecture in San Diego on September 8, starting at 6
p.m. Pacific time, i.e.  at 9 p.m. EST. So he must have traveled from New
York to San Diego in one hour or less, which is impossible. So John did not
murder Bill.''

Notice that what we did here is construct, within our main proof that Bob
is the murderer, a ``subproof,'' or ``proof within a proof,'' whose goal is
to prove that John is not the murderer.  We did this by {\sl introducing a
new hypothesis}, namely, by assuming that John is the murderer.  In other
words, {\sl we created and set out to explore an imaginary world}, in which
John did indeed kill Bill, in order to find out what are the consequences
and ramifications of the new hypothesis.  In this imaginary world, we
proved a number of things, such as, for example, that ``John traveled from
New York to San Diego in one hour or less.''  But we proved these things
{\sl under the hypothesis that John killed Bill}.  In order words, we did
not really prove that ``John traveled from New York to San Diego in one
hour or less,'' but only that this must have been so {\sl if John killed
Bill.}

The ultimate consequence of our ``proof within a proof'' is that 
this world we have imagined, in which John killed Bill, is impossible,
because in this world something impossible happened.   So we get out of
this ``proof within a proof'' the conclusion that {\sl John did not kill
Bill}. And {\sl this conclusion no longer depends on the new hypothesis
that ``John killed Bill.''}   The final conclusion, that 
{\sl John did not kill Bill}, is valid {\sl without any extra hypotheses},
so it is part of our main proof.    

In our mathematical formalism, we will be allowed to start a ``proof within
a proof'' any time we want, by assuming anything we want.  However,
anything we prove will only be part of this ``proof within a proof.''
There will be rules telling us how to get out of the ``proof within a proof'' 
and go back to the main proof.  The most important one is the following: 

\medbreak\noindent{{\bf RULE 3.}}\ \ {\sl If assuming $P$ you get to $Q$,
then you can go, without assuming $P$, to $P\Rightarrow Q$.}

\medbreak For example, suppose you are writing a proof and you already got, 

\medbreak
\pline{(3591)\ste $P\Rightarrow Q$
\hfill($\ldots\ldots\ldots\ldots\ldots\ldots\ldots$)}

\pline{(4507)\ste $Q\Rightarrow R$.  
\hfill($\ldots\ldots\ldots\ldots\ldots\ldots\ldots$)}

\medbreak\noindent Suppose you just finished writing 
Step 6812, and now you want to prove
$P\Rightarrow R$.  Here is one thing you could do:

\medbreak
\pline{(6813.\&)\ste\ste  Assume $P$.\hfill  (Preparation to apply
Rule 3)} 

\pline{(6814.\&)\ste\ste  $Q$.\hfill  (Modus Ponens from (3591) and 
(6813.1))}

\pline{(6815.\&)\ste\ste  $R$.\hfill  (Modus Ponens from (4507) and 
(6814))}

\pline{(6816)\ste $P\Rightarrow R$.\hfill  (Rule 3, from (6813) and
(6815))}

\medbreak\noindent Steps 6813, 6814, 6815 constitute a ``proof
within a proof,'' in which you introduce the new assumption $P$, and under
this assumption you prove first $Q$ and then $R$. Then in Step 
6816 you go back to the main proof, using Rule 3.  

Notice that we have used {\bf extra indentation and a \&} to indicate that
we are writing a proof within a proof.  The way we have organized our proof
makes it clear that {\sl at no point are we proving $Q$ or $R$}. We are
proving $Q$ and $R$ {\sl under the assumption $P$}, from which we can
conclude that $P\Rightarrow R$, as we do in Step 6816.  For all we know,
{\sl $Q$ and $R$ could perfectly well be false}, and nothing in what we
wrote says otherwise.  All our ``proof within a proof'' says is that {\sl
if you assume that $P$ is true, then $Q$ and $R$ must be true.}  The
``proof within a proof'' tells us nothing about what happens if $P$ is
false. And our final conclusion, that $P\Rightarrow R$, is of course valid
if $P$ is false.

There is another way to start a ``proof within a proof,'' by {\sl
introducing an arbitrary constant}.  For example, suppose you want to prove
that ``if you take a natural number and add it to its square, then the
result is an even number.'' (Symbolically, assuming that your universe of
discourse is $\nn$, the set of natural numbers: $(\forall n)(2|n^2+n)$.)
Then you could say: ``let us pick an {\bf arbitrary} natural number and let
us call it $k$. I will show that $k^2+k$ is even.  There are two
possibilities, namely, that $k$ is even and that $k$ is odd. If $k$ is even
then $k^2$ is also even, so $k^2+k$ is even, because the sum of two even
numbers is even. If $k$ is odd then $k^2$ is also odd, and then $k^2+k$ is
even, because the sum of two odd numbers is even.  So we have seen that in
all possible cases $k^2+k$ must be even.  So we have proved $(\forall
n)(2|n^2+n)$.''

Notice that here we introduced a new letter $k$, which serves as the name
of a number that is {\sl fixed} throughout our analysis, until we get to
the final step, in which we say that, since what we did was O.K.  no matter
what $k$ was, then we have shown that $(\forall n)(2|n^2+n)$.  
In our ``proof within a proof,'' the letter $k$ is treated as a constant.    

We could organize this as follows (assuming, say, that we just 
wrote step 4289:

\medbreak
\pline{(4290.\&)\ste\ste\ \  Let $k$ be arbitrary.\hfill
(Preparation to apply Rule 5)} 

\centerline{$\cdots\cdots\cdots\cdots$}

\centerline{$\cdots\cdots\cdots\cdots$}

\centerline{$\cdots\cdots\cdots\cdots$}

\pline{(4365.\&)\ste\ste($k$ is even)$\vee$($k$ is odd).\hfill
(\ $\cdots\cdots\cdots\cdots$\ )} 

\pline{(4366)\ste $(\forall n)\Biggl((n$ is even$)\vee(n$ is
odd$)\Biggr)$.\hfill (Rule 5, from (4290) and (4365))}

{\bf
When we start a subproof by introducing a letter by saying ``let such and
such be arbitrary,'' then this has automatically the effect of declaring
that letter to be a constant for this subproof.} But, {\bf this declaration
is ``local,'' that is, valid within the subproof only.  Once the subproof
is finished, then the effect of this declaration is undone.}

\newpage

\begin{center}
{\Large{\bf BASIC INFERENCE RULES FOR PROOFS}}

\end{center}

\medbreak\noindent Finally, we are ready to give a truly precise definition
of proof. A {\bf proof} is a list of {\bf statements}, each one accompanied
by a {\bf justification}. 

We now list the conditions telling us when a step in a proof is valid: 

\begin{center}

\fbox{\fbox{

\begin{minipage}{5.2in}

\vspace{1mm}

\begin{center}

{\large{\bf WHAT IS PERMITTED IN A PROOF?}}

\end{center}

\bi\item[]\bi
\item[(P.a)] It is always permitted to bring in an 
{\bf axiom} (or ``postulate'') as a new step.  

\item[(P.b)] It is always permitted to bring in one of the {\bf hypotheses}
as a new step.

\item[(P.c)] It is always permitted to bring in a {\bf definition}
as a new step. 

\item[(P.d)] It is always permitted to bring in as a new step
something that follows from previous steps by {\bf applying a valid 
rule of inference}.

\item[(P.e)] It is always permitted to start a proof within a proof
by either

\bi
\item[-] introducing any statement you want  as an assumption, 
\ei
or
\bi
\item[-] bringing in a {\bf new} letter as an arbitrary constant.
\ei
or
\bi
\item[-] bringing in a {\bf new} letter assumed to satisfy some condition,
provided it has been proved that something satsifying that condition exists.

\ei
However, whatever is proved  after this is done, is only valid in the
``proof within a proof'', and one can only get out of it by applying Rule 3
or Rule 5  or Rule 6.
\ei\ei

\vspace{1mm}

\end{minipage}
}}
\end{center}


\medbreak\noindent Now, to wrap this up, I have to tell 
you what our {\bf rules of inference} are. But, before I do that, I have to
take care of an unpleasant and boring but important detail. 

Suppose you have a formula such as $x+3=7-x$, and you call it $p(x)$. Suppose
$a$ is a constant. What do we mean by ``$p(a)$''?  Obviously, we mean
``$a+3=7-a$,'' right?  For example, $p(2)$ is the formula ``$2+3=7-2$,'' so
$p(2)$ is true.  This suggests an obvious possibility: 

\bi
\item[(A)] If $p(x)$ is a formula, and $a$ is a constant, 
then by $p(a)$ we mean the formula obtained by substituting 
$a$ for $x$ wherever $x$ occurs. 
\ei 
That sounds quite easy. Unfortunately, things are not so simple. 

Suppose for example that $p(x)$ was the formula 
$x+3=7-x\wedge(\exists x)(x+3=8)$.  What exactly do we mean by ``$p(a)$''?  
Perhaps we mean 
$$
a+3=7-a\wedge(\exists a)(a+3=8)\,\,. \eqno{(\#)} 
$$
But this is ridiculous, because $a$ is a constant, so we cannot say 
``$(\exists a)$.'' (For example, what on Earth would 
``$2+3=7-2\wedge(\exists 2)(2+3=8)$'' mean?)  

So maybe $p(a)$ should be 
$$
a+3=7-a\wedge(\exists x)(a+3=8)\,\,,\eqno{(*)} 
$$
or 
$$
a+3=7-a\wedge(\exists x)(x+3=8)\,\,,\eqno{(\&)} 
$$
Actually, ($\&$) is the most reasonable choice, because, as we said 
earlier, when we write the formula ``$(\exists x)(x+3=8)$'' the variable 
$x$ is ``bound'' (or ``dummy''), which means that 
``$(\exists x)(x+3=8)$'' is ``really the same'' as
``$(\exists y)(y+3=8)$,'' so ``there really is no $x$ there.'' 

But then, {\bf if we want to adopt ($\&$) as the correct meaning of $p(a)$ 
when $p(x)$ is ``$x+3=7-x\wedge(\exists x)(x+3=8)$,'' then 
we can no longer take (A) to be correct, because (A) inexorably leads us 
to ($\#$), which is nonsense.}

In order to avoid these problems, {\bf we will limit our use of the
substitution of a constant $a$ for a variable $x$ to formulas $p(x)$ where
is no quantifier involving $x$ anywhere.}

\bigbreak\noindent
Now, finally, we are ready to list the rules. 
There are exactly {\large{\bf EIGHT}} of them. Here
they are. 

\rulo You are allowed to bring in any statement which is
an instance of a tautology.

\rulo If you have $p$ and $p\imply q$ then you can go to $q$. 
(This is called {\it Modus Ponens}).

\rulo If $p$ is any statement whatsoever, then you are allowed to start a
subproof (i.e. to go to level $k+1$, if you are at level $k$, and start a
``proof within a proof'')  by saying ``Assume $p$.'' If in
that  subproof you get to a statement $q$ (that is, if you prove $q$ under
the assumption $p$), then you can get out of the subproof 
and carry $p\imply q$ to the level $k$ proof. 

\rulo Suppose $p(x)$ is a formula where there is no quantifier 
involving $x$, $a$ is a letter, and 
$p(a)$ is what you get from $p(x)$ 
by substituting $a$ for $x$ in {\bf all} the occurrences of $x$ in
$p(x)$. Then, if you have $(\forall x)p(x)$ and $a$ has been 
declared to be a constant, you can go to $p(a)$. 
(This is called {\it specialization}.)

\rulo Suppose $p(x)$ is a formula where there is no quantifier involving
$x$, $a$ is a letter, and $p(a)$ is what you get from $p(x)$ by
substituting $a$ for $x$ in {\bf all} the occurrences of $x$ in $p(x)$.
Suppose the letter $a$ has not appeared before.  Then you are allowed to
start a subproof (i.e. to go to level $k+1$, if you are at level $k$, and
start a ``proof within a proof'') by saying ``Let $a$ be arbitrary.''  This
effectively declares $a$ to be a constant, locally, within the ``proof
within a proof.'' If in
this subproof you get to $p(a)$ (that is, if you prove $q$ under the
assumption that $a$ is arbitrary), then you can get out of the subproof and
carry $(\forall x)p(x)$ to the level $k$ proof.

\noindent COMMENT: Naturally, instead of ``$a$'' you could use
``$b$,'' or ``$z$,'' or ``$\alpha$,'' or ``$\beta$,'' or ``$\aleph$,'' or
``$\diamond$,'' or any symbol you want.  What is important is that what you
do should apply to a {\it completely arbitrary} object in our universe of
discourse. Otherwise, you will not be proving that $p(x)$ is true for {\it
all} $x$.  For example ---if our universe of discourse is ${\bf R}$--- it
would not be O.K. to prove that $(\forall x) (\exists y)(y^2=x)$ by saying
``Let $9$ be arbitrary.  Then $(\exists y)(y^2=9)$ is true, so we have
proved that $(\forall x) (\exists y)(y^2=x)$.''  What is wrong here? What
is wrong is that $9$ is not an {\it arbitrary} real number. $9$ is $9$, and
just because something is true for the number $9$ it doesn't mean that it
is true for {\bf all} real numbers.

\rulo Suppose $p(x)$ is a formula where there is no quantifier 
involving $x$, $a$ is a letter, and $p(a)$ is what you get from $p(x)$ by
substituting $a$ for $x$ in {\bf all} the occurrences of $x$ in
$p(x)$. Suppose the letter $a$ has {\bf not} appeared before.
Suppose you already have $(\exists x)p(x)$. 
Then you are allowed to
start a subproof (i.e. to go to level $k+1$, if you are at level $k$, and
start a ``proof within a proof'') by introducing a new object, calling it $a$,
and stipulating that $p(a)$.  This effectively declares $a$ to be a,
locally, within the ``proof within a proof.'' If in
this subproof you get to a statement $q$ that does {\sl not} contain $a$,
(that is, if you prove $q$ under the assumption that $a$ satisfies 
$p(a)$, but $q$ itself does not contain $a$), 
then you can get out of the subproof and
carry $q$ to the level $k$ proof.

\medbreak\noindent COMMENT: Here {\bf it's important that this new object
should be given a name that has not been used before.} For example, suppose
$p(x)$ stands for ``$x$ killed Polonius,'' and our universe of discourse is
the set of all people.  Suppose you are told that $(\exists x)p(x)$,
i.e. that somebody killed Polonius.  Then you can introduce a name for this
individual.  You can call him/her $a$ or, if you prefer, ``the killer,'' in
which case you would be able to say that $p(a)$, or that $p({\rm
the\,\,killer})$.  But you cannot say ``let's call this person Hamlet,'' or
``let's call him Laertes,'' because Hamlet and Laertes are names of
characters that have already appeared in the play. If you call the killer
``Hamlet'' or ``Laertes'' then you would be {\it prejudging}, and declaring
that $p({\rm Hamlet})$, i.e. that Hamlet killed Polonius, or that $p({\rm
Laertes})$, i.e. that Laertes killed Polonius. One of these happens to be
true, and the other one is false, but in either case you cannot just
conclude that it is true by merely choosing a name for the killer.

If you want a more mathematical example: suppose you prove that $1+1$ 
exists (that is, you prove that $(\exists x)(1+1=x)$). Suppose then 
that you decide to introduce a constant as in our rule, but you make the
stupid mistake of calling this constant $1$.  Then you would get $1+1=1$,
and from that you can prove anything you want! So you will have introduced
an {\bf inconsistency} and destroyed all your previous work!

\rulo Suppose $p(x)$ is a formula where there is no quantifier 
involving $x$, $a$ is a letter, and 
$p(a)$ is what you get from $p(x)$ 
by substituting $a$ for $x$ in {\bf all} the occurrences of $x$ in
$p(x)$.   Then from $p(a)$ you can go to 
$(\exists x)p(x)$.  

\rulo You can substitute equals for equals.  That is, 
if $t$ and $s$ are constant terms, 
and you have proved that $t=s$, then you can go from a statement involving 
$t$ to the statement in which $s$ is substituted for $t$ 
in all or some of its ocurrences, and from a statement involving 
$s$ to the statement in which $t$ is substituted for $s$ 
in all or some of its ocurrences.


\sepa

\medbreak

\begin{center}
{\large{\bf EXAMPLES ILLUSTRATING THE USE OF RULE 8}}
\end{center}

\medbreak

\bi
\item[1.] If $a$ and $b$ are constants and you have proved 
$a=b$ and $a.c=a.c$, then you can go to  
$a.c=b.c$.  

\item[2.] After you have given the definition
$$
[0,1]=\{x:0\le x\le 1\}\,,
$$
you can go from
$a\in [0,1]$ to $a\in\{x:0\le x\le 1\}$, by substituting 
``$\{x:0\le x\le 1\}$'' for ``$[0,1]$'' in 
``$a\in [0,1]$.'' 

\item[3.] After you have given the definitions
$$
2=1+1\,,
$$
and 
$$
3=2+1\,,
$$
you can go\footnote{A truly nitpicking student could (and should)
object to this.  Strictly speaking, when you substitute
``$1+1$'' for $2$ in ``$3=2+1$'',  what you get is 
``$3=1+1+1$'', not ``$3=(1+1)+1$.''   If you really want to get 
``$3=(1+1)+1$'', then you should have used ``$3=(2)+1$.''  
This is one of many examples of the annoying complications created by the
use of parentheses. The issue {\bf cannot be ignored.} For example, if you
were writing a computer program to check proofs, then the issue would come
up: if you program Rule 8 into the computer carelessly, 
then the computer would not accept ``$3=(1+1)+1$'' as arising from 
the susbtitution of ``$1+1$'' for $2$ in ``$3=2+1$''.}
\ei



\sepa

\begin{center}
{\bf AN EXAMPLE}
\end{center}

\medbreak\noindent Suppose $p$ is a two-variable predicate letter. 

\medbreak\noindent THEOREM: $(\exists y)(\forall x)p(x,y)
\imply (\forall x)(\exists y)p(x,y)$.

\medbreak\noindent PROOF:

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

\noindent(2.\&.\&) \stetw Let $a$ be such that $(\forall
x)p(x,a)\,.$\hfill[Preparation to apply Rule 6, from (1.1)]

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

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

\noindent(5.\&.\&.\&) \stetw $(\exists y)p(b,y)\,.$\hfill[Rule 7, from (4)]

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

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

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

$\,\,\,$\hfill{\bf QED}

\medbreak\noindent COMMENT: Can you prove 
the converse of the above theorem, that is 
$$
(\forall x)(\exists y)p(x,y)\imply(\exists y)(\forall x)p(x,y)\,\,?
$$
If our rules are any good, then you should {\bf not} be able to prove it,
because you know that this is not logically valid.  (If everybody 
eats something, it does {\bf not} mean that there is something that's eaten by
everybody!)


\medbreak\noindent You should try to prove this, and see by yourself 
why you cannot do it. 

\medbreak\noindent Here is one possible attempt:

\medbreak

\noindent(1.\&) \stef Assume $(\forall x)(\exists y)p(x,y)\,.$

\noindent(2.\&.\&) \stef Let $b$ be arbitrary.

\noindent(3.\&.\&) \stef $(\exists y)p(b,y)\,.$\hfill[Rule 4]

\noindent(4.\&.\&.\&) \stef  Let $a$ be such that $p(b,a)\,.$\hfill[Preparation
to apply Rule 6, from (3)]  

\medbreak\noindent And now you are stuck! You are in level 4, and you
entered it by introducing $a$. So the only way to get out and go back to
level 3 would be to apply Rule 6. For that you need to prove something that
does not involve $a$.  You could, of course, go to $(\exists
y)p(b,y)$. That would indeed get you out of level 4, but you would not have
gained anything, because you already had $(\exists y)p(b,y)$ anyhow, in
step (3).  (This is called ``going around in circles.'' It's not a very
useful thing to do if you actually want to {\bf get} somewhere!)

What else could you do?  It would be nice if you could go to 
$(\forall x)p(x,a)$, because then you would apply Rule 7 and write
$(\exists y)(\forall x)p(x,y)$, which is exactly what you want. 
But you {\bf cannot} go to $(\forall x)p(x,a)$, because Rule 5 tells you
that, if you start a subproof with ``Let $b$ be arbitrary'' and then 
prove $q(b)$ {\bf in the same level} then you can carry $(\forall x)q(x)$ 
to the previous level. Here you have proved $p(b,a)$ in level 4, whereas 
you introduced $b$ as an arbitrary constant in level 3. 

Notice that this restriction, that you cannot prove $q(b)$ in a deeper
level and then use it in the higher level, is very much in agreement with
common sense.  To prove $(\forall x)q(x)$ you have to be able to prove
$q(b)$ for a completely arbitrary $b$, that is, a $b$ that could be
absolutely anything. If you go to a deeper level, you will be introducing a
new assumption, so $b$ will no longer be completely arbitrary. (Example:
let us prove that all real numbers are equal to $47$.  Proof: let $a$ be
arbitrary. Assume that $a=47$. Then $a=47$ and, since $a$ was arbitrary, we
can conclude that $(\forall x)(x=47)$.  Ridiculous, isn't it?  QUESTION:
how does this ``proof'' violate our rules?)

\medbreak
\begin{center}
{\sl (to be continued)}
\end{center}


\end{document}

\end
