# Homework Help: Quantifier equivalence in set theory

1. Dec 2, 2006

### GregA

1. The problem statement, all variables and given/known data
I have been asked to show that $$\exists xAP(x)\vee\exists xBP(x)$$ is equivalent to $$\exists x(A\cup B)P(x)$$

2. Relevant equations
1) $$P\rightarrow Q \equiv \neg P \vee Q$$
2) $$\neg(P\vee Q)\equiv \neg P \wedge \neg Q$$
3) $$P \vee (Q\vee R) \equiv (P\vee Q) \vee R \equiv P \vee Q\vee R$$

3. The attempt at a solution
$$\exists xAP(x)\vee\exists xBP(x)$$
$$\exists x(x\in A \rightarrow P(x))\vee\exists x(x\in B \rightarrow P(x))$$ definition of the above
$$\exists x[(x\notin A \vee P(x))\vee (x\notin B \vee P(x))]$$ using (1)
$$\exists x(x\notin A \vee x\notin B \vee P(x))$$ using (3)
$$\exists x[\neg(x\in A \wedge x\in B) \vee P(x)]$$ using (2)
$$\exists x[x\in (A\cap B) \rightarrow P(x)]$$ using (1) and simplifying the expression ... $$\exists x(A\cap B)P(x)$$

This is not what the book is asking me to show though!...and I can't see where I've gone wrong either ...Starting from the RHS and trying to show it is equivalent to the LHS gets me:
$$\exists xAP(x)\wedge\exists xBP(x)$$ which is still no good!

Trying to think of it in terms of words then:
Referring to A as (the set of colours of an object), referring to B as (the set of shapes of an object) and P(x) as ( P likes it) then
$$\exists xAP(x)\vee\exists xBP(x)$$ is saying that if there exists a certain colour then P likes the object or if there exists a certain shape then P likes the object
My conclusion $$\exists x(A\cap B)P(x)$$ however says that if there exists a certain shape AND a certain colour then P likes the object

what I am meant to show however seems correct inspite of my efforts ie: $$\exists x(A\cup B)P(x)$$ if there exists a certain shape OR a certain colour then P likes the object

Can anyone show me where I'm going wrong?

Last edited: Dec 2, 2006
2. Dec 2, 2006

### HallsofIvy

That is: "either there exist x in A such that P(x) is true or there exist x in B such that P(x) is true" is equivalent to "there exist x in A union B such that P(x) is true"

Yes, that is one of the two statements

Are you sure that's the same thing? I would interpret this as "either there exist x such that if x is in A then P(x) is true or there exist x such that if x is in B then P(x) is true. If P(x) were false for all x in A or B, both statements would be true!

Since $$x in A \rightarrow x in A\cup B$$ and $$x in B \right arrow x in A\cup B$$,
$$(\exists xAP(x)\vee\exists xBP(x))\rightarrow x in A\cup B P(x)$$

Last edited by a moderator: Dec 2, 2006
3. Dec 2, 2006

$$\exists x(x\in A \rightarrow P(x))\vee\exists x(x\in B \rightarrow P(x))$$

should be $$\exists x(x\in A \vee x\in B) \rightarrow P(x))$$

4. Dec 2, 2006

### GregA

I see your point!...thanks for that
Will now return to my book, figure out where I mis-understood it and then try to finish this question properly

*edit* and thankyou to you Courtigrad as well...I was totally unaware of where I was messing up