Could I be using proof by contradiction too much?

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.

Solutions Collecting From Web of "Could I be using proof by contradiction too much?"

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.

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.

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:

  • Intuitionistic Logic
  • Law of Excluded Middle
  • Double Negation Elimination
  • Mathematical Constructivism

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).

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:

  • Can every proof by contradiction also be shown without
  • Are proofs by contradiction weaker than other types of proofs?

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.

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.

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

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.