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 infinte 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?
 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/...ontradict.html is worth a look
 ~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.

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.

Recognitions:

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".
 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.
 Recognitions: Gold Member Science Advisor Staff Emeritus "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".
 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
 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.

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.

 Quote by HallsofIvy 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 statment ~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.
 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?