MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

closed as not constructive by Marc Palm, Steven Landsburg, Andy Putman, Simon Thomas, Henry Cohn May 31 '12 at 15:40

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

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 '12 at 15:06
Suppose reductio ad absurdum is valid. Then... – Qiaochu Yuan May 31 '12 at 15:36
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 '12 at 15:44
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 '12 at 15:44
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 '12 at 15:45