prove conjunction of consecutive implications

Question

$n\ge 2,p_1,p_2,p_3,...,p_n,p_{n+1}$ are statements.

Prove $(p_1\rightarrow p_2)\wedge (p_2\rightarrow p_3)\wedge ...\wedge (p_n\rightarrow p_{n+1})$ $\Rightarrow (p_1\wedge p_2\wedge p_3\wedge...\wedge p_n)\rightarrow p_{n+1}$

Base case:$(p_1\rightarrow p_2)\wedge (p_2\rightarrow p_3)\Rightarrow p_1\wedge p_2\rightarrow p_3$ (by truth table - omitted)

Assume $(p_1\rightarrow p_2)\wedge (p_2\rightarrow p_3)\wedge ...\wedge (p_{n-1}\rightarrow p_n)\wedge (p_n\rightarrow p_{n+1})$ $\Rightarrow (p_1\wedge p_2\wedge p_3\wedge...\wedge p_{n-1}\wedge p_n)\rightarrow p_{n+1}$

$[(p_1\rightarrow p_2)\wedge (p_2\rightarrow p_3)\wedge ...\wedge (p_n\rightarrow p_{n+1})]\wedge (p_{n+1}\rightarrow p_{n+2})$ $\Rightarrow [(p_1\wedge p_2\wedge p_3\wedge...\wedge p_{n-1}\wedge p_n)\rightarrow p_{n+1}]\wedge (p_{n+1}\rightarrow p_{n+2})$ $\Rightarrow (p_1\wedge p_2\wedge p_3\wedge ...\wedge p_n\wedge p_{n+1})\rightarrow p_{n+2}$

Answer 1

I think that we need an induction on the number $k$ of occurrences of $\land$ in the conjunction.

(i) Basis :

For $k=1$ you have already established it :

$(p_1→p_2)∧(p_2→p_3) \vDash (p_1∧p_2)→p_3$

(ii) Induction step :

Assume it for $n$ :

$((p_1→p_2)∧(p_2→p_3)∧ \ldots ∧(p_{n-1}→p_n)) \vDash (p_1∧p_2∧ \ldots ∧p_{n-1})→p_n$

and prove it for $n+1$.

Abbreviate the last formula as $A_n \vDash B_n$.

We have clearly :

if $A_n \vDash B_n$, then $(A_n \land S) \vDash (B_n \land S)$.

Now consider :

$A_{n+1} := A_n \land (p_n→p_{n+1})$;

we have that $A_{n+1} \vDash B_n \land (p_n→p_{n+1})$, i.e :

$A_{n+1} \vDash [(p_1∧p_2∧ \ldots ∧p_{n-1})→p_n] \land (p_n→p_{n+1})$ --- (*).

Now we can build this easy derivation (under the assumption $A_{n+1}$) :

(a) $(p_1∧p_2∧ \ldots ∧p_{n-1}) \land p_n$ --- assumed

(b) $p_n$ --- from (a) by $\land$-elimination

(c) $[(p_1∧p_2∧ \ldots ∧p_{n-1})→p_n] \land (p_n→p_{n+1})$ --- from (*)

(d) $(p_n→p_{n+1})$ --- from (c) by $\land$-elimination

(e) $p_{n+1}$ --- from (b) and (d) by modus ponens

(f) $[(p_1∧p_2∧ \ldots ∧p_{n-1}) \land p_n] \rightarrow p_{n+1}$ --- from (a) and (e) by $\rightarrow$-introduction.

Thus :

$A_{n+1} \vDash [(p_1∧p_2∧ \ldots ∧p_{n-1}) \land p_n] \rightarrow p_{n+1}$

i.e.

if $A_n \vDash (p_1∧p_2∧ \ldots ∧p_{n-1})→p_n$, then $A_{n+1} \vDash (p_1∧p_2∧ \ldots \land p_n) \rightarrow p_{n+1}$.