
\section{Predicate reasoning examples}

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

We have already used quantifiers in sloppy ways\. Now we more carefully
 point out uses of quantifier reasoning.

\subsection{Birthdate}

This example illustrates: Quantifier reasoning (UG, EI, EG)

Before we did a proof by cases that $d^2 + d$ is even for any
birthdate $d$\.
We can generalize this so it talks about all natural numbers, not just 1-31.
\begin{structproof}
Prove: $\forall n \in N (n^2 + n \mbox{ is even})$. \\
1. Fix $n \in N$. \\
2. $n^2 + n$ is even. 
\> \> \> \> \> ??? \\
3. QED  
\> \> \> \> \> Universal Generalization (UG) 
\end{structproof}
UG says, to show something is true for all elements of a set ($\forall$), 
you pick (``fix'') any arbitrary generic element and show it for that\.
The general pattern for using UG is:
\begin{structproof}
Prove: $\forall x \in X (P(x))$. \\
1. Fix $x \in X$. \\
2. $P(x)$ \\
3. QED  
\> \> \> \> \> Universal Generalization (UG) 
\end{structproof}
You've shown that for any $x$ someone gives you, you can write a proof
for that $x$\.  So the claim is true for every $x$\.  The name is
weird; just remember the method\.

Now back to the proof\.  To show step 2, we can use cases: 
\begin{proofoverhead}
Prove: $\forall n \in N (n^2 + n \mbox{ is even})$. \\
1. Fix $n \in N$. \\
2. $n^2 + n$ is even. \\
\> 1. If $n$ is odd then $n^2 + n$ is even.    
   \> \> \> \> ??? \\
\> 2. If $n$ is even then $n^2 + n$ is even.   
   \> \> \> \> ??? \\
\> 3. QED                                      
   \> \> \> \> Cases \\
3. QED 
\end{proofoverhead}

Now fill in steps for the even case\.
This assumes a definition of ``even'' for a natural number, which says
that the number is expressible as $2x$ for some natural number $x$. 
\begin{proofoverhead}
\> 2. If $n$ is even then $n^2 + n$ is even.   \\
\> \> 1. Assume $n$ is even. \\
\> \> 2. $n^2 + n$ is even. \\
\> \> \> 1. $\exists x \in N (n = 2x)$ 
         \> \> Definition of ``even'' \\
\> \> \> 2. Choose $x \in N$, $n = 2x$ 
         \> \> Existential Instantiation (EI) \\
\> \> \> \> \> (If there {\em exists\/} one, you can {\em choose\/} one.) \\
\> \> \> 3. $n^2 + n = 4x^2 + 2x = 2(2x^2 + x)$ 
         \> \> Algebra \\
\> \> \> 4. $\exists y \in N (n^2 + n = 2y)$ 
         \> \> Existential Generalization (EG) \\
\> \> \> \> \> (If you {\em have\/} one, then one {\em exists}.) \\
\> \> \> 5. QED                 
         \> \> Definition of ``even'' \\
\> \> 3. QED                    
      \> \> \> Implication 
\end{proofoverhead}
Or, condensing a little: 
\begin{proofoverhead}
\> 2. If $n$ is even then $n^2 + n$ is even.   \\
\> \> 1. Assume $n$ is even. \\
\> \> 2. Choose $x \in N$, $n = 2x$
      \> \> \> Definition of ``even'', EI \\
\> \> 3. $n^2 + n = 4x^2 + 2x = 2(2x^2 + x)$ 
      \> \> \> Algebra \\
\> \> 4. $n^2 + n$ is even. 
      \> \> \> EG, definition of ``even'' \\
\> \> 5. QED        
      \> \> \> Implication 
\end{proofoverhead}
Analogously for the odd case (using a definition of ``odd'' that says that
the number is expressible in the form $2x + 1$):
\begin{proofoverhead}
\> 1. If $n$ is odd then $n^2 + n$ is even.   \\
\> \> 1. Assume $n$ is odd. \\
\> \> 2. $n^2 + n$ is even. \\
\> \> \> 1. $\exists x \in N (n = 2x + 1)$ 
         \> \> Definition of ``odd'' \\
\> \> \> 2. Choose $x \in N$, $n = 2x + 1$ 
         \> \> EI \\
\> \> \> 3. $n^2 + n = 4x^2 + 4x + 1 + 2x + 1 = 2(2x^2 + 3x + 1)$ \\
\> \> \> \> \> Algebra \\
\> \> \> 4. $\exists y \in N (n^2 + n = 2y)$ 
         \> \> EG \\
\> \> \> 5. QED                 
         \> \> Definition of ``even'' \\
\> \> 3. QED                    
      \> \> \> Implication 
\end{proofoverhead}

\subsection[Reproving sqrt$(2)$ is irrational]%
           {Reproving $\sqrt{2}$ is irrational}

Here is the proof from before, with uses of quantifier
reasoning mentioned explicitly.
\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 properties of rationals, EI \\
\> \> 2. $2 b^2 = a^2$       
      \> \> \> Algebra \\
\> \> 3. $a^2$ is even.
      \> \> \> EG, definition of ``even'' \\
\> \> 4. $a$ is even.      
      \> \> \> ??? \\
\> \> 5. Choose $c \in N$, $a = 2c$. 
      \> \> \> Definition of ``even'', EI \\
\> \> 6. $4 c^2 = a^2 = 2b^2$ 
      \> \> \> Algebra \\
\> \> 7. $2 c^2 = b^2$       
      \> \> \> Algebra \\
\> \> 8. $b^2$ is even.
      \> \> \> EG, definition of ``even'' \\
\> \> 9. $b$ is even.
      \> \> \> ??? \\
\> \> 10. $a$ and $b$ aren't in lowest terms. 
      \> \> \> 1.2.4, 1.2.9 \\
\> \> 11. QED
      \> \> \> 1.2.1, 1.2.10, propositional logic \\
\> 3.  QED                 
   \> \> \> \> Implication \\
2. QED  
\> \> \> \> \> Contradiction 
\end{proofoverhead}

There's a missing piece: showing that $a$ and $b$ are even, because
their squares are even\.  We prove this by contradiction:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> 4. $a$ is even. \\
\> \> \> 1. $a \mbox{ is odd} \Rightarrow \ms{false}$ \\
\> \> \> \> 1. Assume $a$ is odd. \\
\> \> \> \> 2. $a^2$ is odd. 
            \> Do a proof like the one in the birthdate \\
\> \> \> \> \> example, using EI, algebra, and EG. \\
\> \> \> \> 3. $\ms{false}$           
            \> 1.2.3, 1.2.4.1.2, Propositional logic \\
\> \> \> 2. QED
         \> \> Contradiction
\end{tabbing}
Actually, since we are using the same argument twice, it's better
style to extract and reuse some general lemmas\.
(In these, we're using $x_0$ for the values that we fix, to try to avoid
some of the confusion between the different uses of $x$.)
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
{\bf Lemma 1:} \\
Prove: $\forall x \in N [x \mbox{ odd } \implies x^2 \mbox{ odd}]$. \\
1. Fix $x_0 \in N$. \\
2. $x_0 \mbox{ odd } \implies x_0^2 \mbox{ odd}$. \\
\> 1. Assume $x_0$ is odd. \\
\> 2. Choose $y \in N$, $x_0 = 2y + 1$. 
   \> \> \> \> Definition of ``odd'', EI \\
\> 3. $x_0^2 = 4y^2 + 4y + 1 = 2(2y^2 + 2y) + 1$ 
   \> \> \> \> Algebra \\
\> 4. $x_0^2$ is odd.
   \> \> \> \> EG, definition of ``odd''. \\
\> 5. QED
   \> \> \> \> Implication \\
3. QED
\> \> \> \> \> UG
\end{tabbing}

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
{\bf Lemma 2:} \\
Prove: $\forall x \in N [x^2 \mbox{ even } \implies x \mbox{ even}]$. \\
1. Fix $x_0 \in N$. \\
2. $x_0^2 \mbox{ even } \implies x_0 \mbox{ even}$. \\
\> 1. Assume $x_0^2 \mbox{ even }$ \\
\> 2. $x_0 \mbox{ odd } \implies x_0^2 \mbox{ odd}$. 
   \> \> \> \> Lemma 1, UI \\
\> 3. $x_0 \mbox{ even}$. 
   \> \> \> \> Propositional reasoning \\
\> 4. QED
   \> \> \> \> Implication \\
3. QED
\> \> \> \> \> UG
\end{tabbing}

Once we have Lemma 2, we can apply it in the main proof to $a$ and
$b$ (again using UI)\.

Compare the structured proof that $\sqrt{2}$ is irrational with a
typical paragraph proof\.
The paragraph proof follows the same strategy, but leaves you to
figure out the structure and more of the reasons. 

\begin{proof}
The proof is by contradiction.  Assume for purpose of contradiction
that $\sqrt{2}$ is rational.  Then we can write $\sqrt{2} = a/b$ where
$a$ and $b$ are integers and the fraction is in lowest terms.
Squaring both sides gives $2 = a^2 / b^2$ and so $2 b^2 = a^2$.  This
implies that $a$ is even; that is, $a$ is a multiple of $2$.  As a
result, $a^2$ is a multiple of 4.  Because of the equality $2 b^2 =
a^2$, $2 b^2$ must also be a multiple of 4.  This implies that $b^2$
is even and so $b$ must be even.  But since $a$ and $b$ are both even,
the fraction $a/b$ is not in lowest terms.  This is a contradiction,
and so the assumption that $\sqrt{2}$ is rational must be false.
\end{proof}

\subsection{Derivation versus Presentation}

The ideas in the previous proof are given directly, in the order in
which they are {\em used\/}\.  This makes the proof concise and
clear\.  But this is a different order from the way the ideas arose
when we came up with the proof in the first place\.  By switching the
order around, we've lost information about {\em how we came up with\/}
the proof ideas\.

In reading proofs, you will see a tension between trying to provide
the reader with the cleanest possible final product and providing
intuition about how the proof was developed\.  Neither extreme is
perfect---both kinds of information are useful\.  When you write
proofs, you might want to give both the final product and some
discussion of how you arrived at it.


\subsection{De Morgan's Law}

\forstudents{

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall A, B (\bar{A} \cap \bar{B} = \overline{A \cup B})$ \\
1. Fix $A$, $B$. \\
2. $\bar{A} \cap \bar{B} = \overline{A \cup B}$   
\> \> \> \> \> ??? \\
3. QED
\> \> \> \> \> UG 
\end{tabbing}

\noindent
To show two sets are equal, we show that they contain the same
elements (a standard method):
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall A, B (\bar{A} \cap \bar{B} = \overline{A \cup B})$. \\
1. Fix $A$, $B$. \\
2. $\bar{A} \cap \bar{B} = \bar{A \cup B}$ \\
\> 1. $\forall x (x\in \bar{A} \cap \bar{B}  \Leftrightarrow x\in\overline{A \cup B})$ \\
\> \> 1. Fix $x$. \\
\> \> 2. $x \in \bar{A} \cap \bar{B}  \Leftrightarrow x \in \overline{A \cup B}$ 
      \> \> \> ??? \\
\> \> 3. QED    
      \> \> \> UG \\
\> 2. QED           
   \> \> \> \>  Definition of set equality. \\
3. QED 
\> \> \> \> \> UG 
\end{tabbing}

\noindent
Equivalence can be shown by showing two implications, one in each
direction: 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> 2. $x \in \bar{A} \cap \bar{B}  \Leftrightarrow x \in \overline{A \cup B}$ \\
\> \> \> 1. $x \in \bar{A} \cap \bar{B}  \Rightarrow x \in \overline{A\cup B}$ 
         \> \> ??? \\
\> \> \> 2. $x \in \overline{A \cup  B} \Rightarrow x \in \bar{A} \cap\bar{B}$ 
         \> \> ??? \\
\> \> \> 3. QED   
         \> \> Propositional logic 
\end{tabbing}
We already showed the first direction in last lecture.
The other direction reverses the steps: 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> \> 2. $x \in \bar{A \cup  B} \Rightarrow x \in \bar{A} \cap\bar{B}$ \\
\> \> \> \> 1. Assume $x \in \overline{A \cup B}$. \\
\> \> \> \> 2. $x \notin A \cup B$
            \> Definition of complement \\
\> \> \> \> 3. $x \notin A$, $x \notin B$
            \> Definition of union \\
\> \> \> \> 4. $x \in \bar{A}$, $x \in \bar{B}$
            \> Definition of complement \\
\> \> \> \> 5. $x \in \bar{A} \cap \bar{B}$
            \> Definition of intersection \\
\> \> \> \> 6. QED 
            \> Implication 
\end{tabbing}
Actually, the union step could be expanded to a little proof by
contradiction:  if $x$ is in one of the sets, then it's in the union.
}

\subsection{Counterexamples}

Counterexamples are the easiest way to avoid proving a theorem, e.g.: \\
Prove: All natural numbers $\geq 2$ are prime. \\
\\
This is false\.
We can show this using a ``counterexample'', $10$\.
That's all that's needed\.
Really, we're proving the negation, which says $\exists$ a non-prime
$\geq 2$\.
And this follows just by exhibiting one
(Existential Generalization).
