= Solution
Assume the two implications in turn, then derive a contradiction from $\neg P$. The <natural deduction> proof is
$$
\begin{array}{rll}
1&\quad\neg P\to Q&\text{assumption}\\
2&\qquad\neg P\to\neg Q&\text{assumption}\\
3&\qquad\quad\neg P&\text{assumption}\\
4&\qquad\quad Q&\to E\ 1,3\\
5&\qquad\quad\neg Q&\to E\ 2,3\\
6&\qquad\quad\bot&\neg E\ 4,5\\
7&\qquad P&\mathrm{RAA}\ 3\text{--}6\\
8&\quad(\neg P\to\neg Q)\to P&\to I\ 2\text{--}7\\
9&(\neg P\to Q)\to((\neg P\to\neg Q)\to P)&\to I\ 1\text{--}8
\end{array}
$$
Here RAA is the derived <proof by contradiction> rule. The last two <assumption discharge> steps establish the requested right-associated implication as a theorem.
Back to article page
