2
$\begingroup$

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

  • 1
    The best strategy is to understand the definitions of $\Rightarrow$ and $\forall x(\ldots)$, then simply show it holds for these two sentences.2012-11-01
  • 0
    Are you working within some formal deductive framework, or are you allowed to argue informally?2012-11-01
  • 0
    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.2012-11-01
  • 0
    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.2012-11-01
  • 0
    OMG, that makes sense. Ok, I now understand why my approach was wrong.2012-11-01

3 Answers 3

0

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

1

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

0

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