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.

Lately, I've developed a habit of proving almost everything by contradiction. Even for theorems for which direct proofs are the clear choice, I'd just start by writing "Assume not" then prove it directly, thereby reaching a "contradiction." Is this a bad habit? I don't know why, but there's something incredibly satisfying about proof by contradiction.

share|improve this question
7  
If you are trying to show that there is no object thathas certain properties, contradiction is OK. I would suggest trying to avoid it in other situations, by rewriting your argument. –  André Nicolas Mar 3 '13 at 22:45
85  
See if you can go for 24 hours without using proof by contradiction. If not, you may have a real problem. There are twelve-step programs for this, with anonymous meetings where addicts support each other and share life stories. –  Will Jagy Mar 3 '13 at 23:03
17  
For all its faults, I love proof by contradiction, simply because of the tone it lends to one's writing. "... Proof: Suppose for a moment that we live in a crazy, backwards world where I could be wrong. Now let me show you why that assumption is incorrect." –  Alexander Gruber Mar 4 '13 at 3:12
23  
There's nothing wrong with proving things by contradiction. Here's why. Assume that there is something wrong with proving things by contradiction... –  LarsH Mar 4 '13 at 3:57
8  
"Hi, Everyone. It's my first time at the AAA. Now suppose that my name isn't Jack. I will show that this leads to a falsehood that is all the more repugnant for its subtlety." –  Kaz Mar 4 '13 at 8:46

7 Answers 7

up vote 80 down vote accepted

One general reason to avoid proof by contradiction is the following. When you prove something by contradiction, all you learn is that the statement you wanted to prove is true. When you prove something directly, you learn every intermediate implication you had to prove along the way.

More explicitly, if you want to prove that $p \Rightarrow q$ by contradiction, you assume $p$ and $\neg q$ and derive a contradiction. None of the intermediate implications along the way can be reused because your premises were contradictory.

If you want to prove that $p \Rightarrow q$ directly, say by proving that $p \Rightarrow p_1$ and $p_1 \Rightarrow p_2$ and so on until $p_n \Rightarrow q$, then you've also proven that $p_i \Rightarrow p_{i+1}$ for all of the relevant $i$. Many of these statements might be more useful than the original statement you were trying to prove.

Another general reason to avoid a proof by contradiction is that it is often not explicit. For example, if you want to prove that something exists by contradiction, you can show that the assumption that it doesn't exist leads to a contradiction. But this doesn't necessarily give you a method for constructing the actual thing, which you might learn more from trying to do.

A third reason is that frequently, or so it seems to me, a proof by contradiction is really a proof by contrapositive, where you assume $\neg q$ and derive $\neg p$. This feels like a proof by contradiction except that you never make use of the hypothesis $p$ except at the very end, and pretending that these are proofs by contradiction will make you blind to the fact that any intermediate implications you prove in a proof by contrapositive are still valid.

share|improve this answer
1  
As you say, a proof by contradiction is much the same as a proof by contrapositive. But doesn't that mean that the implications alongside a proof by contradiction can be reused for a direct proof $\neg q\implies \neg p$? So in my opinion, the choice of the proof method it more about which direction is more "natural", $p \implies q$ or $\neg q \implies \neg p$. –  azimut Mar 4 '13 at 18:41
3  
@azimut: in a "real" proof by contradiction, you need to use both the hypothesis $\neg q$ and the hypothesis $p$ in a nontrivial way, e.g. perhaps you need both hypotheses to construct some object and then you show that this object has contradictory properties. –  Qiaochu Yuan Mar 4 '13 at 19:19
    
I sometimes conflate the contrapositive and contradiction proofs myself. –  Joe Z. Mar 7 '13 at 20:07

In my opinion the proof by contradiction is a bad habit, when there is a direct proof. I always have the feeling that proofs by contradiction aren't so elegant, as it is necessary to read them several times, to see how someone got the idea that the contradiction will work.

A good proof does not only prove something but gives a way. In a direct proof you always know where you are, at a proof by contradiction there is at the end the contradiction which is more or less easy to see.

share|improve this answer
    
I would second this comment. –  copper.hat Mar 3 '13 at 22:36
6  
Many would also argue that they are a "bad habit" also because of possible foundational issues not just elegance. –  Matt Mar 3 '13 at 22:38

It's certainly good to know how to proceed with a proof by contradiction, and to have a firm grasp of its logic. You'll encounter them often. When students first grasp the logic of such a proof, and succeed in constructing those proofs, they often become enamored by them, especially given the satisfaction some get by "disproving" something.

But it really is in your best interest to develop facility with direct proofs, with proof by induction, proof by cases, etc. Certainly, there are some domains in math, and in particular, certain types of problems and problem statements in which an indirect proof is used more commonly or is even most appropriate. But that is also true of direct proofs, and inductive proofs, and when you become comfortable with those approaches, there is satisfaction that one gets after having affirmed, "established" and/or constructed the result, not just by tearing down the negation of the result.

It's sort of like arguments: one can give tons of reasons why something won't work, and cynics like to do this. The more elegant, informative, and creative arguments establish "why something will work," and explain why.

The bottom line: work to develop skill, mastery, and facility with direct proof and its variations. Sure, the use of indirect proofs is an indispensable tool. But why limit yourself to one tool, when you can acquire many tools, each of which works better to build some proofs in a particular context than do the others. You want to develop the flexibility to know how, and when, to use them all, as they are all indispensable.

You might be interested in these previous posts:

The answers given in these posts, and the links available there, offer a lot of perspectives on the merits and appropriateness of proof-by-contradiction. There have been a number of similar posts, asking questions similar to yours. If I can root them out, I'll return to post a link.

share|improve this answer
    
Indeed some of the answers in those referenced posts are first class. –  Daniel Dinnyes Mar 5 '13 at 21:02

Let me quickly summarize what you can find in some of the other answers, then I will throw my two cents on top of that:

  • Proof is a proof, as long as it is sound. Maybe something cannot be proved by contradiction but otherwise it is just as good as direct proof.
  • Somehow many feel that Reducio Ad Absurdum is less elegant, or less intuitive.

Now my two cents. Please take a look at the following Wikipedia articles:

As you can see there is a branch of mathematical logic, called Intuitionistic Logic, which does not accept the Law of Excluded Middle as an axiom, and because of this the Double Negation Elimination can not be used there. These assumptions lead to a branch of mathematics which – they say – more down-to-earth and more intuitive (see mathematical constructivism, constructive set theory, etc). Take for example the below quotation from the Intuitionistic Logic page:

Constructive logic is practically useful because its restrictions produce proofs that have the existence property, making it also suitable for other forms of mathematical constructivism. Informally, this means that if you have a constructive proof that an object exists, you can turn that constructive proof into an algorithm for generating an example of it.

— removed misleading paragraph about Cantor's diagonal argument —

So to summarize, by going with an existential proof you satisfy even the intuitionistic requirements, therefore it is a reasonable argument to prefer it over a proof by contradiction, which relies on further assumptions (i.e. Law of Excluded Middle).

share|improve this answer
1  
You have made a common mistake: Cantor's diagonal argument is a proof of a negative statement, and as such is perfectly valid proof in the intuitionistic framework. Additionaly, the Axiom of infinity is not rejected by all intuitionists, though the schism between intuitionist mathematics and classical mathematics is more significant in situations where that axiom holds. –  cody Mar 7 '13 at 19:08
    
@cody You are right, it is rather an example of proof by contrapositive –  Daniel Dinnyes Mar 7 '13 at 19:44

Basically, a proof is a proof, as long as it is sound.

However, if there is the choice of a direct and a indirect proof of similar complexity, typically the direct one is considered to be more "elegant".

My suggestion is: The next time you proof something by contradiction, try also to find a direct proof (this may or may not be so easy). If you succeed, compare your proofs and decide which one you like better.

share|improve this answer

As @azimut says, as long as the reasoning holds, proving by contradiction is fine. However, it is a good idea to develop your proof skills by trying to prove results using other methods, as sometimes contradiction will make the proof more complicated than need be. Other methods can be more elegant and/or more clear. Also, when first learning proof techniques, it is easy to think that something has been proved by contradiction when it really has not. I have seen students get confused by what is being contradicted and even what the contradiction is, so as long as you're proving things by contradiction, be careful to check that it's really a proof: check that the right thing is being contradicted, that what you've done is legal, and that the conclusion you've come to is a contradiction.

share|improve this answer

I think proofs by contradiction are fine; in fact, if one keeps their eyes open for an inconsistency in the foundations of mathematics, it could be a multimillion dollar endeavor. In particular:

STEP 1: Find an inconsistency in ZFC (or other widely used set of axioms).

STEP 2 (Important): Don't tell anyone about it.

STEP 3: Gather a list of the remaining millennium prize problems.

STEP 4: Prove each one by contradiction. By this I mean something like

Assume the Riemann Hypothesis is false. Then ( * cleverly and discretely exhibit inconsistency in ZFC * ), which is a contradiction. Thus RH is true. Please send the check to ( * insert address here * ).

STEP 5: ??????

STEP 6: Profit

share|improve this answer
    
Here is the relevant xkcd: xkcd.com/816 –  Daenerys Naharis Mar 4 '13 at 19:35
1  
why is this joke upvoted? it has nothing to do with the question. –  the L Mar 5 '13 at 8:11
1  
    
@Joseph: This does answer the question as it does say that nothing is wrong with contradiction (as do the rest of the answers). However, the joke following would probably best have been left as a comment. –  robjohn Mar 5 '13 at 11:09
1  
Step 4.5: ?????? –  Joe Z. Mar 7 '13 at 20:11

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.