From time to time, when I write proofs, I'll begin with a claim and then prove the contradiction. However, when I look over the proof afterwards, it appears that my proof was essentially a proof of the contrapositive, and the initial claim was not actually important in the proof. 


Can all claims proven by reductio ad absurdum be reworded into proofs of the contrapositive? If not, can you give some examples of proofs that don't reduce? If not all reductio proofs can be reduced, is there any logical reason why not? Is reductio stronger or weaker than the contrapositive?


Edit: Just another minor question (of course this is optional and will not affect me choosing an answer): If they are equivalent, then why would you bother using reductio?


And another bonus question (Like the above, does not influence how I choose the answer to accept.)
Are the two techniques intuitionistically equivalent? 



Reductio ad absurdum or the contrapositive?
Although the other answers correctly explain the basic logical equivalence of the two proof methods, I believe an important point has been missed:


* *With good reason*, we mathematicians prefer a direct proof of an implication over a proof by contradiction, when such a proof is available. (all else being equal)


What is the reason? The reason is the *fecundity* of the proof, meaning our ability to use the proof to make further mathematical conclusions. When we prove an implication (p implies q) directly, we assume p, and then make some intermediary conclusions r1, r2, before finally deducing q. Thus, our proof not only establishes that p implies q, but also, that p implies r1 and r2 and so on. Our proof has provided us with additional knowledge about the context of p, about what else must hold in any mathematical world where p holds. So we come to a fuller understanding of what is going on in the p worlds.


Similarly, when we prove the contrapositive (¬q implies ¬p) directly, we assume ¬q, make intermediary conclusions r1, r2, and then finally conclude ¬p. Thus, we have also established not only that ¬q implies ¬p, but also, that it implies r1 and r2 and so on. Thus, the proof tells us about what else must be true in worlds where q fails. Equivalently, since these additional implications can be stated as (¬r1 implies q), we learn about many different hypotheses that all imply q.


These kind of conclusions can increase the value of the proof, since we learn not only that (p implies q), but also we learn an entire context about what it is like in a mathematial situation where p holds (or where q fails, or about diverse situations leading to q).


With reductio, in contrast, a proof of (p implies q) by contradiction seems to carry little of this extra value. We assume p and ¬q, and argue r1, r2, and so on, before arriving at a contradiction. The statements r1 and r2 are all deduced under the contradictory hypothesis that p and ¬q, which ultimately does not hold in any mathematical situation. The proof has provided extra knowledge about a nonexistent, contradictory land. (Useless!) So these intermediary statements do not seem to provide us with any greater knowledge about the p worlds or the q worlds, beyond the brute statement that (p implies q) alone.


I believe that this is the reason that sometimes, when a mathematician completes a proof by contradiction, things can still seem unsettled beyond the brute implication, with less context and knowledge about what is going on than would be the case with a direct proof.




---


Edit: For an example of a proof where we are led to false expectations in a proof by contradiction, consider Euclid's proof that there are infinitely many primes. In a common proof by contradiction, one assumes that p1, ..., pn are *all* the primes. It follows that since none of them divide the product-plus-one p1...pn+1, that this product-plus-one is also prime. This contradicts that the list was exhaustive. Now, many beginners falsely expect after this argument that whenever p1, ..., pn are prime, then the product-plus-one is also prime. But of course, this isn't true, and this would be a misplaced instance of attempting to extract greater information from the proof, misplaced because this is a proof by contradiction, and that conclusion relied on the assumption that p1, ..., pn were *all* the primes. If one organizes the proof, however, as a direct argument showing that whenever p1, ..., pn are prime, then there is yet another prime not on the list, then one is led to the true conclusion, that p1...pn+1 has merely a prime divisor not on the original list.


