Proof by Contradiction

Sometimes, the easiest way to prove that a statement is true is by proving that the opposite of the statement is false. That is, you assume that the statement you are trying to prove is false, then go through the proof process until you run into a contradiction. This type of proof is most useful when you are trying to prove a negative statement (a statement that contains "not") or involves something continuing infinitely.

If you wanted to prove that a dog is not a cat, the strategy of using proof by contradiction would be useful.

First, assume that a dog is a cat. Then, try to find reasons that this isn’t the case. We could state that the dog does not have the same teeth as a cat, and is therefore not a cat. That would be a contradiction to our statement that a dog is a cat. Of course, this strategy is much more useful in mathematics.

Example

Prove that 3 is not an even number.

Strategy: Assume that 3 is an even number, and then get a contradiction.

We have proven that 3 is not an even number because, when we assumed that it was, we got a contradiction.  If there is a remainder when a number is divided by 2, then the number is not divisible by 2.

This was, of course, a very simple example.  You will revisit proofs by contradiction in later units.