Natural deduction proof of $ \neg q \Rightarrow p$ using $ (p \Rightarrow q) \Rightarrow p$

66 Views Asked by At

I am having some trouble completing this proof, I have attached an image of my best attempt so far but I am unsure if it is correct.

I would like some help on where I have gone wrong and some ideas on what I can do to get a correct derivation. We have the implication rules for $\vee, \wedge, \Rightarrow, \neg$.

Thought process:

Breaking down the question from the bottom, we can assume $\neg q $ and must now prove $p$. I assumed $\neg (p \Rightarrow q) $ and derived $p \wedge \neg q$ and attempted proof by contradiction. I can produce a proof of this derivation separately (it should just use De Morgan's law and rewriting implication).

Notes:

On line 4, I state that I derived this from the subproof. On line 8, this is a PC using (5-7) On line 11 and 15, they are just restatements of previously found values.

Any help would be appreciated.

For convenience, here is the LaTeX code using fitch.sty by Peter Selinger:

$$ \begin{nd}

\hypo {1} {(p \Rightarrow q) \Rightarrow p} \open \hypo {2} {\neg q} \open \hypo {3} {\neg (p \Rightarrow q)}
\open \hypo {4} {p \wedge \neg q} \have {5} {p} \oe {4} \open \have {6} {\neg p } \have {7} {F} \ne {5-6} \close \have {8} {q} \have {9} {\neg q} \oe {4} \have {10} {F} \ne {8-9} \close \have {11} {F} \close \have {12} {p \Rightarrow q} \ii {(3-11)} \have {13} {p} \ie {(1, 12)} \close \have {14} {\neg q \Rightarrow p} \ii {1 - 13} \close \have {15} {\neg q \Rightarrow p} \end{nd} $$