# Attacking proof of a statement with the form: $(\forall x \in X): ( P_1(x) \lor P_2(x) ) \rightarrow Q$

I have a statement of the form $$(\forall x \in X): ( P_1(x) \lor P_2(x) ) \rightarrow Q$$ but I am not sure how to approach proving it. I feel as though there is some sort of case analysis that can be done, but I do not see how to make use of the $$\forall x \in X$$ part of the statement in this context. If I was instead interested in $$( P_1 \lor P_2 ) \rightarrow Q$$, approaching the proof by different cases would be more clear for me.

Sadly, I am not sufficiently knowledgeable in logic or proofs to know what direction to go down. I am sure this is simple for someone who's experienced, so can anyone give me some guidance?

• Rewrite it explicitly as $\forall x( \ x \in X \rightarrow ( \ (P_1(x) \lor P_2(x) \ ) \rightarrow Q \ ) \ )$; restricted quantifiers can be somewhat confusing – user359302 Apr 19 at 17:00

As pointed out in a.c.bruno's comment, your formula $$(\forall x \in X): (P_1(x) \lor P_2(x)) \to Q)$$ is just shorthand for $$\forall x(x \in X \to ((P_1(x) \lor P_2(x)) \to Q))$$ which is logically equivalent to $$\forall x((x \in X \land ((P_1(x) \lor P_2(x))) \to Q)$$

So what you have to prove is actually a universally quantified two-fold implication, which can be re-written as a single implication where the antecedent is a conjunction of a set membership restriction and a disjunction.
But thinking of it in terms of a simple implication with a disjunction as the antecedent and with the background thaught in mind that the elements predicated over are restricted to a particular set ($$X$$) is i.m.o. easier, and all you need for the proof.

For the universal quantifier, since what you want to prove is "for any $$x$$", the usual procedure is to start with "Let $$x \in X$$ be arbitrary", carry out the proof for that dummy element you chose, and eventually state "Since $$x$$ was chosen arbitrarily, the proposition holds for all $$x \in X$$".
What you have to prove for that dummy element is the implication $$(P_1(x) \lor P_2(x)) \to Q$$.
To show prove an implication, you have two (equivalent, but procedurally slightly different) ways to proceed:
You can prove $$A \to B$$ either by

1. showing that in all cases, either $$A$$ is false or $$B$$ is true, or
2. assuming $$A$$, and deriving $$B$$ from this assumption.

For statetements with "arbitrary $$x$$"'s, normally 2. is the more natural option, since you don't know anything about $$x$$ other than the fact that it comes from $$X$$ (after all, you want to keep your $$x$$ arbitrary). So what you have to show is

"Assume $$P_1(x) \lor P_2(x)$$. Then $$Q$$."

And now it becomes obvious that you indeed have to perform a case analysis:

"Two cases:
- $$P_1(x)$$: ... Therefore $$Q$$.
- $$P_2(x)$$: ... Therefore $$Q$$."

The "..." part will likely exploit the fact that $$x \in X$$, so your two cases are actually

1. $$x \in X \land P_1(x)$$
2. $$x \in X \land P_2(x)$$

(This follows from distributivity of disjunction over conjunction: $$x \in X \land (P_1(x) \lor P_2(x)) \equiv (x \in X \land P_1(x)) \lor (x \in X \land P_2(x))$$).

From this case analysis, the statement $$(P_1(x) \lor P_2(x)) \to Q$$ follows immediately.

The last step is now simply to show that the proof holds indeed for any $$x$$, since the dummy $$x$$ you used in your proof was chosen arbitrarily. (So you need to make sure in your case analysis that you don't impose any assumptions on $$x$$ other than that it be an element of $$X$$.)

• This was tremendously useful, thank you for your write up! My only question is when you wrote "What you have to prove for that dummy element is the implication $(P_1(x) \rightarrow P_2(x))$". Do you mean to say that I have to prove the implication $(P_1(x) \lor P_2(x)) \rightarrow Q$ for a dummy element $x$? With that change, I think the rest of what you wrote makes complete sense to me! – stratified_mess17 Apr 19 at 21:41
• That was of typo; of course I meant the implication $(P_1(x) \lor P_2(x)) \to Q$, as you figured out. Fixed it. – lemontree Apr 19 at 22:01
• Great, just wanted to make sure I wasn’t being an idiot. Thanks so much! – stratified_mess17 Apr 19 at 22:02