Proof by Contradiction: An Accessible Introduction with Simple Applications

Proof by contradiction is a fundamental proof method in undergraduate Mathematics, and in fact, it may even be relevant for pre-U students. Yet, how to make use of the method has been much overlooked in A’Level H2 Mathematics. Perhaps it is used by some students in certain elite schools or Olympiad programmes, but the method is not systematically covered in most Junior Colleges in Singapore. This post wishes to fill that gap, offer an accessible introduction to the method, and provide prospective Mathematics undergraduates a smoother transition into undergraduate Mathematics.

Proof by contradiction is an indirect Mathematical proof, a logical result that follows the law of noncontradiction proposed by Aristotle. The law states that a statement and the negation of the statement cannot both be true or false at the same time. To be more specific, one of the them must be true, and the other false at any given time. It is one of the most trivial logical result but still powerful enough to tackle advanced Mathematical problems. The method follows the following procedures:

1. Identify the proposition that needs to be established. Denote the proposition by P.
2. Assume that P is false. (i.e. The negation of P is true)
3. Start working on the negation of P and think about what logical result it brings.
4. Among all the results, find two contradictory with one another. Denote the two propositions Q and the negation of Q.
5. Since the negation of P logically implies both Q and the negation of Q, the negation of P leads to a logical contradiction.
6. Therefore, P must be true to avoid the logical contradiction.

I shall also discuss some examples in this post to illustrate how the method works. The challenge that I usually face is how to find the two contradictory conditions Q and the negation of Q. Do be careful and aware of the assumptions one made in each step as well as the seemingly incorrect entailed results.

Example 1: Prove that there are infinitely many prime numbers.

The question itself is the statement that needs to be established. We first assume that there are only finitely many prime numbers. Let’s denote these prime numbers by p1, p2, p3…pn, since there are only finitely many of them. Without the lose of generality, let’s sort these prime numbers so that p1<p2<p3<…<pn. In other words, we say that pn is the largest prime number, i.e. no natural number larger than pn is prime.

Then let’s consider p=p1*p2*p3…*pn+1. Clearly, p is larger than pn, and therefore by our deduction in the last paragraph, p cannot be prime (Q). Yet, p1,p2,p3…pn are all not the prime factors of p, therefore p has to be a prime number (the negation of Q). Since p cannot be a both prime and non-prime number, we reach a logical contradiction. Therefore, the original supposition must be wrong, and there are infinitely many prime numbers.

Example 2: Prove that \sqrt{2} is irrational.

This is the classical proof by contradiction, and one can even give a kind of quasi-proof that it must use contradiction. The reason is that the word “irrational” means “not equal to \frac{m}{n} for any pair of integers (m,n)”. We first assume on the contrary that \sqrt{2} is a rational number, and by the defining property of a rational number, we can denote \sqrt{2} = \frac{m}{n}, where the greatest common divisor of m and n is 1, i.e. they are co-prime (Q).

Then we can start our algebraic manipulations. We can take square both sides and obtain the expression 2n^2=m^2. Therefore, we can conclude that m^2 has the even divisor 2, and hence m must have the even divisor 2, otherwise m^2 will not be divisible by 2. Since m is divisible by 2, m^2 is divisible by 4, and hence n^2 must be divisible by 2. Following the same analysis, we can obtain the conclusion that n also has the even divisor 2.

Thus, the greatest common divisor of m and n is at least 2 (negation of Q). We have reached a contradictory point, and the original supposition must be wrong. In other words \sqrt{2} must be irrational.

I hope that you find this discussion useful.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.