Subsection 8.3.1 How Does a Proof by Contradiction Work?
Recall the Law of the Excluded Middle:
p ∨ ¬p.
In other words, for any statement p, either it’s true or false. Either it or its negation must be true. There’s nothing “in the middle”.
So suppose that I want to prove p. I’ll start by assuming ¬p. Suppose that, from that, I can derive False (or any contradiction, since every contradiction evaluates to False). But I know that one of p or ¬p must be true. And I’ve just shown that it’s not ¬p. Thus it must be p. I’m done.
Suppose we want to prove that √2 is irrational. (Recall that a number is irrational if it cannot be expressed as the ratio of two integers.) The most straightforward way to prove this claim is to assume that it were rational. (In other words, that it could be expressed as the ratio of two integers, say as x⁄y ). From that, we can derive a contradiction. Since (by the Law of the Excluded Middle) √2 must either be rational or not rational and we’ve just shown that it can’t be rational, it must be irrational. We’ll present the details of this proof soon.
Proofs by contradiction are also sometimes called indirect proofs.