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 101010 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