Prove $((\phi_1 \land \phi_2 \land \cdots \land \phi_n) \rightarrow \psi) \rightarrow \cdots$

Question

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.

Answer 1

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)$.

1. $p\rightarrow\left(q\rightarrow r\right)$ (premise)
2. $r\rightarrow s$ (premise)
3. $p$ (premise)
4. $q\rightarrow r$ (Modus ponens on lines 1, 3)
5. $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:

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)
2. $\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)
3. $\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:

4. $\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:

5. $\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)$$