\newlec
\hdc

\ex Prove that if $x \in \mathbb{R}$ is such that $x^{3} + 7x^{2} < 9$, then $x < 1.1$.

\vskip3em
\pf We prove the contrapositive. Suppose that $x \geq 1.1 > 1$. Then
\begin{align*}
x^{3} + 7x^{2} &\geq (1.1)^{3} + 7(1.1)^{2}\\
& = \left(\frac{11}{10}\right)^{3} + 7\left(\frac{11}{10}\right)^{2}\\
&= \frac{1331}{1000} + 7\left(\frac{121}{100}\right)
&= \frac{1331 + 8470}{1000} \\
&= \frac{9801}{1000} \\
&\geq 9
\end{align*}
as required. \qed

\ic{This is the 10 minute mark}

\newpage

\textbf{Types of Implications}
\vskip1em
Let $A,B,C$ be statements.
\begin{enumerate}
\item $(A \wedge B) \Rightarrow C$ These we have seen in say Divisibility of Integer Combinations or Bounds by Divisibility.
\item $A \Rightarrow (B \wedge C)$.
\vskip1em
\ex Let $S,T,U$ be sets. If $(S \cup T) \subseteq U$, then $S \subseteq U$ and $T \subseteq U$.
\vskip1em
\pf
Suppose $S \cup T \subseteq U$. If $x \in S$, then $x \in S \cup T \subseteq U$. Thus $x \in U$. Thus, $S \subseteq U$. By symmetry (or similarly), $T \subseteq U$. \qed
\ic{Here you can make note of the use of the word `similarly'. It should be used sparingly and only when the argument is truly identical.}
\item $(A \vee B) \Rightarrow C$
\vskip1em
\ex $(x = 1 \vee y = 2) \Rightarrow x^{2}y + y-2x^{2} + 4x - 2xy = 2$
\vskip1em
\pf Assume that $(x = 1 \vee y = 2)$. Then one of these two values is true. If $x = 1$, then
\begin{align*}
\text{LHS} &= x^{2}y + y-2x^{2} + 4x - 2xy  \\
&= (1)^{2}y + y-2(1)^{2} + 4(1) - 2(1)y \\
&= y + y - 2 + 4 - 2y \\
&= 2 \\
&= \text{RHS}.
\end{align*}
If instead $y=2$, then
\begin{align*}
\text{LHS} &= x^{2}y + y-2x^{2} + 4x - 2xy  \\
&=  x^{2}(2) + (2)-2x^{2} + 4x - 2x(2) \\
&= 2x^{2} + 2 - 2x^{2} + 4x - 4x \\
&= 2 \\
&= \text{RHS}.
\end{align*}
completing the proof. \qed
\item $A \Rightarrow (B \vee C)$. (Elimination)
\vskip1em
\ex If $x^{2} - 7x + 12 \geq 0$ then $x \leq 3 \vee x \geq 4$.
\vskip1em
\pf
Suppose $x^{2} - 7x + 12 \geq 0$ and $x > 3$. Then $0 \leq  x^{2} - 7x + 12 = (x-3)(x-4)$. Now, $x - 3 >0$ and so we must have that $x-4 \geq 0$. Hence $x \geq 4$.

\end{enumerate}

\ic{This is the 25-30 minute mark}

\newpage
\hdc
How many years has it been since the Toronto Maple Leafs have won the Stanley Cup?

\begin{enumerate}[A)]
\item -3
\item 49
\item 1000000
\item 1500
\end{enumerate}

\vskip3em
\ic{Argue that many answers are ridiculous and so only the plausible answer remains. Change the second answer to (current year - 1967). You could also introduce contradiction by using a sudoku board which can be fun.}


\newpage

\textbf{Proof by contradiction}
\vskip1em
Let $S$ be a statement. Then $S \wedge \neg S$ is false.
\ic{Mention we sometimes use $\#$ to denote a contradiction has been reached.}
\ex There is no largest integer.
\vskip1em
\pf Assume towards a contradiction that $M_{0}$ is the largest integer. Then, since $M_{0} < M_{0}+1$ and $M_{0} + 1 \in \mathbb{Z}$, we have contradicted the definition of $M_{0}$. Thus, no largest integer exists. \qed
\vskip1em

\ic{This is the 32-37 minute mark}

\newpage

\hdc

\ic{The following is an example of reading proofs and seeing the difference between the direct proofs and proofs by contradiction.}

\textbf{Example:} Let $n \in \mathbb{Z}$ such that $n^{2}$ is even. Show that $n$ is even.

\vskip1em

\textbf{Direct Proof:} As $n^2$ is even, there exists a $k \in \mathbb{Z}$ such that $$n\cdot n = n^{2} = 2k.$$ Since the product of two integers is even if and only if at least one of the integers is even, we conclude that $n$ is even. 

\vskip1em

\textbf{Proof By Contradiction:} Suppose that $n^{2}$ is even. Assume towards a contradiction that $n$ is odd. Then there exists a $k \in \mathbb{Z}$ such that $n = 2k+1$. Now, $$n^{2} = (2k+1)^{2} = 4k^{2} + 4k + 1 = 2(2k^{2} + 2k) + 1.$$ Hence, $n^2$ is odd, a contradiction since we assumed in the statement that $n^{2}$ is even. Thus $n$ is even.

\vskip3em

\ic{This is the 40 minute mark.}

\newpage

\ic{It should be noted that the Well Ordering Principle is not officially in the Math 135 curriculum. Since it is an easier to understand form of Mathematical Induction, I've chosen to include it.}
\noindent \textbf{Axiom} Well Ordering Principle (WOP). Every subset of the natural numbers that is nonempty contains a least element.

\newpage

\hdc

\ic{It's conceivable that you might want to write out the first proof and then display the other two proofs. Feel free to ignore these proofs as well. I do however recommend the first one.}

\textbf{Example:} Prove that $\sqrt{2}$ is irrational.
\vskip1em
\textbf{Proof:} Assume towards a contradiction that $\sqrt{2} = \frac{a}{b} \in \mathbb{Q}$ with $a,b \in \mathbb{N}$ (Think: Why is it okay to use $\mathbb{N}$ instead of $\mathbb{Z}$?). 
\vskip1em

 \textbf{Proof 1:} Assume further that $a$ and $b$ share no common factor (otherwise simplify the fraction first). Then $2b^{2} = a^{2}$. Hence $a$ is even. Write $a = 2k$ for some integer $k$. Then $2b^{2} = a^{2} = (2k)^{2} = 4k^{2}$ and canceling a 2 shows that $b^{2} = 2k^{2}$. Thus $b^{2}$ is even and hence $b$ is even. This implies that $a$ and $b$ share a common factor, a contradiction.

\vskip1em
\textbf{Proof 2 (Well Ordering Principle):} Let $$S = \{ n \in \mathbb{N}: n\sqrt{2} \in \mathbb{N}\}.$$ Since $b \in S$, we have that $S$ is nonempty. By the Well Ordering Principle, there must be a least element of $S$, say $k$. Now, notice that $$k(\sqrt{2}-1) = k\sqrt{2} - k \in \mathbb{N}$$
 (positive since $\sqrt{2} > \sqrt{1} = 1$). Further, $$k(\sqrt{2}-1)\sqrt{2} = 2k - k\sqrt{2} \in \mathbb{N}$$ and so $k(\sqrt{2}-1)  \in S$. However, $k(\sqrt{2}-1) < k$ which contradicts the definition of $k$. Thus, $\sqrt{2}$ is not rational.
 
 \vskip1em
 
 \textbf{Proof 3 (Infinite Descent):}  Isolating from $\sqrt{2} = \frac{a}{b} $, we see that $2b^{2} = a^{2}$. Thus $a^{2}$ is even hence $a$ is even. Write $a = 2k$ for some integer $k$. Then $2b^{2} = a^{2} = (2k)^{2} = 4k^{2}$. Hence $b^{2} = 2k^{2}$ and so $b$ is even. Write $b = 2\ell$ for some integer $\ell$. Then repeating the same argument shows that $k$ is even. So $a = 2k = 4m$ for some integer $m$. Since we can repeat this argument indefinitely and no integer has infinitely many factors of $2$, we will (eventually) reach a contradiction. Thus, $\sqrt{2}$ is not rational.

\vskip3em 
 \ic{If you do all three proofs, notice that the simple proof and the infinite descent proofs are similar.}




