What proof strategy can we use to prove this?

Question

$$\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 01 '12 at 18:14
Are you working within some formal deductive framework, or are you allowed to argue informally? — Brian M. Scott, Nov 01 '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 01 '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 01 '12 at 18:21
OMG, that makes sense. Ok, I now understand why my approach was wrong. — hjggh, Nov 01 '12 at 18:23

score 1 · Answer 1 · answered Nov 01 '12 at 18:52

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

score 0 · Accepted Answer · answered Nov 01 '12 at 18:18

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)]\;.$$

score 0 · Answer 3 · answered Nov 01 '12 at 18:30

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

score 0 · Answer 4 · answered Jul 29 '19 at 17:25

There are two proof strategies presented in the answers. I will use a proof checker to show each one and then provide a third strategy. Both start out assuming $∀xP(x)$, but approach the proof differently.

Brian M. Scott then assumed $∀xQ(x)$ was false to derive a contradiction as this proof does:

Hagen von Eitzen derived $Q(x)$ directly.

This proof starts with assuming the negation of the material implication of the goal.

It is useful having multiple strategies one can use to approach a problem.

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

What proof strategy can we use to prove this?

4 Answers4