Proof By Contradiction
It is sometimes difficult (or impossible) to prove that a conjecture is true using direct methods. For example, to show that the square root of two is irrational, we cannot directly test and reject the infinite number of rational numbers whose square might be two. Instead, we show that the assumption that root two is rational leads to a contradiction. The steps taken for a proof by contradiction (also called indirect proof) are:
Why does this method make sense? One way to understand it is to note that you are creating a direct proof of the contrapositive of your original statement (you are proving if not B, then not A). Because contrapositive statements are always logically equivalent, the original then follows.
Note that the contradiction forces us to reject our assumption because our other steps based on that assumption are logical and justified. The only mistakethat we could have made was the assumption itself. An indirect proof establishes that the opposite conclusion is not consistent with the premise and that, therefore, the original conclusion must be true.
Sometimes, it can be a challenge determining what the opposite of a conclusion is. The opposite of all X are Y is not all X are not Y, but at least one X is not Y. Similarly, when we have a compound conclusion, we need to be careful. Consider these two examples:
Translations of mathematical formulas for web display were created by tex4ht.