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

Question

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.

Answer 1

Unless you already have that hypothesis, you need to get to that hypothesis first.

Also, (α→β)→(β→γ)→(α→γ) is ambiguous. You almost surely want to prove ((α→β)→((β→γ)→(α→γ))). Additionally, you don't actually use the deduction (meta) theorem, you use the rule of inference that it implies as valid. I'll call this rule "conditional introduction".

I don't know your format exactly or what you have exactly, but a proof might go something like this:

Hypothesis (rule of modus ponens/detachment): (α→β), α $\vdash$ β

Weakening: (α→β), α, (β→γ) $\vdash$ β

Commutation on the left side: (α→β), (β→γ), α $\vdash$ β

Identity: (α→β), (β→γ), α $\vdash$ β, (β→γ)

Detachment: (α→β), (β→γ), α $\vdash$ γ

Conditional introduction: (α→β), (β→γ) $\vdash$ (α→γ)

Answer 2

If, as Doug suggested, you are really required to prove

$A\implies B \implies (B\implies C \implies (A\implies C))$,

you could start with 3 successive premises, the first two being:

1. Suppose $A\implies B$

2. Suppose $B\implies C$

3. Suppose ???

(I don't like Greek letters!)

Answer 3

$$\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}$$