2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – user359302 Apr 19 at 17:00
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – stratified_mess17 Apr 19 at 21:41
  • $\begingroup$ 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. $\endgroup$ – lemontree Apr 19 at 22:01
  • $\begingroup$ Great, just wanted to make sure I wasn’t being an idiot. Thanks so much! $\endgroup$ – stratified_mess17 Apr 19 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.