The textbook's natural deduction proof for $\vdash(\neg(\phi\to\psi)\to\phi)$ seems to be wrong with regard to RAA(Reductio Ad Absurdum).

269 Views Asked by At

As you can see below, $\psi$ pops out of nowhere due to RAA(reductio ad absurdum). This is probably wrong. Is there really a proper natural deduction proof for $\vdash(\neg(\phi\to\psi)\to\phi)$?

enter image description here

Update 1 : I added another example.

enter image description here

1

There are 1 best solutions below

6
On BEST ANSWER

The proof is correct. From $\bot$ you can infer anything, which is why the $\psi$ is allowed to "pop out of nowhere" in the first use of RAA in the proof. Note that this use of RAA does not discharge any hypotheses (there is no number next to the line that infers $\psi$ from $\bot$).

In the second use of RAA in the proof, from $\bot$ we discharge hypothesis 2 ($\neg \phi$) in order to infer $\phi$. Perhaps this is a more normal-looking use of RAA that you are used to (if $\neg \phi$ yields a contradiction, then infer $\phi$).