\documentclass[11pt,twoside]{article}
\usepackage{/a/class/6.042/fall00/newlectures/macros-course-lectures}

\renewcommand{\bar}[1]{\overline{#1}}

%\makeslides

\begin{document}

\onlystudents

\lecture{notes2}{Predicate Reasoning; Proof by Induction}{September 12, 2000}

This handout contains some formatted versions of proofs that will look
messier on the blackboard.

\section{Predicate reasoning examples}

\subsection{Birthdate}

\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 ($n^2 + n$ is even.)                       
   \> \> \> \> Cases \\
3. QED ($\forall n \in N (n^2 + n \mbox{ is even})$.) 
\end{proofoverhead}

\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. \\
\> \> 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 ($n^2 + n$ is even)
         \> \> Definition of ``even'' \\
\> \> 3. QED (If $n$ is odd then $n^2 + n$ is even.)
      \> \> \> Implication \\
\> 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) \\
\> \> \> 3. $n^2 + n = 4x^2 + 2x = 2(2x^2 + x)$ 
         \> \> Algebra \\
\> \> \> 4. $\exists y \in N (n^2 + n = 2y)$ 
         \> \> Existential Generalization (EG) \\
\> \> \> 5. QED ($n^2 + n$ is even)                 
         \> \> Definition of ``even'' \\
\> \> 3. QED (If $n$ is even then $n^2 + n$ is even.)
      \> \> \> Implication \\
\> 3. QED ($n^2 + n$ is even.) 
   \> \> \> \> Cases \\
3. QED ($\forall n \in N (n^2 + n \mbox{ is even})$.)
\> \> \> \> \> UG
\end{proofoverhead}

\newpage
\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. \\
\> \> 1. Assume $n$ is odd. \\
\> \> 2. Choose $x \in N$, $n = 2x+1$
      \> \> \> Definition of ``odd'', EI \\
\> \> 3. $n^2 + n = 4x^2 + 4x + 1 + 2x + 1 = 2(2x^2 + 3x + 1)$ \\
\> \> \> \> \> Algebra \\
\> \> 4. $n^2 + n$ is even
      \> \> \> EG, Definition of ``even'' \\
\> \> 5. QED (If $n$ is odd then $n^2 + n$ is even.)
      \> \> \> Implication \\
\> 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 (If $n$ is even then $n^2 + n$ is even.)       
      \> \> \> Implication \\
\> 3. QED ($n^2 + n$ is even.) 
   \> \> \> \> Cases \\
3. QED ($\forall n \in N (n^2 + n \mbox{ is even})$.)
\> \> \> \> \> UG
\end{proofoverhead}

\subsection{$\sqrt{2}$ is irrational}

\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}

\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}

\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}

\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{De Morgan's Law}

\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}

\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}

\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}

\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}

\section{Inductive proof examples}

\subsection{Sum of Series}

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (\sum_{i=1}^n i = \frac{n(n+1)}{2})$.\\
1. (Base) $\sum_{i=1}^0 i = \frac{0(0+1)}{2}$. 
\> \> \> \> \> ??? \\
2. (Inductive step) 
   $\forall n \geq 0 (\sum_{i=1}^n i = \frac{n(n+1)}{2} \Rightarrow
                      \sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2})$ \\
\> \> \> \> \> ??? \\
3. QED                              
\> \> \> \> \> Induction 
\end{tabbing}

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
1. (Base) $\sum_{i=1}^0 i = \frac{0(0+1)}{2}$ \\
\> 1. $\sum_{i=1}^0 i = 0$
   \> \> \> \> Definition of summation with no terms \\
\> 2. $\frac{0(0+1)}{2} = 0$
   \> \> \> \> Arithmetic \\
\> 3. QED
   \> \> \> \> By 1.1 and 1.2.
\end{tabbing}

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
2. (Inductive step) 
   $\forall n \geq 0 (\sum_{i=1}^n i = \frac{n(n+1)}{2} \Rightarrow
                      \sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2})$ \\
\> 1. Fix $n \geq 0$. \\
\> 2. $\sum_{i=1}^n i = \frac{n(n+1)}{2} \Rightarrow 
       \sum_{i=1}^{n+1}i = \frac{(n+1)(n+2)}{2}$ \\
\> \> 1. Assume $\sum_{i=1}^n i = \frac{n(n+1)}{2}$ \\
\> \> 2. $\sum_{i=1}^{n+1}i= \frac{(n+1)(n+2)}{2}$ 
      \> \> \> ??? \\
\> \> 3. QED   
      \> \> \> Implication \\
\> 3. QED
   \> \> \> \> UG 
\end{tabbing}

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> 2. $\sum_{i=1}^{n+1}i = \frac{(n+1)(n+2)}{2}$ \\
\> \> \> 1. $\sum_{i=1}^{n+1}i = (\sum_{i=1}^{n}i)  + (n+1)$ 
         \> \> Summation has one extra term. \\
\> \> \> 2. $(\sum_{i=1}^{n}i) + (n+1) = \frac{n(n+1)}{2}+ n+1$
         \> \> Inductive hypothesis $P(n)$ (2.2.1) \\
\> \> \> 3. $\frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}$
         \> \> Algebra \\
\> \> \> 4. QED 
         \> \> Combining the previous 3 equations.
\end{tabbing}

\newpage
\subsection{Divisibility}

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \in N, n \geq 0 (6 | n^3 - n)$ \\
1. (Base) $6 | 0^3 - 0$ \\
2. (Inductive step) $\forall n \geq 0 (6 | n^3 - n \Rightarrow 6 |
(n+1)^3 - (n+1))$ \\
\> 1. Fix $n \geq 0$. \\
\> 2. Assume $6 | n^3 - n$ \\
\> 3. $6 | (n+1)^3 - (n+1)$ \\
\> \> 1. $(n+1)^3 - (n+1) = n^3 - n  + 3(n^2 + n)$
      \> \> \> Algebra \\
\> \> 2. $n^2 + n$ is even   
      \> \> \> Proved this earlier today \\
\> \> 3. $2 | n^2 + n$  
      \> \> \> Definition of $|$ \\
\> \> 4. $6 | 3(n^2 + n)$ 
      \> \> \> Multiplying both sides by $3$ \\
\> \> \> \> \> (basic properties of $N$)\\
\> \> 5. $6 | (n^3 - n)  + 3(n^2 + n)$
      \> \> \> Divides both terms (2.2, 2.3.4), \\
\> \> \> \> \> so divides sum. \\
\> \> 6. QED 
      \> \> \> 2.3.1, 2.3.5 \\
\> 4. QED \\
3. QED \\
\end{tabbing}

\end{document}



