1

Could Reductio ad Absurdum not be consireded a valid proof method? Are there any compelling arguments against it, or at it's favor?

I feel like I am assuming some metamathematical hypothesis about my set of axioms that may not be true, when I use it. So I always try to convert it to a Contrapositive. But I don't know of any arguments or even bibliography about this matter.

Edit: As some have pointed, this question is somewhat related to (http://mathoverflow.net/questions/12342/reductio-ad-absurdum-or-the-contrapositive). However, I want to understand what are metamathematically the justifications for the method of Reductio and if there are arguments against it.

flag
2 
 You can prove that reduction to the absurd is a valid method of proof in classical first order logic. You want to show that $T\cup\{\lnot\phi\}$ is contradictory if and only if $T\vdash\phi$. One direction is trivial. For the other assume that $T\cup\{\lnot\phi\}$ is contradictory, then by the principle of explosion we have $T\vdash\lnot\phi\to\phi$. It's easy to see that $(\lnot\phi\to\phi)\to\phi$ is a tautology hence $T\vdash\phi$. – Apostolos May 31 at 15:06
9 
 Suppose reductio ad absurdum is valid. Then... – Qiaochu Yuan May 31 at 15:36
3 
 I had nearly finished writing an answer when the question was closed, so I'll move the answer to three comments. To provide a common context for the methods of contraposition and reductio ad absurdum, I'll assume you're interested in proving an implication $A\to B$ (because only implications have contrapositives). So the contrapositive is $(\neg B)\to(\neg A)$. Reductio ad absurdum would mean (to me) deducing a contradiction (which I'll denote by the usual symbol $\bot$) from the hypothesis $A$ and the negation of the conclusion; so you'd be proving $(A\land\neg B)\to\bot$. – Andreas Blass May 31 at 15:44
3 
 The validity of both methods (in classical logic) amounts to the observation that all three of the formulas $[A\to B]$, $[(\neg B)\to(\neg A)]$, and $[(A\land\neg B)\to\bot]$ are tautologically equivalent (as can easily be checked by writing down their truth tables, or more easily by thinking about it for a moment). So, if you've proved any one of the three, the others follow. – Andreas Blass May 31 at 15:44
3 
 If you use constructive (intuitionistic) logic instead of classical, then $(\neg B)\to(\neg A)$ and $(A\land\neg B)\to\bot$ are still equivalent, but they are in general weaker than $A\to B$; indeed, they are equivalent to $A\to\neg\neg B$. So, in general, neither of the two methods is constructively justified. If, however, $B$ is itself a negation, say $\neg C$, then everything is OK again, because $\neg\neg\neg C$ and $\neg C$ are equivalent even in constructive logic. – Andreas Blass May 31 at 15:45
show 4 more comments

closed as subjective and argumentative by Marc Palm, Steven Landsburg, Andy Putman, Simon Thomas, Henry Cohn May 31 at 15:40

Browse other questions tagged or ask your own question.