\section{Proof examples}

\forstudents{\reading{Velleman Chapter 3, Rosen, Section 3.1}}

This section contains some examples of proofs using the deduction rules
described above.  They are presented at about the level of detail commonly used by 
mathematicians.  The examples illustrate basic methods: 
direct proof, proof by contradiction, and proof by cases.

These proofs are written in a stylized way, using statements and
reasons (as in high school geometry proofs).
In math books, proofs are usually presented in prose, with the 
logical structure left implicit.  Caution: 
The proof writer is expecting the reader to figure out the logical
structure.  To understand the proofs, you really have to do this. 
                                %It should always be possible to rewrite any of these proofs in
                                %structured form (given enough time).  
\subsection{Direct proof}

To prove that a proposition of the form $P \Rightarrow Q$ is true, it
is enough to assume $P$ and show $Q$.  Written in a structured style,
the pattern of such a proof is:
\begin{structproof}
  Prove:  $P \Rightarrow Q$ \\
  1. Assume $P$. \\
  2. $Q$ \\
  3. QED 
  \> \> \> \> \> Implication \\
\end{structproof}
QED stands for Quod Erat Demonstrandum, Latin for ``which was to be
proved''.  Here, it's a shorthand for writing the goal out again as
the final step.  In paragraph proofs, you often just write a box:
$\qed$

\begin{example} 
  Let's prove that the sum of the first 100 numbers, $1 + ... + 100$,
  is 5050.    We'll rewrite this as an implication and use the direct proof rule
  above.

  \begin{proofoverhead}
    Prove:  $S = 1 + ... + 100 \Rightarrow S = 5050$. \\
    1. Assume  $S = 1 + ... + 100$. \\
    2. $S = 5050$ 
    \> \> \> \> \> ??? \\
    3. QED  (That is, $S = 1 + ... + 100 \Rightarrow S = 5050$.) 
    \> \> \> \> \> Implication 
  \end{proofoverhead}

  Of course, the interesting part is to fill in the ???.  This needs
  some calculations:

  \begin{proofoverhead}
    Prove:  $S = 1 + ... + 100 \Rightarrow S = 5050$. \\
    1. Assume  $S = 1 + ... + 100$. \\
    2. $S = 5050$ \\
    \> 1. $S = 100 + 99 +...+ 1$  
    \> \> \> \> Commutativity of addition \\
    \> 2. $2S = 101 + 101 + ... + 101$  (100 terms) 
    \> \> \> \> Add term-by-term \\
    \> 3. $2S = 10,100$           
    \> \> \> \> Add the terms up \\
    \> 4. QED  (That is, $S = 5050$.) 
    \> \> \> \> Divide by 2 \\
    3. QED ($S = 1 + ... + 100 \Rightarrow S = 5050$.) 
    \> \> \> \> \> Implication 
  \end{proofoverhead}
\end{example}

\begin{example}
  The following argument shows a property of basic set theory.    It says that, if an element $x$ is in the complements of sets $A$ and
  $B$, then it is in the complement of their union.    Like the previous proof, this one involves a direct, step-by-step
  calculation.
  \begin{tabbing}
    XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
    Prove: $x \in \bar{A} \cap \bar{B}  \Rightarrow x \in \bar{A \cup  B}$ \\
    1. Assume $x \in \bar{A} \cap \bar{B}$ \\
    2. $x \in \bar{A}$, $x \in \bar{B}$ 
    \> \> \> \> \> Definition of intersection \\
    3. $x \notin A$, $x \notin B$ 
    \> \> \> \> \> Definition of complement \\
    4. $x \notin A \cup B$ 
    \> \> \> \>  \> Definition of union \\
    5. $x \in \overline{A \cup  B}$  
    \> \> \> \> \> Definition of complement \\
    6. QED ($x \in \bar{A} \cap \bar{B}  \Rightarrow x \in \bar{A \cup  B}$) 
    \> \> \> \> \> Implication 
  \end{tabbing}
\end{example}

\subsection{Proof by contradiction}

To prove that a proposition $P$ is true, it is enough to prove that 
$\neg P \Rightarrow \ms{false}$. The pattern is: 
\begin{structproof}
  Prove:  $P$ \\
  1. $\neg P \Rightarrow \ms{false}$ \\
  2. QED   
  \> \> \> \> \> Contradiction
\end{structproof}

\noindent
Some variants of this:

\begin{structproof}
  Prove: $P$ \\
  1. $\neg P \Rightarrow (Q \wedge \neg Q)$ \\
  2. QED 
  \> \> \> \> \> Contradiction \\
  \\
  \\
  Prove: $P$ \\
  1. $\neg P \Rightarrow Q$ \\
  2. $\neg Q$ \\
  3. QED       
  \> \> \> \> \> Contradiction \\
\end{structproof}

\begin{example} Let's prove that the average of two numbers is always
  less than their maximum.
\begin{structproof}
Prove: $\frac{a+b}{2} \le \max(a,b)$\\
1. $\frac{a+b}{2} > \max(a,b) \implies \ms{false}$\\
\> 1. Assume $\frac{a+b}{2} > \max(a,b)$
     \> \> \> \> For $P \implies Q$, Assume $P$, prove $Q$ \\
\> 2. \ms{false}\\
\> \> 1. $\frac{a+b}{2} > a$
      \> \> \> Definition of max \\
\> \> 2. $\frac{a+b}{2} > b$
      \> \> \> Definition of max \\
\> \> 3. $\frac{a+b}{2}+\frac{a+b}{2} > a+b$
      \> \> \> Add previous inequalities \\
\> \> 4. $a+b > a+b$
      \> \> \> Simplify \\
\> \> 6. QED
      \> \> \> Actually $a+b=a+b$ \\
\> 3. QED
      \> \> \> \> Showed $P \implies \ms{false}$ \\
2. QED  \> \> \> \> \> Contradiction \\
\end{structproof}
\end{example}

\comment{
\begin{example}
  \mbox{}
  \begin{structproof}
    Assume: If Richard gets at least four hours of sleep then he passes his 
    6042 final. \\
    Richard fails his 6042 final. \\
    Prove: Richard gets less than four hours of sleep.
  \end{structproof}

  \noindent
  Here, let $P= \mbox{``Richard gets less than four hours sleep.''}$.    $Q= \mbox{``Richard passes.''}$. So the proof steps for proving $P$ are:

  \begin{structproof}
    Prove: Richard gets less than four hours of sleep. \\
    1. If Richard gets at least four hours of sleep then he passes. 
    ($\neg P \Rightarrow Q$). \\
    \> \> \> \> \> Assumed \\
    2. Richard fails ($\neg Q$). 
    \> \> \> \> \> Assumed \\
    3. QED (Richard gets less than four hours of sleep.) 
    \> \> \> \> \> Contradiction 
  \end{structproof}
\end{example}
}

\begin{example}
  A more interesting proof by contradiction.    \begin{structproof}
    Prove: $\sqrt{2}$ is irrational.\\
    1. $\sqrt{2}$ rational $\Rightarrow \ms{false}$ \\
    2. QED 
    \> \> \> \> \> Contradiction. 
  \end{structproof}
  Assume it's rational, play with the definitions, and try to get a
  contradiction. 

  \begin{proofoverhead}
    Prove: $\sqrt{2}$ is irrational. \\
    1. $\sqrt{2}$ rational $\Rightarrow \ms{false}$ \\
    \> 1. Assume $\sqrt{2}$ rational. \\
    \> 2. $\ms{false}$ \\
    \> \> 1. Choose $a, b \in N^{+}$, $\sqrt{2} = \frac{a}{b}$, lowest terms.
    \> \> \> Basic property of rationals. \\
    \> \> 2. $2 b^2 = a^2$       
    \> \> \> Algebra \\
    \> \> 3. $a^2$ is even.
    \> \> \> Definition of ``even'' \\
    \> \> 4. $a$ is even. \\   
    \> \> 5. Choose $c \in N$, $a = 2c$. \\
    \> \> 6. $4 c^2 = a^2 = 2b^2$ 
    \> \> \> Algebra \\
    \> \> 7. $2 c^2 = b^2$       
    \> \> \> Algebra \\
    \> \> 8. $b^2$ is even.
    \> \> \> Definition of ``even'' \\
    \> \> 9. $b$ is even. \\
    \> \> 10. $a$ and $b$ aren't in lowest terms. 
    \> \> \> 1.2.4, 1.2.9 \\
    \> \> 11. QED ($\ms{false}$) 
    \> \> \> 1.2.1, 1.2.10, propositional logic \\
    \> 3.  QED ($\sqrt{2}$ rational $\Rightarrow \ms{false}$) 
    \> \> \> \> Implication \\
    2. QED  ($\sqrt{2}$ is irrational) 
    \> \> \> \> \> Contradiction
  \end{proofoverhead}

  Some steps aren't justified here: 
  \begin{itemize}
  \item
    Showing that $a$ and $b$ are even, because we know their squares
    are even.
  \item
    Some other points involving quantifier logic.
  \end{itemize}
  We may revisit this later to fill in the gaps.
\end{example}

\subsection{Proof by cases}

To prove that a proposition $P$ is true, it is enough to prove that
$Q$ and $\neg Q$ both imply $P$, where $Q$ is any other proposition.  This shows $P$ is true in either case, so it's always true.

\begin{structproof}
  Prove: $P$ \\
  1. $Q \Rightarrow P$ \\
  2. $\neg Q \Rightarrow P$ \\
  3. QED                     
  \> \> \> \> \> Cases 
\end{structproof}

\noindent This generalizes to any number of
predicates, provided that together they cover all possibilities.  If
$Q_1 \vee Q_2 \vee \ldots \vee Q_k$ is always true, and you can show
each $Q_i$ implies $P$, then you can infer $P$.
\begin{example}
  \mbox{}
  \begin{structproof}
    Assume: $d =$ your birth date (day of month, 1-31). \\
    Prove: $d^2 + d$ is even. \\
    1. $d = 1 \Rightarrow d^2 + d = 2 \mbox{ is even}$. \\
    2. $d = 2 \Rightarrow d^2 + d = 6 \mbox{ is even}$. \\
    3. $\ldots$ \\
    31. $d = 31 \Rightarrow d^2 + d=992 \mbox{ is even}$. \\
    32. QED ($d^2 + d$ is even.)
    \> \> \> \> \> Cases 
  \end{structproof}
  More clever proofs than this one might consider fewer cases.    For example, can we just consider whether $d$ is even or odd?
\end{example}

\begin{example}
  This example combines an argument by contradiction and an
  argument by cases.    \begin{structproof}
    Prove:  There are infinitely many prime numbers. \\
    1. Assume there are only finitely many prime numbers. \\
    2. $\ms{false}$ \\
    \> 1. Choose $P$ to be the finite set of all prime numbers, and define 
    $m$ to be $1 + \Pi_{p \in P} p$. \\
    \> 2. $m$ isn't in $P$. 
    \> \> \> \> It's larger than all the elements of $P$. \\
    \> 3. $m$ isn't divisible by anything in $P$. 
    \> \> \> \> Remainder is $1$ for any such division. \\
    \> 4. There is some prime that isn't in $P$. \\
    \> \> 1. If $m$ is prime then there is some prime that isn't in $P$. \\
    \> \> \> \> \> $m$ is an example. \\
    \> \> 2. If $m$ is not prime then there is some prime that isn't in $P$. \\
    \> \> \> 1. Assume $m$ is not prime. \\
    \> \> \> 2. $m$ has a prime divisor. 
    \> \> Number theory fact \\
    \> \> \> 3. Choose $q$ to be a prime divisor of $m$. \\
    \> \> \> 4. $q$ isn't in $P$ 
    \> \> $m$ is divisible by $q$, but not by any $p \in P$. \\
    \> \> \> 5. There is some prime that isn't in $P$. \\
    \> \> \> 6. QED 
    \> \> Implication \\
    \> \> 3. QED (There is some prime that isn't in $P$.) \\
    \> \> \> \> \> Cases \\
    \> 3. QED ($\ms{false}$) \\
    3. QED (Infinitely many primes)
    \> \> \> \> \> Contradiction
  \end{structproof}
  We may prove the missing number theory fact later in the course.    Again, some arguments about quantifiers are made informally, so we may
  want to return to these after we study quantifier logic.
\end{example}

\section{Good proofs}

Some features of good proofs:
\begin{itemize}
\item
  They must be {\em correct\/}.
\item
  They should be clear and understandable.
\item
  They should have nice structure: They should be broken up into pieces
  that prove key intermediate properties (lemmas).  (This makes them
  easier to understand, and possibly reusable.)
\item
  They should be written fairly generally and abstractly, so they apply to
  many cases. 
\item
  Don't leave gaps, saying something is obvious when it isn't.
\item
  Elegant, economical,...
\end{itemize}
Notice that many of these are also features that we look for in 
good programs.
