1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
    Staff Emeritus
    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: 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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Quantifier equivalence in set theory
  1. Set Theory (Replies: 11)

  2. Set theory (Replies: 2)

  3. Set theory (Replies: 4)

Loading...