Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
add comment

3 Answers 3

up vote 0 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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