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 N2>N.
However, you have shown that N2 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 15x+9y=1.
Example 3
Prove by contradiction that the only integers n such that 1+4n4 is a prime number are n=1 and n=−1.
Suppose that 1+4n4 is a prime, and n=±1. You have that:
1+4n4=(1−2n+2n2)(1+2n+2n2)
For any positive integer n, n2≥n, so both 1−2n+2n2>0 and 1+2n+2n2>0. These are both positive integers which divide 1+4n4.
1+4n4 is prime by assumption, and therefore one of and 1−2n+2n2 are equal to 1. If 1+2n+2n2=1, then 2n(1+n)=0 so n=0 or n=−1. However n=−1 by assumption, and if n=0 then 1+4n4=1, which is not prime. So 1+2n+2n2=1.
Therefore, 1−2n+2n2=1, and so 2n(1−n)=0. However, n=1, and you have seen that n=0. So, this is a contradiction.
Therefore, the only integers n such that 1+4n4 is a prime are n=1 and n=−1.
