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.

Possible Duplicate:
Are the “proofs by contradiction” weaker than other proofs?

I have been active on this site for two months and on a few occasions I noticed that some people judge contradiction proofs as being less direct(and less elegant) than proofs which do not use contradiction.

In my first year of college I gave headaches to my seminar teacher and my colleagues because I used most of the time proof by contradiction. For me it seemed so natural to argue by contradiction whenever I didn't have any idea to how to proceed in solving the problem directly. At least when you prove something by contradiction, you have a start point, a supplementary hypothesis on which you can develop the following arguments searching for a contradiction with the hypothesis or previous work (theorems, problems, etc.).

Therefore, my question is:

Why do some consider that contradiction proofs are not that good as direct proofs?

share|improve this question

marked as duplicate by Carl Mummert, t.b., Chandru, Qiaochu Yuan Jul 16 '11 at 16:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2  
I don't think I can give a good answer; while you wait for one, you should see read on intuitionistic logic (en.wikipedia.org/wiki/Intuitionistic_logic) –  Bruno Stonek Jul 16 '11 at 11:27
3  
Did you see this old thread here? Also look at the various threads in the linked/related column on the right. –  t.b. Jul 16 '11 at 11:35
2  
Well G.H.Hardy won't agree with you: “Reductio ad absurdum, which Euclid loved so much, is one of a mathematician’s finest weapons. It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game ”. –  user9413 Jul 16 '11 at 11:51
2  
If I could choose between having a constructive proof and a contradiction proof, I'd take the constructive proof any day. –  J. M. Jul 16 '11 at 11:55
2  
Two separate questions: Proof of nonexistence by contradiction is fine. But proof of existence by contradiction is less satisfactory: instead one would like a construction of the item asserted to exist. –  GEdgar Jul 16 '11 at 13:17

6 Answers 6

up vote 18 down vote accepted

I find it harder to read and proofread proofs by contradiction for the following reason: In an ordinary proof, one is trying to show $P \implies Q$. When I read it, I will have in my head a few examples of different things that obey $P$, and I'll check that each step in the proof is consistent with my examples. Hopefully, the last line of the proof will be "$Q$", and everything will work.

In a proof by contradiction, we start out assuming $P \wedge NOT(Q)$. If the theorem is true, there are no examples of things of things which obey $P$ and not $Q$, so I can't think of any examples.

Note that this problem does not arise in proofs which start out by assuming $NOT(Q)$ and deduce $NOT(P)$ at the end, since I can think of examples of things which obey $NOT(Q)$. I have taken to starting these proofs by writing "We establish the contrapositive, that $NOT(Q)$ implies $NOT(P)$" rather than my standard "This proof proceeds by contradiction. Assume...". My hope is that this will help my readers understand that there are still examples available for them to think about.

share|improve this answer
    
+1 for pointing out the contrapositive. –  Hendrik Vogt Jul 16 '11 at 13:53
    
but if what you're going to prove is not constructive to begin with ie. a non-existence then a proof by contradiction will be easier to do. I mean it depends on what you are trying to prove - something "positive" (like an existence) or something "negative" (a non-existence) –  909 Niklas Jul 16 '11 at 15:27
1  
+1, especially for good advice on mathematical writing. At this point I have certainly put in thousands of hours of writing mathematics. Before my first few thousand hours, I would often assume that I didn't have to say much about the logical structure of an argument. In particular I would often start proofs by contradiction by "Proof: suppose not. Then..." Just recently I noticed that I have become more formal about this: "Seeking a contradiction, we suppose..." You can't be too careful in setting things up (well, you could, I suppose, but I have never seen it...) –  Pete L. Clark Jul 16 '11 at 22:21
    
I also agree that if something is an argument by contrapositive, then you should phrase it that way and not as an argument by contradiction, as David has explained quite well. In some recent notes I found myself writing things like $\lnot$ (iii) $\implies$ $\lnot$ (ii) when proving that (ii) implies (iii) by contrapositive. I'm not sure whether this will stand the test of time... –  Pete L. Clark Jul 16 '11 at 22:26

Philosophical issues aside, a point that's been left out: what's better when proving need not be what's better when writing down the proof.

You say "For me it seemed so natural to argue by contradiction…", and you're right: yes, it is often easier when proving to argue by contradiction, but the version without contradiction is often easier to read (and therefore better to write).

When you're trying to prove $P \implies Q$, if you prove by contradiction, then you get to assume both $P$ and $\lnot Q$ before exploring their consequences, so in principle it's never worse than assuming $P$ alone: proving by contradiction never hurts. But after you've finished the proof, it's worth going over your proof and seeing if it can be written directly.

That is, the issue (stylistically speaking) is not so much with proof by contradiction per se, but with writing a proof in terms of contradiction when it's not necessary or helpful. ("Proof by unnecessary contradiction".) See e.g. Mathematical Writing (by Donald Knuth, Tracy Larrabee, and Paul M. Roberts) for this (emphasis added):

The proof above actually commits another sin against mathematical exposition, namely the unnecessary use of proof by contradiction. It would have been better to use a direct proof…

Sometimes (often) the direct proof may be easier to read and more illuminating, and sometimes it may not. It is always worth considering both versions and choosing the one that's easier to read. You owe it to your readers to think carefully about how best to organise your proof.

share|improve this answer

To take a simple example, supposed you wanted to prove that $9$ was a composite number.

You know from Fermat's little theorem that $a^p-a$ is divisible by $p$ if $p$ is prime, but $2^9-2 = 510$ is not divisible by $9$, implying by contradiction that $9$ is not prime.

This is a fully logical proof which (combined with the fact $9$ is not a unit) answers the question, but I personally would regard showing directly that $9 = 3 \times 3$ as being more informative.

share|improve this answer

I should elaborate on what I mean by weaker logics being more applicable.

Most mathematicians do believe that the world of mathematics is governed by the laws of classical logic. But there are worlds within mathematics itself which are not: although we may study such a mathematical universe using a classical background, the internal laws may not be classical. You might be dismissive and say that non-classical logic do not show up in ‘real’ mathematics, but the fact is that they do, albeit in somewhat disguised form. I give three examples:

  1. The Curry–Howard correspondence between the type theory of computation and intuitionistic logic. In essence, if you can prove a propositional formula in intuitionistic propositional calculus, then, we can interpret the proof as a computer program, and the logical formulae as type declarations for the program; conversely, if you have a computer program, then its type declarations can be interpreted as logical formulae, and the program itself is a proof.

  2. The algebra of open sets in a topological space forms a complete Heyting algebra: in particular, it is a model of intuitionistic propositional logic. A particularly memorable application of this is Kuratowski's closure–complement problem: indeed, if we denote by $\lnot A$ the interior of the complement of an open subset $A$ of a topological space $X$, then the fact that $\lnot \lnot \lnot A = \lnot A$ is nothing more than a special case of the general fact that $\lnot \lnot \lnot p$ and $\lnot p$ are equivalent in intuitionistic logic.

  3. Generalising the previous example, a remarkable discovery of the mid-20th century showed that much of mathematics is interpretable in the categories of sheaves on a topological space. Such categories are known as toposes. The category of sets is, of course, a topos, but it just one of many. The theory of rings can be interpreted in any topos (or, indeed, any category with a terminal object and finite products), and such an interpretation is known as a ring object. A ring object in the category of sets is just a ring as we know it, and a ring object in the category of topological spaces is a topological ring, and so on.

    What about a ring object in a category of sheaves? Well, there, a ring object is the same thing as a sheaf of rings. This means that we can treat, say, the structure sheaf of a scheme as essentially the same thing as an exotic ring, and anything we can prove about rings will also be true of the sheaf, interpreted appropriately. With one catch: the proofs must be intuitionistically valid, because the internal logic of a topos is in general intuitionstic. (The internal logic of more general categories are even less pleasant.) In particular, double negation elimination is invalid, so any theorems proven by contradiction become suspect (but not necessarily untrue).

share|improve this answer

I believe some people do not like proof by contradiction because it does not, typically, seem to lead to new mathematics or new ideas. This is a rather general statement, but I think many will concur.

share|improve this answer
2  
Hmm, I don't think I agree with this. Can you give an example of a theorem that was first proved by contradiction and then stagnated until a more direct / constructive proof was found? (I certainly agree that if you don't know how to prove a result directly and someone else does, then she has some new idea that you don't. But I don't think this is what you're claiming.) –  Pete L. Clark Jul 16 '11 at 22:31

To prove something is impossible, you probably can't have a constructive proof and it's ease to understand the counterproof: You just assume that it's possible and derive a contradiction and you're done. Any other way to prove an impossibility?

share|improve this answer
    
Is this an answer to the question, or a question questioning the question? It should be left as a comment, I think. Anyway, proof by negation is not the same as proof by contradiction; see e.g. math.andrej.com/2010/03/29/… –  ShreevatsaR Jul 16 '11 at 15:46
    
OK. Trying to answer the question more I say that a constructive proof can be more compelling to people since it's more straightforward, but at the same time it seems like there is no way to prove an impossibility using modus ponens: To prove an impossibility the way to prove looks like proof by contradiction –  909 Niklas Jul 25 '11 at 12:33
1  
Did you actually read the above link? To prove an impossibility, what you usually use is proof by negation, which is not proof by contradiction! –  ShreevatsaR Jul 25 '11 at 12:48
    
I've never heard of that difference knowing the difference between inducative prrofs and counterexamples this was a third method I'm going to check –  909 Niklas Aug 12 '11 at 2:08
    
I looked at what you call proving negation and its still reducio ad absurdum so its true that both methods are the same: reducio ad absurdum using counterexample. –  909 Niklas Aug 12 '11 at 2:12

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