Proof by contradiction is never needed!

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Proof by contradiction is never needed!

Postby btilly » Thu Nov 08, 2007 3:23 am UTC

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.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Proof by contradiction is never needed!

Postby quintopia » Thu Nov 08, 2007 3:54 am UTC

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.

User avatar
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!

Postby Quanglement Entree » Thu Nov 08, 2007 8:41 am UTC

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.
Because it's homocide when you start killing time.

User avatar
Zohar
COMMANDER PORN
Posts: 8570
Joined: Fri Apr 27, 2007 8:45 pm UTC
Location: Denver

Re: Proof by contradiction is never needed!

Postby Zohar » Thu Nov 08, 2007 10:40 am UTC

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).
Mighty Jalapeno: "See, Zohar agrees, and he's nice to people."
SecondTalon: "Still better looking than Jesus."

Not how I say my name

User avatar
blob
Posts: 350
Joined: Thu Apr 05, 2007 8:19 pm UTC

Re: Proof by contradiction is never needed!

Postby blob » Thu Nov 08, 2007 2:26 pm UTC

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.

gmedina
Posts: 109
Joined: Mon Aug 27, 2007 4:36 pm UTC
Location: Colombia

Re: Proof by contradiction is never needed!

Postby gmedina » Thu Nov 08, 2007 3:15 pm UTC

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

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Proof by contradiction is never needed!

Postby Token » Thu Nov 08, 2007 3:31 pm UTC

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.

User avatar
HenryS
Posts: 199
Joined: Mon Nov 27, 2006 9:16 am UTC
Location: Melbourne
Contact:

Re: Proof by contradiction is never needed!

Postby HenryS » Thu Nov 08, 2007 3:54 pm UTC

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.

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

Re: Proof by contradiction is never needed!

Postby Torn Apart By Dingos » Thu Nov 08, 2007 4:04 pm UTC

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.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Proof by contradiction is never needed!

Postby btilly » Thu Nov 08, 2007 4:17 pm UTC

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.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Proof by contradiction is never needed!

Postby btilly » Thu Nov 08, 2007 4:21 pm UTC

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.

User avatar
Owehn
Posts: 479
Joined: Tue Oct 09, 2007 12:49 pm UTC
Location: Cambridge, UK

Re: Proof by contradiction is never needed!

Postby Owehn » Thu Nov 08, 2007 4:32 pm UTC

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.
[This space intentionally left blank.]

aguacate
Posts: 209
Joined: Fri Feb 16, 2007 10:29 pm UTC

Re: Proof by contradiction is never needed!

Postby aguacate » Thu Nov 08, 2007 4:35 pm UTC

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?
Image

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Proof by contradiction is never needed!

Postby quintopia » Thu Nov 08, 2007 4:38 pm UTC

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.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Proof by contradiction is never needed!

Postby btilly » Thu Nov 08, 2007 4:38 pm UTC

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.

User avatar
Owehn
Posts: 479
Joined: Tue Oct 09, 2007 12:49 pm UTC
Location: Cambridge, UK

Re: Proof by contradiction is never needed!

Postby Owehn » Thu Nov 08, 2007 5:37 pm UTC

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 c1 through cn, and let C be their sum. Suppose furthermore that there are positive real numbers a1 through an such that ci=-aiC for each i from 1 to n. Then ci=0 for all i.

Proof: Suppose there is some i for which ci is nonzero; assume ci is positive (the negative case works identically). Then C=-ci/ai<0. Hence for every j, cj=-ajC>0. Then C=Sumj(cj)>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.]

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Proof by contradiction is never needed!

Postby quintopia » Thu Nov 08, 2007 5:56 pm UTC

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 c1 through cn, and let C be their sum. Suppose furthermore that there are positive real numbers a1 through an such that ci=-aiC for each i from 1 to n. Then ci=0 for all i.

Proof: Suppose there is some i for which ci is nonzero; assume ci is positive (the negative case works identically). Then C=-ci/ai<0. Hence for every j, cj=-ajC>0. Then C=Sumj(cj)>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. c1+...+cn=C and ci=-aiC, ai positive, then all c's are 0.
(one possible) Contrapositive: If some ci != 0 and ci=-aiC, then c1+...+cn != C

Pf of contrapositive:
Let ci be positive (negative case works identically). Since ci=-aiC and ai 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.

User avatar
Owehn
Posts: 479
Joined: Tue Oct 09, 2007 12:49 pm UTC
Location: Cambridge, UK

Re: Proof by contradiction is never needed!

Postby Owehn » Thu Nov 08, 2007 6:13 pm UTC

C was just convenient shorthand for Sumj(cj) - 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.]

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: Proof by contradiction is never needed!

Postby Macbi » Thu Nov 08, 2007 6:49 pm UTC

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.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Proof by contradiction is never needed!

Postby quintopia » Thu Nov 08, 2007 7:05 pm UTC

Owehn wrote:C was just convenient shorthand for Sumj(cj) - 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 ci>0 and sum of c's=C, then for any j, cj!=-a*C for any positive a.

Try it yourself and see.

User avatar
Zohar
COMMANDER PORN
Posts: 8570
Joined: Fri Apr 27, 2007 8:45 pm UTC
Location: Denver

Re: Proof by contradiction is never needed!

Postby Zohar » Thu Nov 08, 2007 7:09 pm UTC

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

Spoiler:
Suppose y0 is a member of kerS and that y0=/=0.
This is where we thought he wouldn't need the contradiction, because he'll just show that y0=0 so why use contradiction? We were wrong, apparently. Anyway:
ImS=H so there exists a y1 such that Sy1=y0. Let's create a sequence of yn's such that for each n, Syn+1=yn.

Now let's define a sequence of spaces: En=span{y0,...,yn}.
Then E0<E1<E2<...
Also, Sn+1En={0} but Sn+1yn+1=y0=/=o. Therefor, yn+1 is not a member of En. So SEn is a subset of En-1 and not equal to En-1.

For each n we'll choose a vector en from En such that en is orthogonal to En-1 and ||en||=1 (we can because of what we just showed). Assume m<n. Then:
||Ten-Tem|| = ||cen-(cen-Ten)+(cem-em)-em|| = ||cen-Sen+Sem-cem|| >= ||cen|| = |c| =/=0

The reason for the first inequality is that the first part cen is from En and it's orthogonal to all the rest of the summed parts. So anyway, we see that in Ten can't contain a Cauchy sub-sequence in contradiction to T being compact. You see, it seems almost completely unrelated to y0 not being zero. You must assume that it is different than zero for it to work, it's not enough to say that it's a general vector and find that it is zero. If it's not zero, the proof doesn't work (therein lies the contradiction, of course).


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

User avatar
rrwoods
Posts: 1509
Joined: Mon Sep 24, 2007 5:57 pm UTC
Location: US

Re: Proof by contradiction is never needed!

Postby rrwoods » Thu Nov 08, 2007 7:11 pm UTC

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

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

User avatar
Owehn
Posts: 479
Joined: Tue Oct 09, 2007 12:49 pm UTC
Location: Cambridge, UK

Re: Proof by contradiction is never needed!

Postby Owehn » Thu Nov 08, 2007 8:10 pm UTC

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.
[This space intentionally left blank.]


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 11 guests