Mathematical Proof/Methods of Proof/Proof by Contradiction

The method of proof by contradiction is to assume that a statement is not true and then to show that that assumption leads to a contradiction. In the case of trying to prove $P\Rightarrow Q$ , this is equivalent to assuming that $P\land \lnot Q$ That is, to assume that $P$ is true and $Q$ is false. This is known by its latin reductio ad absurdum (reduction to absurdity), since it ends with a statement that cannot be true.

Square root of 2

A good example of this is by proving that ${\sqrt {2}}$ is irrational. Proving this directly (via constructive proof) would probably be very difficult (if not impossible). However, by contradiction we have a fairly simple proof.

Proposition 2.3.1. ${\sqrt {2}}\notin \mathbb {Q}$

Proof: Assume ${\sqrt {2}}$ is rational. Then ${\sqrt {2}}={\frac {a}{b}}$ , where $a$ and $b$ are relatively prime integers (a and b have no common factors). and $b\neq 0$ . So

$2={\frac {a^{2}}{b^{2}}}$

$2b^{2}=a^{2}$

But since $a^{2}$ is even, $a$ must be even as well, since the square of an odd number is also odd. Then we have $a=2a_{1}$, or $2b^{2}=4a_{1}^{2},$ so $b^{2}=2a_{1}^{2}$ .

The same argument can now be applied to $b$ to find $2b_{1}=b$ . However, this contradicts the original assumption that a and b are relatively prime, and the above is impossible. Therefore, we must conclude that ${\sqrt {2}}$ is irrational.

Of course, we now note that there was nothing in this proof that was special about 2, except the fact that it was prime. That's what allowed us to say that $a$ was even since we knew that $a^{2}$ was even. Note that this would not work for 4 (mainly because ${\sqrt {4}}=2\in \mathbb {Q}$) because $4|a^{2}$ does not imply that $4|a$ .

More Thoughts

In English, the procedure is this: Assert that a statement is false, and then prove yourself wrong. (Thereby proving the original statement was true.) This is a form of Modus Tollens.

For many students, the method of proof by contradiction is a tremendous gift and a trojan horse, both of which follow from how strong the method is. In fact, the apt reader might have already noticed that both the constructive method and contrapositive method can be derived from that of contradiction.

Assume	Prove	Contradiction
$P\land \lnot Q\ which\ implies\ P$	$Q\ (from\ P\ only)$	$Q\land \lnot Q$
$P\land \lnot Q\ which\ implies\ \lnot Q$	$\lnot P\ (from\ \lnot Q\ only)$	$P\land \lnot P$

However, its reach goes farther than even that, since the contradiction can be anything. Even if we ignore the criticisms from constuctivism, this broad scope hides what you lose; namely, you lose well-defined direction and conclusion, both of which have to be replaced with intuition.

Lastly, even in nonconstructive company, using the method in the first row of the table above is considered bad form (that is, proving something by pseudo-constructive proof), since the proof-by-contradiction part of it is nothing more than excess baggage.

---