## Proof by contradiction is never needed!

**Moderators:** gmalivuk, Moderators General, Prelates

### Proof by contradiction is never needed!

Many years ago a mathematician told me that you never need to use proof by contradiction. In cases where people use it, you can prove the contrapositive instead and it will generally be clearer. (The contrapositive is the fact that A implies B iff not-B implies not-A.) The proofs that can't be rewritten to use the contrapositive can be rewritten as direct proofs instead, which are also clearer.

For example, to prove that the list of all primes is infinite, it suffices to prove that any non-infinite list of primes is not the list of all of the primes. But if I have a non-infinite list of primes, just multiply together and add one, and I have a number that is not divisible by any of them, therefore the list is not complete. QED.

As you see, this is exactly the usual proof by contradiction, but without the confusing step of assuming something false.

While clearness is subjective, I was unable to come up with a counterexample to his claim. Furthermore he's right that students often try proof by contradiction, come up with the proof, and fail to see that they've just obscured a simpler direct proof.

When I had the opportunity to teach proofs, I took a tip from him. The handout that I gave explaining how to do proofs listed a series of techniques to try in order. The contrapositive came before contradiction. The result? My students never tried proof by contradiction because they'd solved their problems using other techniques first. And the quality of their proofs benefited from this.

Anyways I found this interesting, and I'm passing it along for other people's amusement. Try it! Take your favorite proof by contradiction and try to write it using the contrapositive instead.

For example, to prove that the list of all primes is infinite, it suffices to prove that any non-infinite list of primes is not the list of all of the primes. But if I have a non-infinite list of primes, just multiply together and add one, and I have a number that is not divisible by any of them, therefore the list is not complete. QED.

As you see, this is exactly the usual proof by contradiction, but without the confusing step of assuming something false.

While clearness is subjective, I was unable to come up with a counterexample to his claim. Furthermore he's right that students often try proof by contradiction, come up with the proof, and fail to see that they've just obscured a simpler direct proof.

When I had the opportunity to teach proofs, I took a tip from him. The handout that I gave explaining how to do proofs listed a series of techniques to try in order. The contrapositive came before contradiction. The result? My students never tried proof by contradiction because they'd solved their problems using other techniques first. And the quality of their proofs benefited from this.

Anyways I found this interesting, and I'm passing it along for other people's amusement. Try it! Take your favorite proof by contradiction and try to write it using the contrapositive instead.

Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

### Re: Proof by contradiction is never needed!

The reductio ad absurdum is well known to be a different way of expressing a direct proof of the contrapositive of a statement, without the extra step of stating the contrapositive. The benefit of pf by contradiction is the ability to "assume" (i.e. specify) exactly the property you wish to show can't hold. Some proofs are clearer as direct proofs of the contrapositive, and some are clearer as proofs by contradiction, IMO.

- Quanglement Entree
**Posts:**17**Joined:**Wed Jun 13, 2007 11:42 am UTC**Location:**Wellington, New Zealand-
**Contact:**

### Re: Proof by contradiction is never needed!

I was thinking about this recently, and I came to the conclusion that the preference to prove by contradiction is more a psychological thing than anything.

If you run a proof by contrapositive it doesn't feel like it `stuck' as well, because everything comes out nice and nothing much seems to have happened. Contradiction is theatrical, sparks fly, you can say `QED', and you feel like something important has happened.

If you run a proof by contrapositive it doesn't feel like it `stuck' as well, because everything comes out nice and nothing much seems to have happened. Contradiction is theatrical, sparks fly, you can say `QED', and you feel like something important has happened.

Because it's homocide when you start killing time.

### Re: Proof by contradiction is never needed!

I agree that sometimes proof by contradiction is unnescesary. For example, many times when you need to prove uniqueness of something (say a function), you would start with "let's say with have a function f and a function g which satisfy all the above conditions. Let's assume that f=/=g and we'll show that isn't possible." The you calculate f-g and find out it's always zero and thus a contradiction is achieved.

However, instead of that you could simply prove that any f and g which satisfy the above conditions much be equal.

I recently encountered a proof in my course in intro to Hilbert spaces and operators. The prof. used a proof by contradiction and we were sure it was just such a case and was not needed. In the end, he took a completely different turn and we were very surprised by the proof, plus it seemed we really needed it.

Of course technically you don't need to proove by contradiction but it makes things a lot easier sometimes (like in the second case).

However, instead of that you could simply prove that any f and g which satisfy the above conditions much be equal.

I recently encountered a proof in my course in intro to Hilbert spaces and operators. The prof. used a proof by contradiction and we were sure it was just such a case and was not needed. In the end, he took a completely different turn and we were very surprised by the proof, plus it seemed we really needed it.

Of course technically you don't need to proove by contradiction but it makes things a lot easier sometimes (like in the second case).

Mighty Jalapeno: "See, Zohar agrees, and he's nice to people."

SecondTalon: "Still better looking than Jesus."

Not how I say my name

SecondTalon: "Still better looking than Jesus."

Not how I say my name

### Re: Proof by contradiction is never needed!

btilly wrote:Many years ago a mathematician told me that you never need to use proof by contradiction. In cases where people use it, you can prove the contrapositive instead

...there's a difference?

Avatar yoinked from Inverloch.

"Unless ... unless they kill us, then animate our corpses as dead zombies to fight for them. Then I suppose they've taken our lives, AND our freedom."

- Elan, OOTS 421.

"Unless ... unless they kill us, then animate our corpses as dead zombies to fight for them. Then I suppose they've taken our lives, AND our freedom."

- Elan, OOTS 421.

### Re: Proof by contradiction is never needed!

Edit

Last edited by gmedina on Thu Nov 15, 2007 8:52 pm UTC, edited 1 time in total.

In Memoriam

### Re: Proof by contradiction is never needed!

blob wrote:btilly wrote:Many years ago a mathematician told me that you never need to use proof by contradiction. In cases where people use it, you can prove the contrapositive instead

...there's a difference?

Yes. Say you want to prove A -> B. A contrapositive proof proves ¬B -> ¬A. A proof by contradiction assumes A and ¬B, and creates a contradiction.

All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

### Re: Proof by contradiction is never needed!

What about the proof that sqrt(2) is irrational?

The direct statement would presumably be:

(x^2 = 2) => (x is irrational)

So the contrapositive would be that:

(x is rational) => (x^2 =/= 2)

This doesn't seem (to me) easy to do without contradiction somewhere.

The direct statement would presumably be:

(x^2 = 2) => (x is irrational)

So the contrapositive would be that:

(x is rational) => (x^2 =/= 2)

This doesn't seem (to me) easy to do without contradiction somewhere.

- Torn Apart By Dingos
**Posts:**817**Joined:**Thu Aug 03, 2006 2:27 am UTC

### Re: Proof by contradiction is never needed!

HenryS wrote:What about the proof that sqrt(2) is irrational?

The direct statement would presumably be:

(x^2 = 2) => (x is irrational)

So the contrapositive would be that:

(x is rational) => (x^2 =/= 2)

This doesn't seem (to me) easy to do without contradiction somewhere.

x=n/d => n^2 has an even number of 2s in its prime factorization, but 2d^2 has an odd number of 2s in its prime factorization, so n^2=/=2d^2 because prime factorizations are unique.

### Re: Proof by contradiction is never needed!

gmedina wrote:btilly wrote:Take your favorite proof by contradiction and try to write it using the contrapositive instead.

Not my favorite, just an example. Let's say you just genetically constructed Z (the ordered ring of integers) and you want to prove that Z has no lower (or upper) bound. Using a reductio ad absurdum argument gives you a one line proof. How would you proceed without RAA? Will another path produce a clearer demonstration?

Clearer is in the eye of the beholder. But showing that there is no upper bound is the same as proving that all integers are not upper bounds. (upper bound => not exists is equivalent to exists => not upper bound) Which is easy to do.

Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

### Re: Proof by contradiction is never needed!

Zohar wrote:I agree that sometimes proof by contradiction is unnescesary. For example, many times when you need to prove uniqueness of something (say a function), you would start with "let's say with have a function f and a function g which satisfy all the above conditions. Let's assume that f=/=g and we'll show that isn't possible." The you calculate f-g and find out it's always zero and thus a contradiction is achieved.

However, instead of that you could simply prove that any f and g which satisfy the above conditions much be equal.

And that is exactly the point. When you've concealed a direct proof like that, you can't do the translation from proof by contradiction to the contrapositive.

Zohar wrote:I recently encountered a proof in my course in intro to Hilbert spaces and operators. The prof. used a proof by contradiction and we were sure it was just such a case and was not needed. In the end, he took a completely different turn and we were very surprised by the proof, plus it seemed we really needed it.

Of course technically you don't need to proove by contradiction but it makes things a lot easier sometimes (like in the second case).

I'd be curious to see the example. I've never run across one where either the contrapositive wasn't just as easy, or the proof by contradiction wasn't necessary.

Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

### Re: Proof by contradiction is never needed!

I too try to avoid proofs by contradiction when I know of a way to prove the statement or its contrapositive directly. I find that this is usually clearer, since it demonstrates how the hypothesis naturally leads to the conclusion.

The typical method of showing that A implies B is to assume A and prove B. The method of proof by contradiction assumes "A and not B" and proves a contradiction. It is a theorem of first-order logic that either of these methods can be converted into a proof of the statement "A implies B" from the axioms alone. (Another theorem, for example, allows you to conclude "For all x, P(x)" by instead fixing an arbitrary x and proving P(x). All of these rules seem obvious, but we're talking about legal syntactic manipulations of proofs, which is more subtle.)

However, there are genuine examples where this isn't easy, typically ones which use both the hypothesis and the negated conclusion in several different ways during the course of the proof. For those proofs by contradiction that don't submit easily to conversion, I leave them as is and figure that a direct proof would probably be less clear overall.

The typical method of showing that A implies B is to assume A and prove B. The method of proof by contradiction assumes "A and not B" and proves a contradiction. It is a theorem of first-order logic that either of these methods can be converted into a proof of the statement "A implies B" from the axioms alone. (Another theorem, for example, allows you to conclude "For all x, P(x)" by instead fixing an arbitrary x and proving P(x). All of these rules seem obvious, but we're talking about legal syntactic manipulations of proofs, which is more subtle.)

However, there are genuine examples where this isn't easy, typically ones which use both the hypothesis and the negated conclusion in several different ways during the course of the proof. For those proofs by contradiction that don't submit easily to conversion, I leave them as is and figure that a direct proof would probably be less clear overall.

[This space intentionally left blank.]

### Re: Proof by contradiction is never needed!

Torn Apart By Dingos wrote:HenryS wrote:What about the proof that sqrt(2) is irrational?

The direct statement would presumably be:

(x^2 = 2) => (x is irrational)

So the contrapositive would be that:

(x is rational) => (x^2 =/= 2)

This doesn't seem (to me) easy to do without contradiction somewhere.

x=n/d => n^2 has an even number of 2s in its prime factorization, but 2d^2 has an odd number of 2s in its prime factorization, so n^2=/=2d^2 because prime factorizations are unique.

Uhhh, contradiction?

### Re: Proof by contradiction is never needed!

To make sure everyone is on the same page:

Reductio ad absurdum is equivalent to direct proof of contrapositive in all respects except presentation. (i.e. if you're proving the same thing with both, the calculation that gets done is the same and in the same order)

So what we really want to focus on is why a proof by contradiction might make the point more clearly (or not) than the contrapositive proof done directly.

Here's one thing I like about proof by contradiction. Since you know up front you want to produce a contradiction, you can say things like "But that case works, so we can assume the opposite is true. . ." I wish I could think of a good example of a proof that does this so I could compare to the equivalent direct proof.

Reductio ad absurdum is equivalent to direct proof of contrapositive in all respects except presentation. (i.e. if you're proving the same thing with both, the calculation that gets done is the same and in the same order)

So what we really want to focus on is why a proof by contradiction might make the point more clearly (or not) than the contrapositive proof done directly.

Here's one thing I like about proof by contradiction. Since you know up front you want to produce a contradiction, you can say things like "But that case works, so we can assume the opposite is true. . ." I wish I could think of a good example of a proof that does this so I could compare to the equivalent direct proof.

### Re: Proof by contradiction is never needed!

Owehn wrote:However, there are genuine examples where this isn't easy, typically ones which use both the hypothesis and the negated conclusion in several different ways during the course of the proof. For those proofs by contradiction that don't submit easily to conversion, I leave them as is and figure that a direct proof would probably be less clear overall.

Can you provide me with such an example? As I say, I've not encountered one.

Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

### Re: Proof by contradiction is never needed!

Here's a proof by contradiction of a simple fact that came up recently. There's a short proof by contradiction, but I don't know of a direct proof in either direction. (Like I said, I know there is one, but in this case I haven't bothered to look. So don't tell me about a direct proof unless it's just as short and just as clear, in which case I'll try to provide another example.)

Suppose we have a collection of real numbers c

Proof: Suppose there is some i for which c

The reason this might be difficult to convert into a direct proof is that you end up contradicting none of your assumptions (directly), but rather one of the things encountered along the way.

Suppose we have a collection of real numbers c

_{1}through c_{n}, and let C be their sum. Suppose furthermore that there are positive real numbers a_{1}through a_{n}such that c_{i}=-a_{i}C for each i from 1 to n. Then c_{i}=0 for all i.Proof: Suppose there is some i for which c

_{i}is nonzero; assume c_{i}is positive (the negative case works identically). Then C=-c_{i}/a_{i}<0. Hence for every j, c_{j}=-a_{j}C>0. Then C=Sum_{j}(c_{j})>0, contradicting the fact that C<0.The reason this might be difficult to convert into a direct proof is that you end up contradicting none of your assumptions (directly), but rather one of the things encountered along the way.

[This space intentionally left blank.]

### Re: Proof by contradiction is never needed!

Owehn wrote:Here's a proof by contradiction of a simple fact that came up recently. There's a short proof by contradiction, but I don't know of a direct proof in either direction. (Like I said, I know there is one, but in this case I haven't bothered to look. So don't tell me about a direct proof unless it's just as short and just as clear, in which case I'll try to provide another example.)

Suppose we have a collection of real numbers c_{1}through c_{n}, and let C be their sum. Suppose furthermore that there are positive real numbers a_{1}through a_{n}such that c_{i}=-a_{i}C for each i from 1 to n. Then c_{i}=0 for all i.

Proof: Suppose there is some i for which c_{i}is nonzero; assume c_{i}is positive (the negative case works identically). Then C=-c_{i}/a_{i}<0. Hence for every j, c_{j}=-a_{j}C>0. Then C=Sum_{j}(c_{j})>0, contradicting the fact that C<0.

The reason this might be difficult to convert into a direct proof is that you end up contradicting none of your assumptions (directly), but rather one of the things encountered along the way.

Thm: If there are c's and a's s.t. c

_{1}+...+c

_{n}=C and c

_{i}=-a

_{i}C, a

_{i}positive, then all c's are 0.

(one possible) Contrapositive: If some c

_{i}!= 0 and c

_{i}=-a

_{i}C, then c

_{1}+...+c

_{n}!= C

Pf of contrapositive:

Let c

_{i}be positive (negative case works identically). Since c

_{i}=-a

_{i}C and a

_{i}positive, it must be that C is negative. Thus, all c's must be positive. But then sum of c's is positive, and C is negative, so sum of c's != C.

It submits just as nicely to a direct proof. Sorry.

### Re: Proof by contradiction is never needed!

C was just convenient shorthand for Sum

Granted, that wasn't the best example. I'll see if I can dig up another one.

_{j}(c_{j}) - it wasn't really one of the hypotheses of the theorem. The proof by contradiction I gave still works, but yours turns into another proof by contradiction.Granted, that wasn't the best example. I'll see if I can dig up another one.

[This space intentionally left blank.]

### Re: Proof by contradiction is never needed!

blob wrote:btilly wrote:Many years ago a mathematician told me that you never need to use proof by contradiction. In cases where people use it, you can prove the contrapositive instead

...there's a difference?

Exactly.

- Indigo is a lie.

Which idiot decided that websites can't go within 4cm of the edge of the screen?

There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

### Re: Proof by contradiction is never needed!

Owehn wrote:C was just convenient shorthand for Sum_{j}(c_{j}) - it wasn't really one of the hypotheses of the theorem. The proof by contradiction I gave still works, but yours turns into another proof by contradiction.

Granted, that wasn't the best example. I'll see if I can dig up another one.

In your proof, C was shorthand for the sum of the c's. In mine, it was any number. Either way, I proved what you proved by contradiction directly (by proving the contrapositive). The other contrapositive I could have used would have used your notion of C being shorthand for the sum of c's, and would be as simple to prove directly:

If some c

_{i}>0 and sum of c's=C, then for any j, c

_{j}!=-a*C for any positive a.

Try it yourself and see.

### Re: Proof by contradiction is never needed!

OK, I found the theorem. According to my notebook it's by Fredholm.

Theorem: Let T be a compact operator over a Hilbert space H. Let c=/=0, S is the operator S=cI-T (I = identity operator) and suppose ImageS=H. Then kernelS={0}.

The proof we were given is by contradiction. For the purpose of the proof I'll use the symbol A<B to denote "A is a subset of B".

Boy, I needed a lot of sub and sup tags for that...

You may find a proof without the use of a contradiction (I didn't look for one), but the point is that the contradiction here is pretty surprising.

Theorem: Let T be a compact operator over a Hilbert space H. Let c=/=0, S is the operator S=cI-T (I = identity operator) and suppose ImageS=H. Then kernelS={0}.

The proof we were given is by contradiction. For the purpose of the proof I'll use the symbol A<B to denote "A is a subset of B".

**Spoiler:**

Boy, I needed a lot of sub and sup tags for that...

You may find a proof without the use of a contradiction (I didn't look for one), but the point is that the contradiction here is pretty surprising.

Mighty Jalapeno: "See, Zohar agrees, and he's nice to people."

SecondTalon: "Still better looking than Jesus."

Not how I say my name

SecondTalon: "Still better looking than Jesus."

Not how I say my name

### Re: Proof by contradiction is never needed!

gmedina wrote:btilly wrote:Take your favorite proof by contradiction and try to write it using the contrapositive instead.

Not my favorite, just an example. Let's say you just genetically constructed Z (the ordered ring of integers) and you want to prove that Z has no lower (or upper) bound. Using a reductio ad absurdum argument gives you a one line proof. How would you proceed without RAA? Will another path produce a clearer demonstration?

I have z in Z, chosen arbitrarily. z + 1 is also in Z. Therefore z is not an upper bound of Z.

[tea time!]

edit: Put slightly differently, the statement "There is no upper bound of a set S" is equivalent to "For all x in S, there exists a y in S which is greater than x." For the integers, we can use the generation of Z itself to make this statement: For all z in Z, z + 1 is in Z.

31/M/taken/US

age/gender/interest/country

age/gender/interest/country

Belial wrote:The sex card is tournament legal. And I am tapping it for, like, six mana.

### Re: Proof by contradiction is never needed!

So far, nearly every proof-by-contradiction converted to a proof-by-contrapositive has been along the following lines:

Suppose that from not-B we can derive a contradiction. Let A be a true statement, so that the contradiction implies not-A (often not-A was the contradiction to begin with). Then from not-B we can derive not-A, which we interpret as a proof of the contrapositive of "A implies B". Since A is true, "A implies B" is equivalent to B. Therefore we have converted the proof by contradiction of B into a proof by contrapositive.

For example, suppose the last line of the proof is "So 2 does not equal 2, a contradiction." Then I adjust what I think of as the hypotheses of the proof to include 2=2, and wham-o, suddenly my proof has become a proof of the contrapositive of the new theorem's statement. For a more genuine example, the proof about operators in Hilbert Space can be reinterpreted as a direct proof that "If S = c - T, where c is nonzero, ker S is nonzero, and im S = H, then T is not compact." That might actually make the statement and proof of the theorem more clear.

However, this is generally a bit disingenuous. Suppose that the proposition B, whose negation implied a contradiction, is actually an implication "S implies T." Then the so-called contrapositive we end up with isn't the contrapositive of B, "not-T implies not-S", but rather it's "not-(S implies T) implies not-A", i.e. "S and not-T together imply not-A". Since we chose A to be a true statement, most of us would simply recognize this as another statement of a proof by contradiction. So the method I've described (the one people appear to be using for the most part) to convert proofs by contradiction into proofs by contrapositive typically don't gain any clarity, and often gain unnecessary length by explaining how the new hypothesis fits in.

Going back to the Hilbert Space example, suppose that the proof by contradiction had actually required the compactness of T, rather than just contradicting it at the end. Then the proof by contrapositive would become:

Suppose S = c - T, c is nonzero, ker S is nonzero, and im S = H.

Either T is compact or T is not compact.

If T is not compact, we're done.

If T is compact, then ... [insert the proof by contradiction here, which requires the compactness of T] ... T is not compact.

Either way, T is not compact.

So the new proof just contains the old one, shrouded in some weird restatements of the hypotheses, all so that a proof by contradiction can be converted into a supposedly more clear proof by contrapositive. Not worth it, in my opinion.

Edit: I never thought I'd find myself arguing for the use of proofs by contradiction! Usually I'm telling people to avoid them if they can. However, I do think that sometimes a proof by contradiction can be more clear than the proof by contrapositive it induces, in which case the proof by contradiction should be used.

Suppose that from not-B we can derive a contradiction. Let A be a true statement, so that the contradiction implies not-A (often not-A was the contradiction to begin with). Then from not-B we can derive not-A, which we interpret as a proof of the contrapositive of "A implies B". Since A is true, "A implies B" is equivalent to B. Therefore we have converted the proof by contradiction of B into a proof by contrapositive.

For example, suppose the last line of the proof is "So 2 does not equal 2, a contradiction." Then I adjust what I think of as the hypotheses of the proof to include 2=2, and wham-o, suddenly my proof has become a proof of the contrapositive of the new theorem's statement. For a more genuine example, the proof about operators in Hilbert Space can be reinterpreted as a direct proof that "If S = c - T, where c is nonzero, ker S is nonzero, and im S = H, then T is not compact." That might actually make the statement and proof of the theorem more clear.

However, this is generally a bit disingenuous. Suppose that the proposition B, whose negation implied a contradiction, is actually an implication "S implies T." Then the so-called contrapositive we end up with isn't the contrapositive of B, "not-T implies not-S", but rather it's "not-(S implies T) implies not-A", i.e. "S and not-T together imply not-A". Since we chose A to be a true statement, most of us would simply recognize this as another statement of a proof by contradiction. So the method I've described (the one people appear to be using for the most part) to convert proofs by contradiction into proofs by contrapositive typically don't gain any clarity, and often gain unnecessary length by explaining how the new hypothesis fits in.

Going back to the Hilbert Space example, suppose that the proof by contradiction had actually required the compactness of T, rather than just contradicting it at the end. Then the proof by contrapositive would become:

Suppose S = c - T, c is nonzero, ker S is nonzero, and im S = H.

Either T is compact or T is not compact.

If T is not compact, we're done.

If T is compact, then ... [insert the proof by contradiction here, which requires the compactness of T] ... T is not compact.

Either way, T is not compact.

So the new proof just contains the old one, shrouded in some weird restatements of the hypotheses, all so that a proof by contradiction can be converted into a supposedly more clear proof by contrapositive. Not worth it, in my opinion.

Edit: I never thought I'd find myself arguing for the use of proofs by contradiction! Usually I'm telling people to avoid them if they can. However, I do think that sometimes a proof by contradiction can be more clear than the proof by contrapositive it induces, in which case the proof by contradiction should be used.

[This space intentionally left blank.]

### Who is online

Users browsing this forum: No registered users and 11 guests