Proof method: Proof by contradiction

Proof method: Proof by contradiction

I was first presented with a proof by contradiction while I was studying Discrete event systems in Canada. And I was puzzled about it most day. I came to really like it though.

When we want to prove something by contradiction we assume that the statement we want to prove is false and then show that it leads to a logic contradiction at some point, therefore the statement must be true. Don’t be confused just yet. I will come to the examples.

Proof by contradiction is not limited to conditional statements like the the direct proof is. So we don’t need to have a proposition on the form if Q then P.

The structure of the theorem when using proof by contradiction goes

Proposition: P

Proof: Assume ~P

Then

Where ~ means is a negation. So by assuming that ~P is true we will see that at some point we get to the conclusion that some statement needs to be both true and false, and thereby we end up having a contradiction.

So we are trying to show the conditional statement which is exactly what we did with the direct proof.  One big difference here is that we don’t necessarily knows what C should be when we start out.

Example 1

For this we first need a few definitions.

Definition: A real number x is rational if x = a/b for some . That is for some integer values of a and b. A number x is irrational if it is not rational, that is if for every .

Definition: A number is Even if for some .

Definition: A number is Odd if for some .

Definition: Two number are coprimes if no number divides both a and b. Such that .

Proposition: The number is irrational

Proof: Assume that is rational (That is ~P).

That means .

We can assume that the number a,b are coprimes, since otherwise we could make a smaller pair of a and b by dividing the common factor out of both a and b. This also means that a and/or b is odd. Otherwise a and b would not be coprimes as we could divide both by 2.

By rearranging we get . That means is even since it adheres to the definition of even.

I promise I will prove this later with a method I haven’t covered yet, but for now it is just is even, so is a.

Since a is even b must be odd since we assume that a and b are coprimes. (This is C in the proof outline as we shall see later on).

Since a is even it means that there exists a c such that a = 2c. This we can plug into the equation and get . And by dividing by two on both sides we get which means that is even by definition and from that it follows (by the yet unproven statement) that b is even.

So now we have that b is odd and b is even. That is a clear contradiction. and thus proofs that is irrational. QED.

Example 2

In this example we are back in number theory, and what we want to prove is that there is an unlimited number of prime numbers. This is one of my favourite personal proofs by contradiction. At least among the ones I have encountered so far.

Definition: A number is a prime number if it only has the divisors 1 and p. That is to say there exists no such that b|p apart from 1 and p.

Definition: A number is composite if there exists at least one divisors apart from 1 and a. That is to say there exists a such that b|a apart from 1 and p. From this and the rules of divisibility this is also follows that there exist at least one prime number that will divide a.

Proposition: There is an infinite amount of prime numbers.

Proof: Assume that there is only a limited amount of prime numbers.

That means we can write them as such that is the largest prime that exists.

Now take the number . That is the product of all primes + 1. This number must be a composite thus there must exist a prime number that can divide it.  That means there will be a prime with such that .

However for all we will get 1 as remainder. That means there are no prime divisors for a, which in turns means that there are no divisors for a and thus it cannot be a composite number and therefore a is a prime number.  This contradicts the fact that that all a is not in the set of all primes and thus contradicts the assumption that there is only a limited number of primes. QED.

The dangers of using a proof by contradiction

Proof by contradiction is by all means a powerful technique but there is a major pitfall. If you make small mistake somewhere in the process you might end up with a contradiction which wont show that the proposition is true but it will show that you made a mistake. This could also happen with other proof methods, but this seems to be prone to it. So if it is possible it seems to be the advice to use Direct Proof or a Contra Positive proof which I will work with later on.

Wrapping up

There are many great sources to read about Proof by Contradiction. A few of them is Book of Proofs and Larry Cusicks website.

I will recommend you to do some of the exercises in Hammacks book, I have done so my self. And feel free to ask questions about them if you like. Maybe we can figure it out together. One more curious question. Do you have a favourite Theorem which is proven by contradiction?

Credit goes to Quitz who has taken the photo for this post and shared under the creative commons license. I am very grateful for borrowing it and my alteration is of course shared under the same license.

Posted by Kristian

11 comments

This is very neat.
I love Euclid’s proof of infinite primes.

Two things I noticed, that might be mistakes:
In Example 1: Two numbers a,b are coprime if no number x divides a,b with no remainder [i]except 1[/i].
In Example 2: Proposition: There is an [i]in[/i]finite amount of prime numbers.

Thanks SuprDewd

Yes the first was a non rigorous explanation, it should of course exclude 1, the second point was a plain mistake.
Thanks for noticing, I have corrected the main article.

Glad to help 🙂

But how do I format my comments?
Like for code?

Console.WriteLine("Hello World.");

You can format code by using [ csharp ]Console.WriteLine(“Hello World.”);[ /csharp ] or most other languages without the spaces in the brackets.
The plugin supports the tags

as3, bash, coldfusion, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, php, plain, powershell, python, ruby, scala, sql, vb, xml.

so most languages should be supported 🙂

Besides that the comments can be formatted with: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

#SuprDewd { happy: 100%; }

Proposition: 1 is the largest integer.
Proof: Assume that 1 is not the largest integer. Then there is an n > 1 which is the largest integer.
But n2 > n which is a contradiction.
Therefore, 1 is the largest integer.

This proof by contradiction is very cool, if it weren’t flawed, that is, it relies on the fact that there exists an n greater than all other integers, which is not true.
You’ve probably seen this one, but I thought it was really awesome.

“But n^2 > n”

I think it shows the danger of proof by contradiction very well. In the proof you just made it isn’t that subtle, since it is fairly easy to see that

“Then there is an n > 1 which is the largest integer.”

is a fallacy. But what happens when you make that “mistake” is that you prove your assumption to be a contradiction and thus prove your proposition.

I generally like proof by contradiction, but I’ve seen a lot of proofs that deduce contradiction to assumed hypothesis; just as in your introduction C & ~C. I find it difficult to accept those proofs, no matter how “intuitive” they seem to be. Nice article!

Hi Bellpeace

I completely agree with you about the difficulty in accepting these proofs. I find it to be my inability to actually negate a statement and accept that this is the opposite of the original and that the two are covering everything.

/Kristian

I as well think thus, perfectly pent post!

Leave a Reply