Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Quantifier equivalence in set theory

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



    2. Relevant equations
    1) [tex] P\rightarrow Q \equiv \neg P \vee Q[/tex]
    2) [tex] \neg(P\vee Q)\equiv \neg P \wedge \neg Q [/tex]
    3) [tex] P \vee (Q\vee R) \equiv (P\vee Q) \vee R \equiv P \vee Q\vee R [/tex]


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

    This is not what the book is asking me to show though!...and I can't see where I've gone wrong either:frown: ...Starting from the RHS and trying to show it is equivalent to the LHS gets me:
    [tex]\exists xAP(x)\wedge\exists xBP(x)[/tex] 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
    [tex]\exists xAP(x)\vee\exists xBP(x)[/tex] 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 [tex]\exists x(A\cap B)P(x)[/tex] 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: [tex]\exists x(A\cup B)P(x)[/tex] 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. jcsd
  3. Dec 2, 2006 #2

    HallsofIvy

    User Avatar
    Science Advisor

    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 [tex]x in A \rightarrow x in A\cup B[/tex] and [tex]x in B \right arrow x in A\cup B[/tex],
    [tex](\exists xAP(x)\vee\exists xBP(x))\rightarrow x in A\cup B P(x)[/tex]
     
    Last edited by a moderator: Dec 2, 2006
  4. Dec 2, 2006 #3
    [tex]\exists x(x\in A \rightarrow P(x))\vee\exists x(x\in B \rightarrow P(x))[/tex]


    should be [tex]\exists x(x\in A \vee x\in B) \rightarrow P(x))[/tex]
     
  5. Dec 2, 2006 #4
    I see your point!...thanks for that :smile:
    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
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook