I haven’t written a basics post in a while, because for the most part, that well has run dry, but once

in a while, one still pops up. I got an email recently asking about proofs by contradiction and

counterexamples, and I thought that would be a great subject for a post. The email was really

someone trying to get me to do their homework for them, which I’m not going to do – but I can

explain the ideas, and the relationships and differences between them.

Proof by contradiction, also known as “reductio ad absurdum”, is one of the most beautiful proof

techniques in math. In my experience, among proofs of difficult theorems, proofs by contradiction are the

most easy to understand. The basic idea of them is very simple. Want to prove that something is true? Look

at what would happen if it were false. If you get a nonsensical, contradictory result from assuming its

false, then it must be true.

Let’s be a bit more precise. The principle of proof by contradiction comes from the logical law of the

excluded middle, which says “for any statement S, (S or not S) is true” – that is, S must be either true or false. From that, we can infer that if S in true, not S must be false; if not S is true, then S must be false. There is no third option. So if we can prove that (not S) is false, then we know that S must be true. The way that we can prove that (not S) is false is by assuming that it’s true, and showing that

that leads to a contradictory result.

The alterative form (which is really the same thing, but can look different when it’s presented by

mediocre teachers) is proving that something is false. Just switch S and not S in the above discussion. Proving that S is false is just another way of saying that we want to prove that (not S) is

true. In a proof by contradiction, we can do that by assuming that S is true, and showing that that

leads to a contradictory result.

As always, things are best with an example. Since I’m a computer scientist, I’ll pull out

my favorite proof by contradiction: the proof of the Halting theorem.

Suppose you have a computer, which we’ll call φ. Every program for φ can be

described by as a number. Similarly, every possibly input for a program can be represented

as a number. The result of running a particular program on φ can be described as a function

φ(p,i) where p is the program, and i is the input.

One thing about programs is that they can contain infinite loops: there are some programs

which for some inputs will run forever without producing any results. One thing that we would

really like to know is for a program p with input i, will φ(p,i) ever return a result? If

it does, we say that program p *halts* with input i. The big question is, can we

write a program h such that takes any pair of p and i as inputs, and tells us whether p halts with input i?

The answer is no. The way that we prove that is by a classic proof by contradiction. So we

start by assuming that it’s true:

- Suppose that we
*do*have a program h such that φ(h,(p,i))=true if φ(p,i)

halts, and false otherwise. - We can write a program q, where φ(q,i) runs φ(h,(q,i)) as a subroutine. If

φ(h,(q,i)) returns true, then q enters an endless loop. Otherwise, q halts. - For program q, if φ(h,(q,i)) says that q halts, then q doesn’t halt. If φ(h,(q,i))

says that q doesn’t halt, then q halts. Therefore h isn’t a program which correctly says

whether another program will halt. This contradicts the assumption in step one, so that

assumption must be false.

For another example, one of the classic logic errors is the misuse of implication. If you have a logical statement

that for all possible values X, if A is true for X, then B must also true for that X, and you know that A is true for some specific thing Y, then you can infer that B must be true for Y. There’s a common error where you get that backwards: for all X, if A is true for X, then B must be true for X, and you know B is true for some specific Y, then inferring A is true for Y. That is *not* valid inference – it’s false.

We can prove that that kind of inference is invalid. The way we’ll do it is by assuming its true,

and then reasoning from it.

- Assume that it is true that “for all values X, if A is true for X, then B must be true for X”, and

“B is true for Y”, then “A is true for Y”. - Take the classic example statement of this type: “If X is a man, then X is mortal”,

and we’ll use it as an instantiation of the rule above: If we know that “If X is a man, then X is mortal, and we know that X is a mortal, then X is a man.” - The pet dog that I grew up died about 15 years ago. Since he died, he must have been mortal.
- By the statement we just derived, we can conclude that my pet dog was a man.
- But my pet dog was
*not*a man, he was a dog. So we have a contradiction, and

that means that the statement cannot be true.

Presto, one proof by contradiction.

Often, as in the example above, when you do proof by contradiction, what you do is find a specific

example which leads to a contradiction. If you can do that, that example is called a

*counter-example* for the disproven statement. Not all proofs by contradiction use specific

counter-examples. A proof by contradiction can be done using a specific counterexample for which the

statement is false. But it can also be done in a more general way by using general principles to show that

there is a contradiction. Stylistically, it’s usually considered more elegant in a proof by

contradiction to show a way o constructing a specific counterexample. In the two example proofs

I showed above, both proofs used counterexamples. The first proof used a *constructed counter-example*: it didn’t show a specific counter-example, but it showed how to construct

a counterexample. The second proof used a specific counter-example. *Most* proofs

by contradiction rely on a constructed counter-example, but sometimes you can simply show by

pure logic that the assumption leads to a contradiction.

An important thing to be careful for in proofs by contradiction is that you are actually obtaining

*true contradictions*. Many creationist “proofs” about evolution, age of the universe, radiological

dating, and many other things are structured as proofs by contradiction; but the conclusion is merely

something that *seems* unlikely, without actually being a logical contradiction. A very common

example of this is the big-numbers argument, in which the creationist says “Suppose that life were the

product of natural processes. Then the following unlikely events would have had to occur. The probability

of that combination of events is incredibly small, therefore it couldn’t have happened.” That’s not

a proof of any kind. There is no logical contradiction between “X has a probability of 1 in 10^{1010} of occuring”, “X occured”. Improbable never equals impossible, no matter

how small the probability – and so it can’t create a logical contradiction, which is required for

a proof by contradiction.

As an interesting concluding side-note, there are schools of mathematical thought that do not

fully accept proof by contradiction. For example, intuitionism doesn’t accept the law

of the excluded middle, which limits proof by contradiction. Intuitionism also, by its

nature, requires that proofs of existence show how to construct an example. So a proof by

contradiction that proves that something exists, by showing that assuming its non-existence

leads to a logical contradiction, are not considered valid existence proofs in intuitionistic

logic.