Derivations in Hilbert's system: pencil-and-paper exercises (2 exercises)

Propositional Logic: Hilbert's deductive system

Derivations in Hilbert's system: pencil-and-paper exercises (2 exercises)

First, attempt each exercise on your own, and then compare your answer with the worked-out solution.

Show that $p\rightarrow q, q\rightarrow r \vdash p\rightarrow r$ .

Worked-out solution

$\begin{array}{l|ll} 1 & p\rightarrow q & (\mathrm{P})\\ 2 & q\rightarrow r & (\mathrm{P})\\ 3& (q\rightarrow r) \rightarrow \bigl(p\rightarrow(q\rightarrow r)\bigr) & \mathrm{Ax\;a}\text{ with }\varphi=(q\rightarrow r), \psi=p\\ 4 & p\rightarrow (q\rightarrow r) & \mathrm{MP}, 2, 3\\ 5 & \bigl(p\rightarrow (q\rightarrow r)\bigr) \rightarrow \bigl((p\rightarrow q)\rightarrow (p\rightarrow r)\bigr)& \mathrm{Ax\;a}\text{ with }\varphi=p, \psi=q, \chi=r\\ 6 & (p\rightarrow q)\rightarrow (p\rightarrow r) & \mathrm{MP}, 4, 5\\ 7 & p\rightarrow r & \mathrm{MP}, 1, 6\end{array}$

Note that this statement follows via the Deduction theorem from the derivation of $p\rightarrow q, q\rightarrow r, p\vdash r$ chosen as an example earlier.

Show that $p\rightarrow ( q\rightarrow r) \vdash q\rightarrow (p\rightarrow r)$ .

Worked-out solution

It follows from the deduction theorem that it suffices to show that $p\rightarrow ( q\rightarrow r), q \vdash r$ . The derivation of this goes as follows:

$\begin{array}{l|ll} 1 & q & (\mathrm{P})\\ 2 & p\rightarrow (q\rightarrow r) & (\mathrm{P})\\ 3 & q\rightarrow (p\rightarrow q) & \mathrm{Ax\;a}\text{ with }\varphi=q, \psi=p\\ 4 & p\rightarrow q & \mathrm{MP}, 1, 3\\ 5 & \bigl(p\rightarrow (q\rightarrow r)\bigr) \rightarrow \bigl((p\rightarrow q)\rightarrow (p\rightarrow r)\bigr)& \mathrm{Ax\;a}\text{ with }\varphi=p, \psi=q, \chi=r\\ 6 & (p\rightarrow q)\rightarrow (p\rightarrow r) & \mathrm{MP}, 2, 4\\ 7 & p\rightarrow r & \mathrm{MP}, 4, 6\end{array}$