Archive for March 28th, 2010

When is proof by contradiction necessary?

March 28, 2010

It’s been a while since I have written a post in the “somewhat philosophical” category, which is where I put questions like “How can one statement be stronger than an another, equivalent, statement?” This post is about a question that I’ve intended for a long time to sort out in my mind but have found much harder than I expected. It seems to be possible to classify theorems into three types: ones where it would be ridiculous to use contradiction, ones where there are equally sensible proofs using contradiction or not using contradiction, and ones where contradiction seems forced. But what is it that puts a theorem into one of these three categories?

This is a question that arises when I am teaching somebody who comes up with a proof like this. “Suppose that the sequence (a_n) is not convergent. Then … a few lines of calculation … which implies that a_n\rightarrow a. Contradiction.” They are sometimes quite surprised when you point out that the first and last lines of this proof can be crossed out. Slightly less laughable is a proof that is more like this. “We know that |y-x|<\delta. Suppose that |\sin(y)-\sin(x)|\geq\delta. Since the derivative of \sin has absolute value at most 1 everywhere, it follows that |y-x|\geq\delta, which is a contradiction. Therefore, |\sin(x)-\sin(y)|<\delta.” There, it is clearly better to work directly from the premise that |y-x|<\delta via the lemma that |f(x)-f(y)|\leq\|f'\|_\infty |x-y| to the conclusion that |\sin(y)-\sin(x)|<\delta. However, the usual proof of the lemma does use contradiction: one assumes that the conclusion is false and applies the mean value theorem.

The result of all this is that I don’t have a good tip of the form, “If your theorem is like this then try a proof by contradiction, and otherwise don’t.” For the remainder of this post I’ll discuss another couple of examples that show some of the complications that arise. (more…)