Give a Hilbert Style Proof using Modus Ponens

Question

$$(φ \Rightarrow ψ), (ψ \Rightarrow θ) \vdash (φ \Rightarrow θ)$$

$ 1.\quad φ \Rightarrow ψ \quad (Assumption\ 1)$

$ 2.\quad ψ \Rightarrow θ \quad (Assumption\ 2)$

$ 3.\quad φ \Rightarrow ψ \equiv \lnot φ \lor ψ\quad (Thm\ 2.4.11)$

$ 4.\quad ψ \Rightarrow θ \equiv \lnotψ \lor θ\quad (Thm\ 2.4.11)$

$ 5.\quad \lnot φ \lor ψ\quad \quad (1,3\ +\ $Modus Ponens$) $

$ 6.\quad \lnotψ \lor θ\quad (2,4\ +\ $Modus Ponens$)$

That's all I have, not sure if I'm even doing it right.

It's also asked to give a proof of this formal theorem using the Deduction Theorem.

I've been sitting on this for a while and can't figure out what they asking. Help is much appreciated!

Here's a link to the Theorems I'm using: https://www.eecs.yorku.ca/course_archive/2012-13/F/1090/pdf/facts.pdf

Answer 1

Actually, what you're trying to prove is trivially given as theorem 2.5.9 from the notes that you provide. But suppose it is not given.

The MP rule must be used over two previous conclusions of the form $\phi$ and $\phi\Rightarrow\psi$, where $(\Rightarrow)$ is implication.

You have used the MP rule on two formulas of the form $\phi$ and $\phi\equiv\psi$, which is invalid (at least in this context). With a correct use of the MP rule you don't need any extra theorem. What you need, besides MP, is a rule of the Hilbert system about implication.

Answer 2

(I have replaced "$\Rightarrow$" all throughout by "$\to$")

Consider the set $\{\varphi\to\psi,\psi\to\theta,\varphi\}$. Then note that, \begin{align*} \{\varphi\to\psi,\psi\to\theta,\varphi\}&\vdash~1.~\varphi&\text{(Reflexitivity)}\\&\vdash~2.~\varphi\to\psi&\text{(Reflexitivity)}\\&\vdash~3.~\psi&\text{(MP, 1.,2.)}\\&\vdash~4.~\psi\to\theta&\text{(Reflexitivity)}\\&\vdash~5.~\theta&\text{(MP, 3.,4.)}\end{align*}Hence $\{\varphi\to\psi,\psi\to\theta\}\vdash\varphi\to\theta$, by Deduction Theorem. Here by Reflexitivity I mean the following property of Boolean Logic,

For all set of Boolean Logic wffs $\Gamma$ and for all wff $\alpha$, if $\alpha\in \Gamma$ then $\Gamma\vdash\alpha$.

This immediately follows by the definition of Deduction.