# Prove: $(A_1 \wedge A_2 \wedge \dots \wedge A_n) \to B\iff A_1 \to (A_2 \to (\dots \to (A_n \to B)\dots))$

I want to prove the following, using induction for every $$n \geq 0$$: $$(A_1 \wedge A_2 \wedge \dots \wedge A_n) \to B\iff A_1 \to (A_2 \to (\dots \to (A_n \to B)\dots)).$$ It is an exercise regarding propositional logic. $$\iff$$ stands for "(tauto)logically equivalent".

My base cases for induction are (maybe I do not need all of them):

$$n=0: B \iff B$$ (always holds)

$$n=1: A_1 \to B \iff A_1 \to B$$ (always holds)

$$n=2: (A_1 \wedge A_2) \to B \iff A_1 \to (A_2 \to B)$$ (proven here, using a boolean table)

I am getting stuck at the induction step. Assuming that it holds for n: $$((A_1 \wedge A_2 \wedge \dots \wedge A_n) \to B) \to(A_1 \to (A_2 \to (\dots \to (A_n \to B)\dots))) \text{ is always true}\\ ((A_1 \wedge A_2 \wedge \dots \wedge A_n) \to B) \leftarrow (A_1 \to (A_2 \to (\dots \to (A_n \to B)\dots))) \text{ is always true}$$

I do not know why it should hold for n+1: $$(A_1 \wedge A_2 \wedge \dots \wedge A_n \wedge A_{n+1}) \to B \iff A_1 \to (A_2 \to (\dots \to (A_n \to (A_{n+1} \to B))\dots)).$$

Any tips on how I can use the assumptions? I was also thinking about strong induction. Tipps would be greatly appreciated before giving me a full solution. But I am glad for any input.

Ansatz:

$$(A_1\wedge A_2\wedge\ldots \wedge A_n \wedge A_{n+1})\rightarrow B$$

equivalent to

$$(A_1\wedge A_2\wedge\ldots \wedge (A_n \wedge A_{n+1}))\rightarrow B$$

equivalent by induction to

$$A_1\rightarrow (A_2\rightarrow(\ldots\rightarrow (A_{n-1}\rightarrow ((A_n\wedge A_{n+1}\rightarrow B)...))$$

equivalent by $$n=2$$:

$$(A_n\wedge A_{n+1})\rightarrow B$$ equivalent to $$A_n\rightarrow (A_{n+1}\rightarrow B)$$

to

$$A_1\rightarrow (A_2\rightarrow(\ldots\rightarrow (A_{n-1}\rightarrow (A_n\rightarrow A_{n+1}\rightarrow B)...))$$

• Thank you very much! I see it now. I was thinking too much in terms of boolean tables. Commented Feb 23, 2021 at 15:48