How can I prove $(P \to Q) \to (\lnot Q \to \lnot P)$?

Question

I'm struggling to grasp how to do natural deduction and am going through questions but this one has stumped me completely.

The question is to prove $(P \to Q) \to (\lnot Q \to \lnot P)$ without the use of (non-discharged) assumptions.

Answer 1

In order to prove $A\rightarrow B$ we have the rule $\rightarrow-$introduction which works that you assume $A$ and then prove $B$. In this case you want to prove $$(P\rightarrow Q)\rightarrow (\neg Q\rightarrow \neg P).$$ Thus assume $P\rightarrow Q$ and try to prove $\neg Q\rightarrow \neg P$. Again we can apply the reasoning above. Since we want to prove $\neg Q\rightarrow \neg P$ we assume $\neg Q$ and try to prove $\neg P$.

So at this point we have done two assumptions: $(P\rightarrow Q)$ and $\neg Q$. If we from this can prove $\neg P$ we can use two cases of $\rightarrow-$introduction and we will be done.

To prove $\neg P$ we have the rule $\neg-$introduction. Which works as follows: Assume $P$, derive a contradiction ($\bot$) and you may then conclude $\neg P$. Can you take it from here?