Mathematical Proof/Methods of Proof/Proof by Contradiction

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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 , this is equivalent to assuming that That is, to assume that is true and 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

[edit | edit source]

A good example of this is by proving that 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.

Proof: Assume is rational. Then , where and are relatively prime integers (a and b have no common factors).[1] and . So

But since is even, must be even as well, since the square of an odd number is also odd. Then we have , or so .

The same argument can now be applied to to find . However, this contradicts the original assumption that a and b are relatively prime, and the above is impossible. Therefore, we must conclude that 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 was even since we knew that was even. Note that this would not work for 4 (mainly because ) because does not imply that .

More Thoughts

[edit | edit source]

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

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.

  1. It is a simple exercise to see that any rational number may be written in this form.