Proof by contradiction may at first seem completely weird! I give you something to prove, and you seem to ignore me and try and prove that what I want you to prove is wrong!

Actually, this isn’t nearly as strange as it first seems, and it can work in contexts other than mathematics. The idea stems from the fact that a statement is either true, or false (well, if you listen to Gödel, then you have to be a bit careful, but it’s reasonable enough for now). The process is the following:

  1. You want to prove that a statement is true.
  2. You say “what would happen if the statement were actually false?”
  3. You explore the consequences of it being false.
  4. If you find that it gives you a contradiction (something which you claimed to be true, but which you now see isn’t true), then you know that in fact the original statement can’t be false…so it must be true, and you’ve proved it.

This is definitely weird when you read it like that, so let’s try and understand it from some examples.

Let’s look at one of the most common examples. Let’s try and prove the statement:

 

\sqrt{2} is an irrational number.

 

So, we want to prove that this is true. That’s the first step above. The second step is to assume that it’s false. How would we state this? Well, if it’s not true that \sqrt{2} is irrational, then it must be rational, right? Numbers are either rational, or irrational, there’s no number which is neither rational or irrational, nor is there a number which is both. Irrational just means that it can’t be written as the quotient of two integers. If it is rational, then it can be written as the quotient of two integers.

 

So, we are now going to try and prove that the statement is false, and see what happens. If we think that it can be written as a rational number, then it can be written as:

 

\sqrt{2}=\dfrac{p}{q}

 

Where p and q are two integers and we will assume that p and q have no common factors. If they did have common factors, then we could always divide through by the common factors and end up with a simpler expression where the new numbers have no common factors. This would be equivalent to taking:

 

\dfrac{15}{25} and writing it in the simpler form \dfrac{3}{5}. We are assuming that in the form of p and q above, it is already in its simplest form.

 

In fact it is going to be this part of the statement which we show to be contradictory. We will show (as you see below) that although we said that p and q had no common factors, that in fact they do, so this will mean that you can’t write it as a rational number as we are claiming that you can.

 

Let’s now see what the consequences of being able to write \sqrt{2} as this rational number is. Let’s first square both sides:

 

2=\dfrac{p^2}{q^2}

 

Now rearrange to give:

 

2q^2=p^2

 

Ok, now one thing that we know is that p and q can’t both be even. If they were even, then they would have had a common factor, of 2, and thus \frac{p}{q} wouldn’t have been in the simplest form possible. However, we see that because the left hand side is 2 times something, the right hand side must be even. If p^2 is even, then p must be even (an even number squared must be even, and an odd number squared must be odd).

 

That seems fine – so we’ve discovered that p is even. But if p is even (ie. divisible by 2), then p^2 must be divisible by 4. But if p^2 is divisible by 4, then we can write it as p^2=4 a for some integer a. So we now have:

 

2q^2=4a

 

which gives:

 

q^2=2a

 

But this says now that q^2 must be even, so q must also be even. Ok, but this is a problem, because now we seem to have shown that both p and q are even, and we started by saying that we could write it in a form where there were no common factors – but we’ve just found that there is a common factor of 2. So we have a contradiction. The contradiction is:

 

If \sqrt{2} can be written as a rational number, then we must be able to write it in a simplest form of \dfrac{p}{q}. However, we can show a contradiction that \dfrac{p}{q} isn’t the simplest form! Therefore in fact \sqrt{2} can’t be written in the form \dfrac{p}{q} and so it can’t be a rational number, so it must be irrational.

 

Spend some time thinking about what’s happened here, and we will look at some more examples in the next post.

How clear is this post?