Is Proof by Contradiction the Most Popular Technique in Mathematics?

[pivoxa15]

How widely used is this method? Is it the most popular proof technique? All it takes it to find a condradiction or counter example in order to prove something which is often much simpler than listing all the cases (not to mention if there are infinite of them to start with) or directly proving something.
i.e To prove A=>B
Proof by contradiction works by showing ~B=>~A
So if A is true than B must be true which is what we set out to prove.

When doing undergrad abstract algebra, I am finding that I am using this method a lot. Is this good? Wasn't this Godfrey Hardy's favouriate proof technique?

 

[jing]

counter examples and proof by contradiction are not the same thing.

You can make an conjecture and use a counter example to show it is false.

conjecture

Two odd whole numbers add to give an odd whole number

counter example 5 + 3 = 8 which is even.

This does not prove that Two odd whole numbers add to give an even whole number for all whole numbers

showing ~B=>~A to prove A=>B is not a proof by contradiction and is often a more complicated proof.

A n, m are two odd whole numbers or two even whole numbers
B n+m is even

~A n, m are two whole numbers one or which is even
~B n+m is odd

n + m is odd
therefore n+m=2p+1 for some whole number p

therefore n=2p-m+1

m is either odd or even
m odd m=2q+1 for some whole number q
since n>0 and m>0 then n+m>m therefore 2p+1>2q+1 therefore p>q therefore p-q>0
n=2p-2q-1+1 = 2(p-q) therefore n is even

m even m=2q for some whole number q
n=2p-2q+1 = 2(p-q)+1 n is odd

so if m is odd n is even and if m is even n is odd and by symmetry
if n is odd m is even and if n is even m is odd.

hence ~B=>~A and so A=>B not a contradiction in sight

Proof by contradiction means

to prove A=>B start with the opposite conjecture A=>~B and arrive at a contradition

A n, m are two odd whole numbers
B n+m is even

~B n+m is odd

Assume A=> ~B
m is odd therefore m=2p+1
n is odd therefore n=2q+1
n+m is odd therefore n+m = 2r+1
then 2p+1 + 2q +1 = 2r+1
if and only if 2(p+q)+1 = 2r
if and only if 2(p+q-r)=1
if and only if p+q+r=1/2 contradicting p,q,r are whole numbers
and so our assumption is wrong and A=>B

Of course in this case the best way is to prove A=>B directly

Where you might be getting confused about counter example and proof by contradiction is the \sqrt{2} is irrational proof.

A n is a positive whole number
B \sqrt{n} is rational

you disprove A=>B using a counter example by showing \sqrt{2} is irrational

you show \sqrt{2} is irrational by using proof by contradition

start with the opposite assumption that \sqrt{2} is rational and arrive at a contradiction.

http://zimmer.csufresno.edu/~larryc/proofs/proofs.contradict.html is worth a look

 

[ZioX]

~B=>~A is called the contrapostive, which is equivalent to A=>B.

Here's the first proof that popped into my head for proof by contradiction:

If every sequence x_n that converges to A has the property that f(x_n) converges to L then the limit x->A L.

You can't prove this by direct proof because there are soooooooooo many sequences converging to a. So a proof by contradiction is used.

 

[fopc]

In ~B -> ~A, you've given the form for a contrapositive proof.

For an assertion of the form, A -> B, a proof by contradition would look like:

(A and ~B) -> some contradiction, e.g., ~A or B or perhaps you can pull an R out of your hat and arrive at (R and ~R).

Sometimes a proof is started as a proof by contradiction,
and in the end you arrive at say ~A (an apparent "contradiction").
But, if in the course of the proof A is never explicitly used, then the proof is actually a proof by contraposition.

You might keep in mind that virtually all assertions come with some form of quantification. Often times left implicit, but there never the less. To say that this can complicate things is an understatement.

PS.
"to prove A=>B start with the opposite conjecture A=>~B and arrive at a contradition."

You might read your link again. Just the first sentence will suffice.

 

[uart]

Proof by contradiction means to prove A=>B start with the opposite conjecture A=>~B and arrive at a contradition

I think that should read "start with the conjecture that A does not imply B" rather than "start with the conjecture that A implies Not_B".

More generally proof by contradiction doesn't need to be set out in the form of "A implies B" etc, but rather it just requires that we start with a conjecture "C" that we wish to prove and then show that if C is false then that leads to a contradiction.

If the conjecture "C" that we begin with is that "A implies B" then assuming C to be false is equivalent to assumming that "A does not imply B" rather than assumming that "A implies Not_B".

 

[jing]

fopc - not sure what you mean by the PS.

The first sentence of what?

The link is not mine in the sense that I wrote the page to which the link goes I just found it by searching for proof by contradiction.

 

[HallsofIvy]

"Proof of the contrapositive" is a special case of "proof by contradiction"- you assume the conclusion is true and then prove that the hypothesis is false- that's the contradiction.

But proof by contradiction is more general- you assume the conclusion is false and use that along with the hypotheses to prove "statement A", which may have no obvious relation to the hypotheses- then turn around and prove "statement B" which also may have not obvious relation to the hypotheses, but contradicts "statement A".

 

[jing]

uart - take

A n=2
B \sqrt{n} is irrational

conjecture C A=>B assuming C to be false is equivalent to assuming that A does not imply B, ie n=2 does not imply \sqrt{n} is irrational does not get anywhere as it gives no indication as to what n=2 could imply. n=2 does not imply \sqrt{n} is irrational does not imply that n=2 implies that \sqrt{n} is rational


But I am also incorrect in saying A=>B is false is equivalent to A=>~B

revising my boolean logic

A=>B is equivalent to ~A V B (V OR) ~ NOT

so ~(A=>B) is equivalent to ~(~A V B) is equivalent to A & ~B (& AND)

so assuming C (above) to be false gives

n=2 AND \sqrt{n} is rational (given that all real numbers are either irrational or rational) and hence the proof by contradiction can proceed.

Sorry for the basic error but it is a while since I did predicate calculus

 

[fopc]

"The first sentence of what?"

I don't think there should be any confusion about what sentence I was referring to. But OK, I was referring to the first sentence on the page of the link that you provided.


"The link is not mine in the sense that I wrote the page to which the link goes I just found it by searching for proof by contradiction."

I didn't say you wrote the page. My reference to "your link" only meant the link that you provided to this thread. In that sense you are responsible for the link; but it doesn't mean that you wrote it.

By the way, your words, "is worth a look", strongly suggests (to me at least) that you actually bothered to review the page. Otherwise, why provide the link and say its "worth a look", if you haven't "looked at it"
yourself? My suggestion that you read (again?) the first sentence was to remind you that your statement, "to prove A=>B start with the opposite conjecture A=>~B and arrive at a contradition", has some serious problems. I meant no offense by it.

Anyway, have a nice day.


On another issue:

1.) A->B <->
2.) ~B -> ~A <->
3.) (A and ~B) -> any contradiction.

If you choose to prove 1 directly, obviously there is no contradiction.

If you choose to prove 2 directly, there is no contradiction (this is considered a direct contrapositive proof).
You're simply trying to establish that if B is false, then A is necessarily false.

In proving 3 directly, obviously there will be a contradition (this is considered a proof by contradiction).

If you choose to prove 2 by contradiction, then you are proving (~B and A) -> any contradiction. But as you can see, this is just 3, and clearly 3 can be derived from either 1 or 2. So the status of 3 does not have to have anything whatsoever to do with the contapositive.

Contrapositive proof does not involve producing a contradiction.

Of course, if you say proving 2 by contradiction amounts to a proof by contradiction of the contrapositive, then I think terminology becomes clouded. But I would argue that proving 2 by contradiction is just proving
1 by contradiciton, and now the word contrapositive no longer enters into the discussion.

 

[jing]

fopc - No offense taken at all. I genuinely did not follow what you were saying.

I took "The first sentence will suffice" to mean "Nothing after the first sentence is required" rather than "It is sufficient to read just the first sentence of the link to see that the statement ...had serious errors

I did realize my mistake after further thought, and revision reading as you will see by my later post

I was trying to clear up some confusion in the OP about counter examples, proof by contradiction and the way it works and unfortunately not quite succeeded. However if pivoxa15 now reads the whole thread (s)he should be able to sort out the differences between counter examples, direct proof, contrapositive proofs and proof by contradiction.

Unfortunately in sorting this out nobody has answered the original questions directly.

 

[pivoxa15]

I think I see what the general version of proof by contradiction is.

To prove A=>B do
~B=>C where C is wrong when assuming A. The only way for ~B=>C to be correct is for ~B to be false so B is correct (when we assumed A in the statement ~B=>C). Hence when assuming A to be correct, we proved that B must be correct. Proof complete.
C could be ~A hence a special case as you people pointed out.

 

[AsianSensationK]

That looks kind of tough to follow. It works (ie I've seen it in my abstract algebra textbook), but you don't actually have to start off with a statement like A=>B. You can use it to prove any general kind of statement A simply by finding a contradiction when assuming ~A.

At its absolute most basic, it will look just like HallsofIvy and others have described.

But proof by contradiction is more general- you assume the conclusion is false and use that along with the hypotheses to prove "statement A", which may have no obvious relation to the hypotheses- then turn around and prove "statement B" which also may have not obvious relation to the hypotheses, but contradicts "statement A".

Here's a step by step summary. I want to prove some statement A.

I assume ~A.
I find some statement B which is implied by ~A and any other hypotheses.
I also find some statement ~B which is implied by ~A and any other hypotheses.
I now have a contradiction (B and ~B).

At this point we discharge the assumption of ~A. Because I have a contradiction, I can apply negation introduction to get ~~A. And by negation elimination I have A. Proof complete.

As far as taking undergrad math courses, I've found that I use mathematical induction and direct proof the most. Proof by contradiction popped up every once in a while when I wanted to prove something existed but there was no obvious way to do it with the direct proof method.

Proof by contradiction is a staple in most philosophy courses though. They like to call it reductio ad absurdum.

 

[pivoxa15]

When doing algebra with rings, I found that if I don't see a direct proof immediately, I try proof by contradiction and it tends to fall out. Is this method the most popular in mathematics? And especially in algebra?