Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

From time to time, when I write proofs, I'll begin with a claim and then prove the contradiction. However, when I look over the proof afterwards, it appears that my proof was essentially a proof of the contrapositive, and the initial claim was not actually important in the proof.

Can all claims proven by reductio ad absurdum be reworded into proofs of the contrapositive? If not, can you give some examples of proofs that don't reduce? If not all reductio proofs can be reduced, is there any logical reason why not? Is reductio stronger or weaker than the contrapositive?

Edit: Just another minor question (of course this is optional and will not affect me choosing an answer): If they are equivalent, then why would you bother using reductio?

And another bonus question (Like the above, does not influence how I choose the answer to accept.) Are the two techniques intuitionistically equivalent?

share|improve this question
    
Wrt. your comment on Pete's post, you can change which answer you consider accepted: click on the green tick to unselect, and then you can choose again. –  Charles Stewart Jan 20 '10 at 9:50
    
WRt that post, I only unaccepted it because you said it was incorrect. In general, I don't change answers once I accept them unless it turns out that the information is wrong. –  Harry Gindi Jan 20 '10 at 10:17
1  
seems to be related to this question: gowers.wordpress.com/2010/03/28/… –  Kaveh Aug 3 '10 at 2:00
    
Proof by contradiction (, i.e. derive $\Delta \vdash \varphi$ from $\Delta, \lnot \varphi \vdash \bot$) is not valid in intuitionistic logic. Proof by contrapositive (, i.e. derive $\Delta \vdash \psi \rightarrow \varphi$ from $\Delta \vdash \lnot \varphi \rightarrow \lnot \psi$) is neither. It is not hard to see that intuitionistic logic plus each gives the classical logic. –  Kaveh Aug 3 '10 at 2:11
    
considering your first minor question, I think the reason is this: people prefer to have fewer negations in their theorems, IMHO, they prefer to think of theorems as constructively as possible, even when the proof is not. So in place of saying "if there is no foo, then there is no bar", people prefer "if there is a bar, then there is a foo". –  Kaveh Aug 3 '10 at 2:17
add comment

7 Answers

up vote 87 down vote accepted

Although the other answers correctly explain the basic logical equivalence of the two proof methods, I believe an important point has been missed:

  • With good reason, we mathematicians prefer a direct proof of an implication over a proof by contradiction, when such a proof is available. (all else being equal)

What is the reason? The reason is the fecundity of the proof, meaning our ability to use the proof to make further mathematical conclusions. When we prove an implication (p implies q) directly, we assume p, and then make some intermediary conclusions r1, r2, before finally deducing q. Thus, our proof not only establishes that p implies q, but also, that p implies r1 and r2 and so on. Our proof has provided us with additional knowledge about the context of p, about what else must hold in any mathematical world where p holds. So we come to a fuller understanding of what is going on in the p worlds.

Similarly, when we prove the contrapositive (¬q implies ¬p) directly, we assume ¬q, make intermediary conclusions r1, r2, and then finally conclude ¬p. Thus, we have also established not only that ¬q implies ¬p, but also, that it implies r1 and r2 and so on. Thus, the proof tells us about what else must be true in worlds where q fails. Equivalently, since these additional implications can be stated as (¬r1 implies q), we learn about many different hypotheses that all imply q.

These kind of conclusions can increase the value of the proof, since we learn not only that (p implies q), but also we learn an entire context about what it is like in a mathematial situation where p holds (or where q fails, or about diverse situations leading to q).

With reductio, in contrast, a proof of (p implies q) by contradiction seems to carry little of this extra value. We assume p and ¬q, and argue r1, r2, and so on, before arriving at a contradiction. The statements r1 and r2 are all deduced under the contradictory hypothesis that p and ¬q, which ultimately does not hold in any mathematical situation. The proof has provided extra knowledge about a nonexistent, contradictory land. (Useless!) So these intermediary statements do not seem to provide us with any greater knowledge about the p worlds or the q worlds, beyond the brute statement that (p implies q) alone.

I believe that this is the reason that sometimes, when a mathematician completes a proof by contradiction, things can still seem unsettled beyond the brute implication, with less context and knowledge about what is going on than would be the case with a direct proof.


Edit: For an example of a proof where we are led to false expectations in a proof by contradiction, consider Euclid's proof that there are infinitely many primes. In a common proof by contradiction, one assumes that p1, ..., pn are all the primes. It follows that since none of them divide the product-plus-one p1...pn+1, that this product-plus-one is also prime. This contradicts that the list was exhaustive. Now, many beginner's falsely expect after this argument that whenever p1, ..., pn are prime, then the product-plus-one is also prime. But of course, this isn't true, and this would be a misplaced instance of attempting to extract greater information from the proof, misplaced becasue this is a proof by contradiction, and that conclusion relied on the assumption that p1, ..., pn were all the primes. If one organizes the proof, however, as a direct argument showing that whenever p1, ..., pn are prime, then there is yet another prime not on the list, then one is led to the true conclusion, that p1...pn+1 has merely a prime divisor not on the original list.

share|improve this answer
4  
I was wondering when you'd come by. You usually have really good answers to these kinds of questions. –  Harry Gindi Jan 20 '10 at 9:51
    
Thanks, Harry. I appreciate it. It looks like I was late to this party... –  Joel David Hamkins Jan 20 '10 at 9:59
    
Oh, Thanks for accepting! It looks like I wasn't too late after all. –  Joel David Hamkins Jan 20 '10 at 10:44
13  
An interesting corollary of this is that, if you are making a first attempt at proving something, then proof by contradication can be very profitable, precisely because you don't end up worrying about all the intermediate implications. Of course, if you are successful, you should then check to see if there is a better proof... –  Matthew Daws Feb 9 '10 at 15:19
3  
Indeed Euclid's original proof is not by contradiction, but consists in the direct construction. –  Pietro Majer Oct 31 '10 at 23:52
show 2 more comments

Strictly speaking, the contrapositive of a statement which is not an implication doesn't make sense. However you can always fake the implication, the contrapositive of $\top \to A$ (or just $A$) is $\lnot A \to \bot$, i.e., a "proof by contradiction" is the contrapositive of a "proof (from tautology)."


I guess I can still answer the other two parts, which were added later on.

First, a proof by contradiction is a more versatile tool than the contrapositive. It is more efficient when dealing with complex statements, e.g. anything which is not a simple implication. Also, the contrapositive doesn't work very well when the hypothesis is not completely necessary or when implicit hypotheses are lurking around. For (pseudo-)example, suppose $A$ and $B$ are statements about widgets with property $C$. You have proof that $A \to B$ by assuming that $A$ and $\lnot B$ and concluding that either $\lnot A$ or the widget does not have $C$. You could formally conclude $\lnot A$ from the failure of $C$ since $C$ is an implicit hypothesis, but that would be unnatural. Proving $\lnot B \to \lnot A$ directly might be difficult since it is unclear where the implicit hypothesis $C$ should come in play. Of course, all of this can be fixed by removing unnecessary hypotheses and stating all implicit hypotheses, but this only happens in fairy tales (a.k.a. well written textbook exercises). See Pete's answer (and vote it up!) for more concrete examples...

Finally, to answer the very last part. The implication

$(B \to A) \to (\lnot A \to \lnot B)$

is intuitionistically valid. Indeed, the right hand side is a much weaker statement. The converse

$(\lnot A \to \lnot B) \to (B \to A)$

gives $\lnot\lnot A \to A$ when substituting $\top$ for $B$, so it only holds in classical logic. However,

$(B \to \lnot A) \leftrightarrow (A \to \lnot B)$

is intuitionistically valid, both sides say $\lnot(A \land B)$. So you can always take the contrapositive of an implication whose conclusion is negative. This is yet another face of the old saying "you can't prove a negative" or, more accurately, proving a negative is inherently nonconstructive.

share|improve this answer
add comment

My answer applies to standard logic only.

In terms of standard logic, proofs by contrapositive and by contradiction are "equivalent" in that they are both logically valid, and two logically valid propositions are equivalent to each other.

On the other hand, it is certainly true that every proof by contrapositive can be phrased as a proof by contradiction. Indeed, since the latter is perhaps a bit more intuitive, it is often used as a justification of the former when it is needed e.g. in calculus courses:

We wish to show $A \implies B$. Suppose we know that $\lnot B \implies \lnot A$. Suppose further that $B$ is false. Then $\lnot B$ is true, so $\lnot A$ is true, so $A$ is false, contrary to our assumption.

Suppose a proposition can be proved by contraposition. As above, there is then a standard recipe for modifying the proof to give a proof by contradiction. However, if you compare the two proofs you find that the one by contradiction merely has the above two line argument appended to it, so it is just slightly longer without any additional content. For this reason, when it is possible to give a direct proof of $\lnot B \implies \lnot A$ it is preferable to do so, rather than casting it as a proof by contradiction.

However, proof by contradiction is a more powerful technique in the informal sense that some proofs are more difficult to phrase using contraposition. (I don't want to say impossible, because as above, both "techniques" are simply logically valid arguments, so may be inserted in a proof at any point.)

What makes contradiction potentially more powerful? (This is a question that you have to face when you teach introduction to proofs classes, as I have. I wouldn't have had as ready an answer before.) I think it is because we get to assume two things rather than one. Namely, instead of just assuming $\lnot B$ and using that one assumption to work our way to $\lnot A$, we get to assume both $A$ and $\lnot B$ and play them off one another in order to derive a contradiction.

Here is an example of this. Suppose we wish to prove that $\sqrt{2}$ is irrational. First, let's phrase this as an implication:

For all $x \in \mathbb{R}$, $x^2 = 2 \implies x \not \in \mathbb{Q}$.

Or, contrapositively:

For all $x \in \mathbb{R}$, $x \in \mathbb{Q} \implies x^2 \neq 2$.

Taking the contrapositive was not so helpful! What we need to do is work from both ends at once:

Suppose that $x \in \mathbb{Q}$ and $x^2 = 2$. Now we are in business; we can work with this. (I omit the proof since I assume that everyone knows it.)

Here is another difference between the two proofs, which I didn't notice until I thought about this answer: the contrapositive of the statement

$\forall x \in S, P(x) \implies Q(x)$

is

$\forall x \in S, \lnot Q(x) \implies \lnot P(x)$:

note that the quantifier has not changed. (Of course we might have an existential quantifier instead, and the discussion would be the same. Anyway, in practice most mathematical propositions do begin with a universal quantifier.)

However, the negation of the statement is

$\exists x \in S \ | \ P(x) \wedge \ \lnot Q(x)$.

Note that the quantifier has changed from $\forall$ to $\exists$, which is a key feature of the above proof.

Finally, you ask why we would prefer one technique over another since both are equivalent. But of course we do this all the time, according to convenience and taste: e.g. induction, strong induction and well-ordering are all logically equivalent, but we use all three. We could e.g. phrase all induction proofs as appeals to the Well-Ordering Principle, but in many cases that would amount to inserting a tiresome rigamarole "Consider the set $S = \{ n \in \mathbb{N} \ | \ P(n)\ \text{is false} \}$..." which does not add to the clarity or concision of the proof.

share|improve this answer
1  
This is a great answer, but I already accepted another answer, so I can't accept this one, but seriously, +1. –  Harry Gindi Jan 20 '10 at 3:21
    
Those are great examples! –  François G. Dorais Jan 20 '10 at 3:25
    
I noticed the same thing last semester working through the exercises in Munkres. Having an eye for when you can work with existential instead of universal quantifiers makes life a lot easier (though the exercises aren't that bad to begin with). –  Qiaochu Yuan Jan 20 '10 at 3:45
1  
When you argue that with proofs by contradiction, you get to assume two things, so it is potentially more powerful: Yes, you get to assume more, but also, you must prove more to complete the argument, indeed, much more, an impossible thing, since you must prove a contradiction! –  Joel David Hamkins Jan 20 '10 at 9:54
1  
@Joel: This is a belated remark, but: I hope I am correct in reading your last comment as tongue-in-cheek. If anything, I find the opposite of what you say to be true: because a proof by contradiction does not proceed in a linear manner from one true thing to another true thing, it is much easier to write down a proof by contradiction: you need only make a single mistake somewhere. This is also something I warned my intro. to proofs students about: e.g., if your contradiction is that $3x^2 + 1 = -3x^2-1$, be sure you didn't just make a sign error! –  Pete L. Clark Aug 6 '10 at 9:45
show 1 more comment

I agree with Joel's answer: proofs by contrapositive are more satisfying than proofs by contradiction, because they give you more information beyond just knowing that the desired result is true. For instance, in analysis, proofs by contrapositive tend to be finitary in nature and yield effective bounds, whereas proofs by contradiction (especially when combined with compactness arguments) tend to be infinitary in nature do not easily yield such bounds (unless one very painstakingly converts each step of the infinitary contradiction argument into a finitary contrapositive argument). I discuss this for instance in

http://terrytao.wordpress.com/2008/08/30/the-correspondence-principle-and-finitary-ergodic-theory/

But by the same token, proof by contradiction is a more powerful method in practice than proofs by contrapositive, if your only aim is to prove the stated result; it is precisely because one is less ambitious that one can achieve one's goal more easily.

There is an analogy with the computational problem of trying to find a path in a maze from A to B. The direct approach would be to start from A and explore all reasonable-looking directions from A until one reaches B. The analogue of proof by contrapositive would be starting backwards from B and trying to reach A; then at the end one simply reverses the path. The analogue of proof by contradiction is a meet-in-the-middle strategy: explore both forwards from A and backwards from B until one gets an intersection. This is a faster strategy, with a run time which is typically the square root of the run time of the other two approaches (because of the birthday paradox, basically, or Metcalfe's law if you wish). This analogy is somewhat oversimplified because even in the meet-in-the-middle strategy it is not difficult to disentangle the solution to create a direct path from A to B; but with more complicated problem-solving tasks than mazes (e.g. trying to convert several hypotheses $A_1,\ldots,A_n$ into several conclusions $B_1,\ldots,B_m$, using deductive rules such as ``If $A_3$ and $C_5$ are true, then $D_7$ is true'', etc.) one can make the meet-in-the-middle solutions quite hard to convert back to a direct argument.

There is a class of proofs by contradiction that I call "no self-defeating object" arguments, which are particularly difficult to convert into proofs by contrapositive. Basically these proofs tend to show that A is false by using one argument to establish $A \implies B$ and another to establish $A \implies \neg B$, giving the contradiction (A defeats itself). One can convert this into a proof by contrapositive by making the inspired decision to divide into the two cases $B$ and $\neg B$, and show that each of these cases implies $\neg A$ by taking contrapositives of each side of the no-self-defeating object, but it is difficult in practice to motivate this choice of division into cases unless one had already seen the proof-by-contradiction version of the argument. This is particularly the case if A is an existence statement $\exists x: A(x)$ and B is dependent on x; then the dichotomy $B \vee \neg B$ cannot even be introduced without first introducing x. I discuss this type of argument on my blog at

http://terrytao.wordpress.com/2009/11/05/the-no-self-defeating-object-argument/

share|improve this answer
add comment

They are trivially equivalent. The contrapositive of (P → Q) is (¬Q → ¬P). This is equivalent to (¬Q → (P → ⊥)), which is a curried form of (¬Q ∧ P) → ⊥.

Edit: I'm not sure about your added comment. Reductio seems the more general proof technique to me (as Anweshi mentions, it works for statements which are not implications); contraposition seems less useful unless the contrapositive form ¬Q → ¬P is especially natural or intuitive.

Edit 2: These transformations would seem to be intuitionistically valid, with the proviso that a "proof by contradiction of (P → Q)" is only a proof of (P → ¬¬Q). Hence, the contrapositive (¬Q → ¬P) is strictly weaker than (P → Q).

On a further note, it is often the case that the antecedent P can be naturally seen as a negative statement (¬P'). In these cases, we may be able to provide a proof of (¬Q → P'). This may be the case of a proof by contrapositive which is a "direct proof", possibly accounting for J. Polak's remarks.

Edit 4: JD Hamkins points out that direct proofs often provide useful proofs of intermediate statements, whereas proofs by contradictions do not. But this technique can be generalized by pushing contradictory "contexts" to the very end of the proof: i.e. one can say: "We will prove a contradiction by assuming P, Q, R and S. From P, R and S we obtain the following lemmas..." It's not clear that all such proofs can be naturally stated as proofs by contrapositive.

share|improve this answer
    
This works only for "P implies Q" types of statements. What do you have to say about "P is not true" type of statements? Here specifically I have the Cantor's proof that a set and its power set are not equivalent. –  Anweshi Jan 19 '10 at 23:52
    
Ah, F G Dorais has already written it below. I had not seen it yet when I was typing the above comment. Sorry. –  Anweshi Jan 19 '10 at 23:55
    
It's just that 80-90% of the proofs I've done by contradiction have the contrapositive proof stuck inside somewhere. –  Harry Gindi Jan 20 '10 at 0:12
    
@Harry. Yes that is true. But there are genuine examples of ad absurdum, like the Cantor proof. –  Anweshi Jan 20 '10 at 0:36
1  
I agree with your edit, about pushing the contradictory context to the end. When successful, this method essentially turns the proof into a direct proof, with the advantages that I mention for the intermediary statements, and an additional proof by contradiction at the end. –  Joel David Hamkins Jan 20 '10 at 13:24
show 6 more comments

There does seem to be a difference, although I don't know how to distinguish them formally, but here are two cases which distinguish the two:

*Let V be a vector space. A linear map f on V is injective if its kernel is 0. (yes I know it's an iff). The contrapositive is, if f is a linear map and ker f is not 0, then f is not injective. Proof: $v\in \ker f$ nonzero means $f(v) = f(0) = 0$. We don't have to assume in the proof that f is injective first and get a contradiction.

Here we are arguing about a class of objects with one property and we are trying to prove another of that class.

--

*sqrt(2) is irrational. We can word this (artificially) as x = sqrt(2) implies there does not exist a,b rational such that x = a/b. However if we try the contrapositive, we get, there exists a,b rational such that x = a/b implies x is not sqrt(2). But to prove this we still need to assume that a/b = sqrt(2) and derive a contradiction.

Here we are trying to prove that a single object does not possess a certain characteristic. There must be a more formal treatment of these differences, however...

share|improve this answer
1  
Could it have something to do with a proof by contrapositive being somehow "still constructive"? –  Harry Gindi Jan 20 '10 at 0:26
    
@Harry. A proof by contrapositive is still a "direct proof". The second type of proof above, is not. It is true reductio ad absurdum. –  Anweshi Jan 20 '10 at 0:43
1  
A proof by contrapositive still relies on the identity (not(not A)) is logically equivalent to A. The standard way to show this is A=>B is equivalent to (not A) or B, which is equivalent to (not A) or (not not B) which is equivalent to (not A) <= (not B), at least in Bourbaki's axiomatization. –  Harry Gindi Jan 20 '10 at 0:48
    
@Harry. Unlike you I had given up trying to read Bourbaki, and I also gave up logic, set theory etc.. So I must confess I am trying to argue based on gut feelings. –  Anweshi Jan 20 '10 at 0:58
    
@Harry, see my answer. I think there may be a useful way of distinguishing "direct proof" by contrapositive (such as Polak's proof above) from true reductio ad absurdum. –  compguy Jan 20 '10 at 1:47
add comment

It often feels like a proof by contradiction is like making your point through a witty joke and the contrapositive is sitting down and explaining why the joke is funny.

Since the two approaches are logically equivalent, and since it is usually easy for the average journal reader to convert between the two --- the distinction for me comes down to style. Most of the arguments I have seen by contradiction are usually shorter, more intuitive, and elegant. Hence, I would usually favor proof by contradiction (it is usually the first proof I come up with...) unless the steps in the contrapositive are particularly insightful.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.