# What proof strategy can we use to prove this?

$$\forall x [P(x) \rightarrow Q(x)] \Rightarrow [\forall x P(x) \rightarrow \forall x Q(x)]$$

I tried to do a proof by case, but it doesn't work because of the quantifiers. So I was wondering what are the proof strategies I can use for this.

-
The best strategy is to understand the definitions of $\Rightarrow$ and $\forall x(\ldots)$, then simply show it holds for these two sentences. –  Asaf Karagila Nov 1 '12 at 18:14
Are you working within some formal deductive framework, or are you allowed to argue informally? –  Brian M. Scott Nov 1 '12 at 18:15
informally, i guess. i was trying to show that if the LHS is false, then the RHS can't be true, but there's no way to do that. –  hjggh Nov 1 '12 at 18:17
Okay; I’ve written an answer using informal reasoning and leaving some of it for you to finish. But note that your approach can’t work: you want to show LHS $\Rightarrow$ RHS, so the case that you want to rule out is LHS true and RHS false. –  Brian M. Scott Nov 1 '12 at 18:21
OMG, that makes sense. Ok, I now understand why my approach was wrong. –  hjggh Nov 1 '12 at 18:23

Assuming that you’re allowed to argue informally, I’d assume that $\forall xP(x)\to\forall xQ(x)$ is false. Then $\forall xP(x)$ must be true, and $\forall xQ(x)$ must be false. Thus, every $x$ (in the universe of discourse) has property $P$, but there is at least one $-$ call it $a$ $-$ that does not have property $Q$.

You should now be able to show quite easily that $\forall x [P(x) \rightarrow Q(x)]$ cannot be true, thereby showing the contrapositive of

$$\forall x [P(x) \rightarrow Q(x)] \Rightarrow [\forall x P(x) \rightarrow \forall x Q(x)]\;.$$

-

You are given that $$\tag1\forall x[P(x)\to Q(x).$$ Assume that $$\tag2\forall x P(x).$$ Let $x$ be arbitrary. Then by specialization from $(2)$, you have$P(x)$ and by specialization from $(1)$ you have $P(x)\to Q(x)$, hence by modus ponens $(Q(x)$. By generalization (i.e. because $x$ was arbitrary) $$\tag 3 \forall x Q(x).$$ Since you derived $(3)$ by assuming $(2)$, you have $$\forall x P(x)\to \forall x Q(x).$$

-

Or you can argue directly. What do you need in order to establish a conditional (as on the RHS)?

You assume the antecedent and aim to prove the consequent.

So you are given the LHS i.e. $\forall x [P(x) \rightarrow Q(x)]$, are assuming $\forall x P(x)$ for the sake of argument, and need to show $\forall x Q(x)$.

Do you see how to do that? (If you don't immediately see it, you need to (re)read a decent introduction to predicate logic, as this really is ABC.)

-