Proof by Contrapositive
Proof by contrapositive can be used to prove if-then statements indirectly. The statement \(P\Rightarrow\mathcal{Q}\) is logically equivalent to its contrapositive \(\neg Q\Rightarrow\neg P\). Since logically equivalent means that when one is true the other must also be true, if we prove that the contrapositive is true, we also proved the original statement. Hint: use the contrapositive when there are “negative” statements (no solutions, not natural, \(\neq,\notin,\), etc.), when the if part is hard to start from, or simply when stuck.
Example
Use the contrapositive the prove that if \(c>\frac{49}8\) then \(f(x)=2x^2+7x+c\) has no solutions.
Solution
First, we formulate the contrapositive:
- P is \(c>\frac{49}8\mathrm{~so~}\neg P\mathrm{~is~}c\leq\frac{49}8.\)
- \({Q}\) is \(f(x)=2x^2+7x+c\) has no solutions so \(\neg\mathcal{Q}\) is \(f(x)=2x^2+7x+c\) has at least one solution.
Therefore, the contrapositive is if \(f(x)=2x^2+7x+c\) has at least one solution then \(c>\frac{49}8\). For a quadratic polynomial \(f(x)=ax^2+bx+c\) to have roots its determinant must satisfy \(b^2-4ac\geq0\). For our polynomial that is \((7)^2-4(2)(c)\geq0\). We try to isolate \({c}\):
\(\begin{aligned}
(7)^2-4(2)(c)& \geq{0} \\
\text{49-8c}& \geq0 \\
\text{49}& \geq8c \\
\frac{49}8& \geq c
\end{aligned}\)
which was what we wanted. Since the contrapositive is equivalent to the original statement, we have proven that if \(c>\frac{49}8\) then \(f(x)=2x^2+7x+c\) has no solutions.
Proof by Contradiction
Proof by contradiction can be used to prove any statement, including if-then. To prove a statement \({P}\) by contradiction:
- Formulate \(\lnot P\) and assume it is true.
- Manipulate the statement(s) in \(\lnot P\) to find a contradiction. A contradiction means two opposing statements being true at the same time (e.g. \(x=0\mathrm{~and~}x\neq0\)).
Hint: use contradiction when there are negative statements, “or” statements or simply when stuck.
Example
Prove that if \(a^2+5\) is even then \({a}\) is odd.
Solution
- The statement to prove in this case has the form \(P\Rightarrow Q\), where \({P}\) means \(a^2+5\) is even and \({Q}\) means \({a}\) is odd. The negation of \(P\Rightarrow Q\) is \(P\wedge\neg Q\), that would be \(a^2+5\) is even and \({a}\) is even.
- Now, we must assume these facts are true and use them to achieve a contradiction.
We’ve assumed that \({a}\) is even, that means \(a=2k\) for some \(k\in\mathbb{Z}\). We can use this information about \({a}\) and plug it into \(a^2+5\):
\(\begin{aligned}
&a^2+5 =(2k)^2+5 \\
&a^2+5 =4k^2+5 \\
&a^2+5 =4k^2+4+1 \\
&a^2+5 =2(2k^2+2)+1
\end{aligned}\)
Since \(a^2+5\) takes the form \(2m+1\) for \(m\in\mathbb{Z}\), it must be odd. However, we originally said \(a^2+5\) is even. This is a contradiction; therefore the negation must be false and the original statement must be true.