Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I remember hearing several times the advice that, we should avoid using a proof by contradiction, if it is simple to convert to a direct proof or a proof by contrapositive. Could you explain the reason? Do logicians think that proofs by contradiction are somewhat weaker than direct proofs?

Edit: To clarify the question. I am wondering, if there is any reason that one would still continue looking for a direct proof of some theorem, although a proof by contradiction has already been found. I don't mean improvements in terms of elegance or exposition, I am asking about logical reasons. For example, in the case of axiom of choice, there is obviously reason to look for a proof that does not use the axiom of choice. Is there a similar case for proofs by contradiction?

share|improve this question
1  
Related: math.stackexchange.com/questions/198. –  Ben Alpert Jul 30 '10 at 3:46
2  
"I don't mean improvements in terms of elegance or exposition, I am asking about logical reasons." So it's unrelated to your question, but I'll point out that the exposition of proofs often becomes much more elegant when converted from by-contradiction into a direct form (and sometimes less). Before writing up a proof, it's often worth considering both the direct and contrapositive forms and picking whichever is nicer, regardless of how you arrived at the result. –  ShreevatsaR Aug 6 '10 at 2:04

8 Answers 8

up vote 71 down vote accepted

Over at this MathOverflow question, I posted the following answer to a similar question (and there are several other interesting answers there):

  • 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 nonexistant, 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.

For an example of a proof where we are led to false expectations in a proof by contradiction, consider Euclid's theorem 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 lead to the true conclusion, that p1...pn+1 has merely a prime divisor not on the original list. (And Michael hardy mentions that indeed Euclid had made the direct argument.)

share|improve this answer
1  
+1 once again. (Note that I made a comment to your comment to my answer to this MO question. Over here, it seems that you would get automatically notified of this, but not on MO...) –  Pete L. Clark Aug 6 '10 at 9:47
11  
It's worth stressing that reductio proofs can in fact lead to "extra value". Take your example of Euclid's proof. One can organize the reductio proof to conclude that 1 + p1 ... pn is a unit, contradiction. But in other rings with finitely many primes this is a valid deduction, essentially amounting to the fact that 1+J consists of units for any J contained in the Jacobson radical. In fact this leads to a far reaching constructive generalization of Euclid's proof to fewunit rings, i.e. any ring having fewer units that elements - see my proof here bit.ly/FewUnitsA –  Bill Dubuque Sep 20 '10 at 4:31
5  
It is commonly stated by respectable number theorists that Euclid's proof of the infinitude of primes was by contradiction. But it is false. See my joint paper with Catherine Woodgold about this: Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, volume 31, number 4, fall 2009, pages 44–52. –  Michael Hardy Jul 16 '11 at 23:02
    
@Michael: If you ever update that paper, you can add Terence Tao as one of the culprits: Structure and Randomness in the prime numbers –  joriki Jul 18 '12 at 8:05
    
@joriki : While speaking briefly with Terence Tao in an elevator I pointed out why the proof by contradiction is not as good. Some time later I found it mentioned in his blog that someone had pointed this out to him. –  Michael Hardy Oct 18 '12 at 3:15

Most logicians consider proofs by contradiction to be equally valid, however some people are constructivists/intuitionists and don't consider them valid.

(Edit: This is not strictly true, as explained in comments. Only certain proofs by contradiction are problematic from the constructivist point of view, namely those that prove "A" by assuming "not A" and getting a contradiction. In my experience, this is usually exactly the situation that people have in mind when saying "proof by contradiction.")

One possible reason that the constructivist point of view makes a certain amount of sense is that statements like the continuum hypothesis are independent of the axioms, so it's a bit weird to claim that it's either true or false, in a certain sense it's neither.

Nonetheless constructivism is a relatively uncommon position among mathematicians/logicians. However, it's not considered totally nutty or beyond the pale. Fortunately, in practice most proofs by contradiction can be translated into constructivist terms and actual constructivists are rather adept at doing so. So the rest of us mostly don't bother worrying about this issue, figuring it's the constructivists problem.

share|improve this answer
    
Noah, is there any reason you posted this as a separate answer? –  Larry Wang Jul 21 '10 at 5:07
5  
It's a totally different kind of answer from the other answer. People may very well like one of the answers a lot more than the other. –  Noah Snyder Jul 21 '10 at 5:22
9  
Intuitionists do accept proofs by contradiction. Indeed, they take the definition of "not A" to be "A implies a contradiction", so a direct proof of "not A" in an intuitionistic setting assumes A and derives a contradiction. The thing that intuitionists do not accept is that "not not A" is equivalent to "A". So if you assume "not A" and arrive at a contradiction, this can be a perfectly valid intuitionistic proof of "not not A", but it will not be a proof of "A". That has essentially nothing to do with proof by contradiction, though. –  Carl Mummert Aug 6 '10 at 13:15
1  
It's certainly not true that constructivists reject proofs by contradiction. However, they do reject proofs of existence by contradiction. –  Michael Hardy Oct 18 '12 at 15:48
1  
I want to add that constructive proofs have computational content: if you prove the existence of an object, it is possible to perform a computation and obtain (a representation of) that object. In this sense it seems reasonable to reject non-constructive proofs of existence, as they give absolutely no method of obtaining a description of the asserted object. –  cody Oct 18 '12 at 18:49

In order to prove A, let's assume not A.

[Insert 10-page argument here.]

Which of the assertions proved in the foregoing 10 pages are false because they were deduced from the (now proved false) assumption that not A? Which are true but cannot be considered to have been validly proved because the proofs relied on the false assumption that not A? And which were validly proved since their proofs did not rely on that assumption? It can be hard to tell. And if you saw an assertion proved along the way, you might think it's known to be true.

In that way, a proof by contradiction can be at best confusing.

share|improve this answer
    
The 10-page argument is only for proving A. The main goal of this argument is to establish (via already proven theorems) that if not A then we get a result we know cannot be true. If you want to get something more valuable from the argument you have to go through it again and think of what you may be able to use in other contexts. Yes, proof by contradiction can be confusing but is much more than just confusing. –  AndreasS Oct 18 '12 at 17:12
    
Often though, Proof by contradiction arguments can be ALOT simpler than their direct proof counterparts. Personally, in general, I prefer what ever proof is simpler, faster and more easily generalised. –  John Marty May 1 '13 at 4:30
1  
It seems to me that it's often easier to find a proof by contradiction, but after that the proof often becomes clearer if rearranged into a direct proof. –  Michael Hardy May 1 '13 at 22:05

Sometimes you might want to know not just that there exists something, you might want to know how to actually go about finding it (and related questions like how quickly you can find it). Proofs by contradiction are non-constructive, while direct proofs are typically constructive in the sense that they actually construct an answer.

For example, the proof that there are infinitely many primes usually proceeds by contradiction. However, you can make it a direct proof which gives the stronger result that the nth prime is less than e^{e^n}. (This is a good exercise to work out for yourself, but you can also find it as Prop 1.1.3 in my senior thesis and probably many other places as well.)

share|improve this answer

Nearly always the direct proof is easier to understand, shorter, and more helpful!

share|improve this answer
7  
-1 Even if this is true "in-general," I know of many cases where proofs by contradiction are significantly more concise and elegant. –  Ami Jul 21 '10 at 3:39
1  
The question was why people are given this advice. Most advice doesn't actually apply to all situations ever. Advice by nature is an oversimplification. I think that's a bad downvote. –  Noah Snyder Jul 21 '10 at 3:41
3  
@Noah: Not really - I don't think Scott's statement is very accurate. The nicer proof is extremely context dependant –  Casebash Jul 21 '10 at 4:09
1  
Harry calm down... Scott and I are both confident enough that we're not offended by other people disagreeing with us. –  Noah Snyder Jul 21 '10 at 5:07
1  
-1. A quest for a direct proof is a philosophical aim that may not always agree with the mathematical aims. –  user218 Jul 28 '10 at 13:20

In mathematics you can construct a mathematical theory with different sets of axioms. This can be really useful. When mathematicians ignored the parallel line axiom in Euclidian geometry it gave raise to non-Euclidian geometries, which became really important in Einsteinian physics.

An axiom of logic is the law of the excluded third which basically says that one statement is either true or false. This means that any theorem that depends completely in this axiom is not valid on mathematical theories that decide to ignore the axiom.

A proof by contradiction is using the axiom directly; if the consequent is false then the antecent is false, then the converse of the consequent is true (because it must be either true or false). If the theorem can be proved in a constructive way, then it does not depend on the Law of Excluded Third and is valid in theories that does not use the law.

share|improve this answer
    
I believe that your third paragraph is a logical fallacy in the form of affirming the consequent. In short, you state "If $A$, then $B$. $\lnot B$. Therefore $\lnot A$." In general, any statement about $B$ can not be used to reason about $A$ in these situations. With statements in the form of "If $A$, then (something about $B$)", even the statement $\lnot A$ can not be used to reason about $B$. This is different from "$A$. If $\lnot B$, then $\lnot A$. $\lnot B$. Therefore $\lnot A$." - a contradiction. –  johne Jan 19 '11 at 20:35

Proof by contradiction is just as logically valid as any other type of proof. If you are unsure, I think it might help to consider exactly what a proof by contradiction entails.
Say we have a set of statements $\Gamma$, and that $\Gamma\cup\{(\neg\phi)\}$ is not consistent. That is, the statement $\neg\phi$ contradicts something in $\Gamma$. (In other words, we supposed $\phi$ was false, and reached a contradiction.) Say that statement was $\psi$. Then $\Gamma\cup\{(\neg\phi)\}\vdash\psi$ and $\Gamma\cup\{(\neg\phi)\}\vdash \neg\psi$. By the principle of explosion, we conclude that $\Gamma\cup\{(\neg\phi)\}\vdash\phi$. (We can prove any statement, so we prove $\phi$.
By deduction, we know that $\Gamma\vdash(\neg\phi\Rightarrow\phi)$.
Most first-order logic systems have an axiom that gives us $((\neg\phi\Rightarrow\phi)\Rightarrow\phi$. I hope you can convince yourself that this is true without trouble.
This yields $\Gamma\vdash\phi$.
We started with the idea that the negation of the statement $\phi$ was incompatible with your working set of axioms and theorems $\Gamma$, and concluded that therefore $\Gamma$ proves $\phi$.

Of course, there is more than one way to prove anything. Other methods can often be more intuitive, more elegant, or may lead to some other useful results. However, that is distinct from "weaker." Proof by contradiction is perfectly sound.

share|improve this answer
    
Not sure if my corrections are what you meant in the question. You wrote \rarrow. Do you want a simple arrow or a double one? –  Beni Bogosel Jul 16 '11 at 16:36
1  
"Proof by contradiction is perfectly sound." This completely misses the point. There are assumptions that make it sound, and carefully pointing out what they are and why people make them is what the questioner is asking. Not clearly indicating the assumptions and presenting a "proof of soundness" does not help answer the question. –  Matt Jul 18 '11 at 21:27

At first this seems like a silly question - after all isn't the point of a mathematical proof to be a proof and hence to be beyond question. But of course, to prove anything we need assumptions and some people do disagree with the axioms commonly used by mathematicians. I don't have much knowledge of this view, but I am sure they have theorems that show that contradiction like proofs are valid (given their axioms) within certain conditions. I would recommend going along with what everyone else does and treating "proofs by contradiction" as equally valid, unless you have investigated the Constructivism view and you decide that they are correct.

As to whether they are clearer, that will depend on the actual proof. Sometimes the clearest way to make a proof is to start from the assumptions and see what they are really saying and why that is going to lead to a contradiction. The most illustrative proof depends on the circumstances.

share|improve this answer

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.