Mathematical Writing - Vivaldi Franco 2014
Proof by Contradiction
Forms of Argument
A proof by contradiction of a proposition consists of assuming and deducing a false statement:
(7.6)
The false statement could be anything, including any assertion that contradicts the assumption . Formally, contradiction works because from (7.6) and the truth table (4.9) of the implication operator we deduce that is false and hence is true.
For example, in the proof by contradiction of the irrationality of , presented in Sect. 7.1, we assumed that , and deduced that
which is clearly false.
A classic proof by contradiction is Euclid’s proof of the infinitude of primes.
Theorem 7.1. The number of primes is infinite.
PROOF. Assume there are only finitely many primes, . Consider the integer
(7.7)
Then is greater than all the primes; moreover, if we divide by we get remainder 1, and therefore is not divisible by any of the primes. Now, every integer greater than 1 is divisible by some prime. It follows that must be divisible by a prime not in the given list, a contradiction.
The statement that every integer greater than 1 is divisible by some prime needs some justification (see Sect. 8.1).
To apply the method of contradiction to an implication , we assume the negation of the implication, namely . By Theorem 4.1, this is equivalent to , so our proof amounts to establishing that
This form of proof by contradiction is called the both ends method: to prove that if then , we assume both and not-, and we deduce something impossible. The appealing feature of this method is that it gives us two assumptions to exploit, namely and . This is often how mathematicians work, although this strategy may not be made explicit. It also easily causes confusion in writing, as the following example (from a textbook) shows.
Theorem. For all real numbers , if , then .
BAD PROOF: If then , so , i.e., , a contradiction. Therefore . Since can’t be , we conclude that .
In this proof, the assumption of is hidden, and the assumption of is confused. Not helpful writing!
PROOF. We use contradiction. Let us assume that and . Multiplying the second inequality by , we obtain , and since is positive, multiplication by yields . Simplification gives , which is false.
The final deduction rests on the inequality , which may be derived from the axioms of the real number system.