Proof by contradiction is another general proof technique like direct proofs and the contrapositive proofs. When you first encounter proof by contradiction it can seem rather mysterious:
Assume to be true something we know is false, then
prove garbage, then
from this deduce truth!
But after you get the hang of it, proof by contradiction becomes indispensable.
Warning11.0.1.Not everything is a nail.
One of the reasons that the authors have left this topic until quite late in the text is that we find that students try to use this method for everything. Remember, contradiction is just another method in our toolbox and just because we have a shiny new hammer, not every result is a nail 150 . Please do not forget the other proof techniques.
With that warning out of the way, what is proof by contradiction and how does it differ from other techniques? Well, roughly speaking, when we use proof by contradiction, we do not seek to prove a statement \(P\) to be true, but rather we prove that \((\neg P)\) is false.This might seem to be a delicate and pedantic distinction, but it does make the structure of the resulting proof very different from direct and contrapositive proofs.
Once we know that \((\neg P)\) is false we can deduce that \(P\) is true. To do so we rely on the law of the excluded middle 151 which states that a statement must either be true or its negation must be true:
\begin{align*}
(P \lor (\neg P)) & \text{ is a tautology}
\end{align*}
and also modus tollens 152 . Remember modus ponens is:
So if we know that an implication \(P \implies Q\) is true, and the conclusion \(Q\) is false, then the hypothesis \(P\) must be false 153 .
So how do we put these things together to make a proof by contradiction?
Remember the Law of the Instrument (or look it up with your favourite search engine).
Being middle child, one of the authors finds it difficult to not think of the law of the excluded middle as being some sort of analysis of birth-order and family dynamics. The interested reader should continue to the next section of the text in which we discuss it further. “It” being the law of the excluded middle and not anything to do with middle-child syndrome.
or “denying the consequent” as it is known in less latin moments.
The skeptical reader should take a quick glimps at the truth table to see why this is so.
