How to prove this with induction

Question

$$(P_0 \lor P_1 \lor P_2\lor\ldots\lor P_n) \rightarrow Q $$

is the same as

$$(P_0 \rightarrow Q) \land (P_1 \rightarrow Q) \land (P_2 \rightarrow Q) \land\ldots\land(P_n \rightarrow Q)$$

Do I use strong or weak induction, and how should I go about with it. e.g. I don't have concrete sets to test this on.

---

I'm not quite sure whether I'm on the right track. When showing n = 2.

Answer 1

There is no doubt the induction will be over $n$ here. Start with the base of the induction, that is the case $n=0$. Write both expressions above for the case $n=0$ and show they are equivalent. This should be particularly easy since the two expressions you will get will be typographically identical.

Now, while unneeded for the formal proof, it is a good idea to go ahead and prove the case $n=1$. Now there will be a little bit to do in order to show that the expressions are equivalent. When you are done with that go ahead and do the case $n=2$. You will see that you can do it by using the case $n=1$. This is already a hint that induction should work. Now, try the case $n=3$. By now you should be getting a very strong sense of deja vu. If not do the case $n=4$. Stop when the deja vu is there.

Now attempt the induction step. Assume that when $n=k$ the two expressions are equivalent and proceed to analyse the expressions when $n=k+1$. Use the deja vu feeling from the informal previous step. Formalize this current step and voila - a proof.

Answer 2

You could use truth tables, which is quite unpleasant to some degree, or you can do the following:

Recall, or prove, that $p\rightarrow q$ is equivalent to $\lnot p\lor q$. The first implication can be written as: $$\lnot(P_1\lor\ldots\lor P_n)\lor Q$$

And by DeMorgan laws (which you have to prove by induction based on the law for two propositions), this is equivalent to $$(\lnot P_1\land\ldots\land\lnot P_n)\lor Q$$

Lastly, you should prove that $(A\land B)\lor C$ is equivalent to $(A\lor C)\land(B\lor C)$, and proceed with the obvious generalization by induction. Now we have: $$(\lnot P_1\lor Q)\land(\lnot P_2\lor Q)\ldots\land(\lnot P_n\lor Q)$$ which translates by the first identity used, to: $$(P_1\rightarrow Q)\lor\ldots\lor(P_n\rightarrow Q)$$

---

Note that there are several inductive proofs here (DeMorgan's generalization, the distributivity of disjunction over conjunction); but those are often a preliminary exercise or a given theorem. If they are not, it is much easier to prove those by induction than working through a maze of implications and disjunctions.

Answer 3

You can solve it "embedding" the induction into the formula itself.

You have that the "general case" can be written as :

$$[(P_0 \lor P_1 \lor P_2\lor\ldots\lor P_n) \lor P_{n+1}] \rightarrow Q $$

i.e. $[\mathcal{A} \lor P_{n+1}] \rightarrow Q $

But $P \rightarrow Q$ is $\lnot P \lor Q$, so that the above formula is :

$\lnot [\mathcal{A} \lor P_{n+1}] \lor Q $

Using De Morgan :

$[\lnot \mathcal{A} \land \lnot P_{n+1}] \lor Q $

now distribute :

$(\lnot \mathcal{A} \lor Q)\land (\lnot P_{n+1} \lor Q)$

i.e.

$(\lnot \mathcal{A} \lor Q) \land (P_{n+1} \rightarrow Q)$.

Now, what about $(\lnot \mathcal{A} \lor Q)$ ?

It is :

$\lnot (P_0 \lor P_1 \lor P_2\lor\ldots\lor P_n) \lor Q$

and using "general" De Morgan we have :

$(\lnot P_0 \land \lnot P_1 \land \lnot P_2 \land \ldots \land \lnot P_n) \lor Q$

Distribute again :

$(\lnot P_0 \lor Q) \land \ldots \land (\lnot P_n \lor Q)$

that is :

$(P_0 \rightarrow Q) \land \ldots \land (P_n \rightarrow Q)$

But this was $(\lnot \mathcal{A} \lor Q)$, so that the complete formula will be :

$(P_0 \rightarrow Q) \land \ldots \land (P_n \rightarrow Q) \land (P_{n+1} \rightarrow Q)$.