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

Question

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?

Answer 1

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$.)