[Math] Natural deduction proof of $(\alpha\to\beta)\to(\beta\to\gamma)\to(\alpha\to\gamma)$

logicnatural-deductionpropositional-calculus

My teacher has assigned us this exercise as part of our homework:

Give a natural deduction proof of $(\alpha\to\beta)\to(\beta\to\gamma)\to(\alpha\to\gamma)$

Here is an example of natural deduction that he gave us:

$\vdash \alpha\to\beta\to\alpha$.

This is a tautology, but it's easier to prove than to verify:
$\alpha,\beta\vdash\alpha$, hypothesis
$\alpha\vdash\beta\to\alpha$, deduction theorem
$\vdash\alpha\to\beta\to\alpha$, deduction theorem

Here is my attempt:

Hypothesis: $(\alpha\to\beta),(\beta\to\gamma) \vdash (\alpha\to\gamma)$
Deduction thm: $(\alpha\to\beta) \vdash(\beta\to\gamma)\to(\alpha\to\gamma)$
Deduction thm: $\vdash(\alpha\to\beta)\to(\beta\to\gamma)\to(\alpha\to\gamma)$

Is this enough? I feel like I need to take apart the functions inside the parentheses and check those as well, but I don't know how.

Best Answer

$$\begin{align} (1) & \alpha \rightarrow \beta && [\text{HYP}] \\ (2) & \beta \rightarrow \gamma && [\text{HYP}] \\ (3) & \alpha && [\text{HYP}] \\ (4) & \beta && [\text{MP}(1,3)] \\ (5) & \gamma && [\text{MP}(2,4)] \\ (6) & \alpha \rightarrow \gamma && [\rightarrow\text{-intro}(3,5)] \\ (7) & (\beta \rightarrow \gamma) \rightarrow (\alpha \rightarrow \gamma) && [\rightarrow\text{-intro}(2,6)] \\ (8) & (\alpha \rightarrow \beta) \rightarrow ((\beta \rightarrow \gamma) \rightarrow (\alpha \rightarrow \gamma)) && [\rightarrow\text{-intro}(1,7)] \\ \end{align}$$

Related Question