​Proof by contradiction

​​In a nutshell

Two statements are contradictory when assuming both to be true at the same time allows you to derive something false, such as $$0=1$$. Many statements can be proved true by first assuming that they are false, and then deriving a false statement using statements you know to be true. This is known as proof by contradiction.

Contradictory statements

Suppose you are given statements $$P$$​ and $$Q$$, and, by assuming both to be true, you are able to derive something false. Then at least one of $$P$$​ and $$Q$$​ must be false; if you already know, say, that $$P$$​ is true, you can be certain that $$Q$$​ is false.

Negation

If you are trying to prove statement $$Q$$​ by contradiction, begin by assuming the negation of $$Q$$, written as $$¬Q$$​. This is just the statement that $$Q$$​ is false. For example, if $$Q$$ is the statement "there are infinitely many integers", then $$¬Q$$ is the statement "there are not infinitely many integers", or equivalently, "there are only finitely many integers". The negation of the negation of $$Q$$ is just $$Q$$​ again - this is like saying "$$Q$$​ is not not true".

Now, suppose you have a statement $$P$$​ which you know to be true. In this example, $$P$$ could be "for every integer $$n$$​, $$n+1$$ is also an integer". If assuming $$P$$​ and $$¬Q$$​ at the same time allows you to derive something false - a contradiction - then $$¬Q$$ must be false, and therefore $$Q$$​ must be true!

In this example, assume both "there are only finitely many integers" and "for every integer $$n$$​, $$n+1$$​ is also an integer" at the same time. If there are only finitely many integers, there must exist a largest integer - call it $$N$$. You now have the statement "$$N$$ is the largest integer". The statement "for every integer $$n$$​, $$n+1$$ is an integer" allows you to derive the statement "$$N+1$$​ is an integer". But this is larger than $$N$$​, so can't be an integer because "$$N$$ is the largest integer" so you have derived a false statement!

You know that "for every integer $$n$$​, $$n+1$$ is an integer" is a true statement (as well as other statements subtly assumed in the above proof, such as "for any number $$n$$, $$n+1$$ is greater than $$n$$​") and yet you derived a false statement - so the assumption "there are only finitely many integers" must be false. You have proved its negation, the statement "there are infinitely many integers", by contradiction!

Example 1

Prove that there are infinitely many square numbers.

Suppose for a contradiction that this is false, so there are only finitely many square numbers.

Then, there exists a largest square integer - call it $$N$$.

$$N$$ is a square integer, so it is positive, and there are square integers greater than $$1$$​ (such as $$4$$) so you must have that $$N > 1$$, and therefore $$N^2 > N$$.

However, you have shown that $$N^2$$ is a square integer greater than $$N$$, which must be false, as $$N$$ is the largest square integer - you have derived a contradiction! Your assumption that there are only finitely many square numbers must be false, so you have proved its negation, that there are infinitely many square integers.

Therefore, there are infinitely many square integers.

Example 2

Prove by contradiction that there are no two integers $$x$$ and $$y$$ such that $$15x + 9y = 1$$.

Suppose for a contradiction that there exists a pair of integers $$x$$ and $$y$$ such that $$15x + 9y = 1$$.

​$$15x$$​ is an integer multiple of $$3$$, and so is $$9y$$, so $$15x + 9y$$ is divisible by $$3$$​ . But $$15x + 9y = 1$$, so you have that $$1$$ is divisible by $$3$$, a contradiction.

​

Therefore, there is no pair of integers $$x$$ and $$y$$ such that $$\underline{15x + 9y = 1}$$.

​

Example 3

Prove by contradiction that the only integers $$n$$​ such that $$1 + 4n^4$$ is a prime number are $$n=1$$ and $$n=-1$$​.

Suppose that $$1 + 4n^4$$ is a prime, and $$n \ne \pm 1$$. You have that:

 $$1 + 4n^4 = (1 - 2n + 2n^2)(1 + 2n + 2n^2)$$​

​

For any positive integer $$n$$, $$n^2 \ge n$$, so both $$1 - 2n + 2n^2 > 0$$ and $$1 + 2n + 2n^2 > 0$$. These are both positive integers which divide $$1 + 4n^4$$.

$$1 + 4n^4$$​ is prime by assumption, and therefore one of and $$1 - 2n + 2n^2$$ are equal to $$1$$. If $$1 + 2n + 2n^2 = 1$$, then $$2n(1 + n) = 0$$ so $$n = 0$$ or $$n = -1$$. However $$n \ne -1$$ by assumption, and if $$n = 0$$ then $$1 + 4n^4 = 1$$, which is not prime. So $$1 + 2n + 2n^2 \ne 1$$.

Therefore, $$1 - 2n + 2n^2 = 1$$, and so $$2n(1-n) = 0$$. However, $$n \ne 1$$, and you have seen that $$n \ne 0$$. So, this is a contradiction.

Therefore, the only integers $$n$$ such that $$1 + 4n^4$$ is a prime are $$\underline{n=1}$$ and $$\underline{n=-1}$$.