Prove $((\phi_1 \land \phi_2 \land \cdots \land \phi_n) \rightarrow \psi) \rightarrow \cdots$ I am trying to do the following exercise from the book Logic Programming for computer scientists by Michael Huth and Mark Ryan.
$$((\phi_1 \land \phi_2 \land \cdots \land \phi_n) \rightarrow \psi) \rightarrow (\phi_1 \rightarrow (\phi_2 \rightarrow (\cdots (\phi_n \rightarrow \psi) \cdots )))$$
I am trying it by induction on $n$.
Basis: When $n = 1$ we have $(\phi_1 \rightarrow \psi) \rightarrow (\phi_1 \rightarrow \psi)$, which is true.
Inductive hypothesis: Suppose $((\phi_1 \land \phi_2 \land \cdots \land \phi_n) \rightarrow \psi) \rightarrow (\phi_1 \rightarrow (\phi_2 \rightarrow (\cdots (\phi_n \rightarrow \psi) \cdots )))$ is true for some $n$.
Inductive step:
Suppose $((\phi_1 \land \phi_2 \land \cdots \land \phi_n \land \phi_{n + 1}) \rightarrow \gamma)$ is true.
Now I don't see how I can use the induction hypothesis to prove this implies $(\phi_1 \rightarrow (\phi_2 \rightarrow (\cdots (\phi_n \rightarrow ( \phi_{n + 1} \rightarrow \gamma)) \cdots )))$.
Does $((\phi_1 \land \phi_2 \land \cdots \land \phi_n \land \phi_{n + 1}) \rightarrow \gamma)$ imply that $((\psi \land \phi_{n + 1}) \rightarrow \gamma)$ because $((\phi_1 \land \phi_2 \land \cdots \land \phi_n) \rightarrow \psi)$ is true by the inductive hypothesis? (I know this is wrong, the inductive hypothesis does not say this must be true)
Then we have a conjunction of two formulas, for which we already know $((\psi \land \phi_{n + 1}) \rightarrow \gamma) \rightarrow (\psi \rightarrow (\phi_{n + 1} \rightarrow \gamma))$ by the induction hypothesis. It feels like I am really misunderstanding what is going on.
 A: The answer depends on your initial principles. Perhaps, you can use the following theorems:

*

*Theorem 1: $\vdash p\rightarrow\left(q\rightarrow p\wedge q\right)$.

*Theorem 2: $\vdash p\rightarrow q,q\rightarrow r\vdash p\rightarrow r$.

*Deduction theorem: If $p_{1},p_{2},...,p_{n}\vdash q$ then $p_{1},p_{2},...,p_{n-1}\vdash p_{n}\rightarrow q$.

First, we prove theorem 3: $p\rightarrow\left(q\rightarrow r\right),r\rightarrow s\vdash p\rightarrow\left(q\rightarrow s\right)$.

*

*$p\rightarrow\left(q\rightarrow r\right)$ (premise)

*$r\rightarrow s$ (premise)

*$p$ (premise)

*$q\rightarrow r$ (Modus ponens on lines 1, 3)

*$q\rightarrow s$ (Th. 2 on lines 4, 2)

Thus, we have shown that $p\rightarrow\left(q\rightarrow r\right),r\rightarrow s,p\vdash q\rightarrow s$.
Then, by the deduction theorem, we get:
$$p\rightarrow\left(q\rightarrow r\right),r\rightarrow s\vdash p\rightarrow\left(q\rightarrow s\right)$$
If the parentheses are inserted from left to right (I thing this is
the usual rule), then $\left(\phi_{1}\wedge\phi_{2}\wedge\phi_{3}\wedge...\wedge\phi_{n}\right)$
is $\left(...\left(\left(\phi_{1}\wedge\phi_{2}\right)\wedge\phi_{3}\right)\wedge...\wedge\phi_{n-1}\right)\wedge\phi_{n}$.
This is of the form $p\wedge q$, thus we can apply theorem 1:

*

*$\left(...\left(\left(\phi_{1}\wedge\phi_{2}\right)\wedge\phi_{3}\right)\wedge...\wedge\phi_{n-1}\right)\rightarrow\left[\phi_{n}\rightarrow\left(...\left(\left(\phi_{1}\wedge\phi_{2}\right)\wedge\phi_{3}\right)\wedge...\wedge\phi_{n-1}\right)\wedge\phi_{n}\right]$
(Th. 1)

*$\left(...\left(\left(\phi_{1}\wedge\phi_{2}\right)\wedge\phi_{3}\right)\wedge...\wedge\phi_{n-1}\right)\wedge\phi_{n}\rightarrow\psi$
(postulate)

*$\left(...\left(\left(\phi_{1}\wedge\phi_{2}\right)\wedge\phi_{3}\right)\wedge...\wedge\phi_{n-1}\right)\rightarrow\left(\phi_{n}\rightarrow\psi\right)$
(Th. 3 on lines 1, 2).

In the next step, we use again theorem 1:


*$\left(...\left(\left(\phi_{1}\wedge\phi_{2}\right)\wedge\phi_{3}\right)\wedge...\wedge\phi_{n-2}\right)\rightarrow\left[\phi_{n-1}\rightarrow\left(...\left(\left(\phi_{1}\wedge\phi_{2}\right)\wedge\phi_{3}\right)\wedge...\wedge\phi_{n-2}\right)\wedge\phi_{n-1}\right]$
And then, theorem 3 again, on lines 4, 3:


*$\left(...\left(\left(\phi_{1}\wedge\phi_{2}\right)\wedge\phi_{3}\right)\wedge...\wedge\phi_{n-2}\right)\rightarrow\left(\phi_{n-1}\rightarrow\left(\phi_{n}\rightarrow\psi\right)\right)$
By successive repetitions, we finally get $\left(\phi_{1}\rightarrow\left(\phi_{2}\rightarrow...\rightarrow\left(\phi_{n}\rightarrow\psi\right)...\right)\right)$.
Thus, we have shown:
$$\left(...\left(\left(\phi_{1}\wedge\phi_{2}\right)\wedge\phi_{3}\right)\wedge...\wedge\phi_{n-1}\right)\wedge\phi_{n}\rightarrow\psi\vdash\left(\phi_{1}\rightarrow\left(\phi_{2}\rightarrow...\rightarrow\left(\phi_{n}\rightarrow\psi\right)...\right)\right)$$
Now, by the deduction theorem, we get:
$$\vdash\left[\left(...\left(\left(\phi_{1}\wedge\phi_{2}\right)\wedge\phi_{3}\right)\wedge...\wedge\phi_{n-1}\right)\wedge\phi_{n}\rightarrow\psi\right]\rightarrow\left(\phi_{1}\rightarrow\left(\phi_{2}\rightarrow...\rightarrow\left(\phi_{n}\rightarrow\psi\right)...\right)\right)$$
