1
$\begingroup$

If we have a premise, $x \in A$, is the following a correct use of RAA?

Suppose $x \in A$:

Assume P:

...

Derive $x \notin A$

Therefore not P.

Can we correctly reject P if we find a contraction against the premise when assuming P?

$\endgroup$
  • $\begingroup$ If $x\in A$ is certain , then we can show that $P$ cannot hold by showing that the assumption that $P$ holds leads to a contradiction, which you did. By the principle of the excluding middle, $P$ must be false. $\endgroup$ – Peter Sep 16 '18 at 14:12
  • $\begingroup$ The abbreviation RAA is not familiar to me. Perhaps spelling it out (reductio ad absurdum?), or linking to or citing its source would be helpful. $\endgroup$ – hardmath Sep 16 '18 at 14:51
1
$\begingroup$

This is a proof that $x\in A \implies \neg P$. It can be simplified, since everything between "Assume $P$" and "Derive $x\not\in A$" is just a proof that $P\implies x\not\in A$, from which by contrapositive we get $x\in A \implies \neg P$, which was to be demonstrated.

You can't in general conclude from this that $P$ is always false, of course.

$\endgroup$
1
$\begingroup$

Yes. Deriving a contradiction from the assumption of $P$ is a proof for $\neg P$.

Although apparently similar, this is not actually Reduction ad Absurdum.

This is the Rule of Negation Introduction.   Unlike RAA this is an intuitionistically valid rule of inference. $$\dfrac{\Sigma,P\vdash \bot }{\Sigma\vdash \neg P}{\sf\small\neg I}$$


RAA consists of Negation Introduction and Double Negation Elimination. The later rule is not considered valid under an intuitionistic proof system.$$\dfrac{\dfrac{\Sigma, \neg P\vdash \bot}{\Sigma\vdash\neg\neg P}{\small\neg\sf I}}{\Sigma\vdash P}{\small\neg\neg\sf E}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.