Proof by contradiction

A proof by contradiction (a.k.a. reductio ad absurdum, reduction to absurdity) is a strategy used by mathematicians to show that a mathematical statement is true by proving that the [-negation] of that statement leads to being able to prove that two opposite statements are simultaneously true (a [-contradiction]).

Outline

The outline of the strategy is as follows:

1. Suppose that what you want to prove is false.
2. Derive a contradiction from it.
3. Conclude that the supposition is wrong.

Examples

To illustrate the concept, we will do a simple, non rigorous reasoning. Imagine yourself in the next situation:

You are a defense lawyer. Your client is accused of stealing the cookie from the cookie jar. You want to prove her innocence. Lets say you have evidence that the jar is still sealed. Reason as follows:

1. Assume she stole the cookie from the cookie jar.
2. Then she would have had to open the jar.
3. The jar is still sealed.
4. For the jar to be sealed and for her to have opened it is a contradiction.
5. Hence the assumption in 1 is false (given the deductions below it are true).
6. Hence she did not steal the cookie from the cookie jar.

Now we will work through an actual mathematical example: we will show that $~$\sqrt 2$~$ is not rational; that is, it cannot be expressed as the division of two natural numbers.

1. We suppose that $~$\sqrt 2$~$ is rational, which means that there exist $~$a,b\in\mathbb{N}$~$ such that $~$\sqrt 2 = \frac{a}{b}$~$. Without loss of generality, we can suppose that $~$a$~$ and $~$b$~$ [coprime have no common divisors], since otherwise we can just divide both numbers by their greatest common divisor to obtain a pair of numbers which satisfy both properties.
2. If this was the case, $~$b\sqrt2=a$~$. by squaring both sides, we arrive to $~$2b^2=a^2$~$. But then $~$2$~$ divides $~$a$~$, so we can express $~$a$~$ as $~$2n$~$ for some $~$n\in\mathbb{N}$~$. Substituing in the previous expression, we arrive to $~$2b^2 = 4n^2\implies b^2 =2 n^2$~$. By the same reasoning, $~$2$~$ must divide $~$b$~$, but then $~$a$~$ and $~$b$~$ have a common divisor! We have a contradiction.
3. We conclude that our original assumption that $~$\sqrt 2$~$ is rational must be false, and thus $~$\sqrt 2$~$ is not rational.

When to use it

Proof by contradiction is one of the most useful techniques one can use to prove anything.

In particular, if you get stuck while doing a proof, resorting to proof by contradiction is a great way to keep exploring a problem from a different perspective. Even if you do not get to solve the problem, you may get a useful insight about the problem when performing the procedure of proof by contradiction.

Also, trying to do proof by contradiction may result in a [ counterexample], which dissolves the problem in question.

[todo: exercises]