Solving problem about disjunction, conjunction, implication, and equivalence, by induction

Question

How to solve with induction?

For all finite sets $I \neq \emptyset$.

$ \left( \bigvee_{i \in I} P_i \right) \Rightarrow Q \equiv \bigwedge_{i \in I} (P_i \Rightarrow Q)$

Answer 1

Let $n$ be the size of the set $I$. We'll induct on $n$, of course, and we'll use a result that's easily verified: $$ (a\lor b)\Rightarrow c\equiv (a\Rightarrow c)\land(b\Rightarrow c)\qquad\text{(*)} $$

Base: ($n=1$) Obviously $P_1\Rightarrow Q\equiv P_1\Rightarrow Q$

Induction Assume the result is true for all sets of predicates of size $n$ and let $I$ be a set of $n+1$ predicates. Then $I = \{P_1, P_2, \dots, P_n\}\cup \{P_{n+1}\}$. Call the set $\{P_1, P_2, \dots, P_n\}=J$. We then have $$ \bigvee_{i\in I}P_i\equiv \left(\bigvee_{i\in J}P_i\right)\lor P_{n+1} $$ and so we have, $$ \begin{align} \left(\bigvee_{i\in I}P_i\right)\Rightarrow Q&\equiv \left(\left(\bigvee_{i\in J}P_i\right)\lor P_{n+1}\right)\Rightarrow Q\\ &\equiv\left(\left(\bigvee_{i\in J}P_i\right)\Rightarrow Q\right)\land (P_{n+1}\Rightarrow Q)&\text{by (*)}\\ &\equiv\left(\bigwedge_{i\in J}(P_i\Rightarrow Q)\right)\land(P_{n+1}\Rightarrow Q) &\text{by assumption}\\ &\equiv\bigwedge_{i\in I}(P_i\Rightarrow Q) \end{align} $$ establishing the equivalence we needed.