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 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.
Proof by contradiction is viewed as a logical consequence of the following series of steps to the question, "How can we show that P does not imply Q?"
- We must show that the predicate not only not imply but it cannot, or else logic breaks down.
- To begin, we show that does not imply . This results in showing that
- The statement above is equivalent to the statement
- This actually only proves that an implication is not true.
- Contradictions show that both statements cannot be true at the same time, or else logic breaks down by claiming a logical impossibility: .
- Thus, a proof by contradiction requires us to show, initially assuming that does not imply , either:
- Which, when substituted back into the logical statement yields either
- a true contradiction.
A contradiction proof is one of the strongest types of proof, since it proves not just that some given does not imply some , which does not discredit other attempts at proving a statement—only the one that shows your version of does not imply , but that can never imply ; and can never coexist together. If you are in mathematics, this type of proof is desired and sought after for exactly its quality of being such a strong argument.
It is straightforward to prove a contradiction and can be easily done by following the following steps:
- Prove separately these two claims
- is valid.
- (The original claim)
- (The contrapositive of the original claim)
- (whichever one is easier)
- Put the two together; . You have a contradiction.
Below are some examples where you see how this method is put into effect.
Square root of 2
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). 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
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
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.
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.
- It is a simple exercise to see that any rational number may be written in this form.