Results 1 to 7 of 7

Math Help - Unique Existential Quantifier

  1. #1
    Member
    Joined
    Oct 2010
    Posts
    95

    Question Unique Existential Quantifier

    I am given this unique existential quantifier: \exists !x P(x), which means there is only one single unique x in the domain that statisfy P(x)=true. But I don't understand how would this (\exists x P(x)) \wedge (\forall y, (y\neq x) \rightarrow \lnot P(y)) be equivalent?

    Unique Existential Quantifier-thoughtdiagram.jpgWouldn't (\exists x P(x)) \wedge (\forall y, (y\neq x) \rightarrow \lnot P(y)) mean there is a possibility that there is more than one x in the domain, so long as x\neq y? There could have been like 2 xs that is different from all of the other ys that satisfy P(x)=true. Then in this case, this isn't unique anymore right?


    I also attached a diagram of how I thought of this, with the green zone being the y and the white circles within the green zone being the x. In the diagram, it exists more than one "x" and is not equals to "y", which makes me not understand the equivalence of (\exists x P(x)) \wedge (\forall y, (y\neq x) \rightarrow \lnot P(y)) to \exists !x P(x).

    thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Quote Originally Posted by xEnOn View Post
    I am given this unique existential quantifier: \exists !x P(x), which means there is only one single unique x in the domain that statisfy P(x)=true. But I don't understand how would this (\exists x P(x)) \wedge (\forall y, (y\neq x) \rightarrow \lnot P(y)) be equivalent?
    First, there should not be a closing parenthesis after \exists x\,P(x) because the rest of the formula uses x, so the scope of \exists x must extend to the end of the formula.

    Suppose that P(x_1) and P(x_2) are true, where x_1\ne x_2. If we instantiate x in \exists!x\,P(x) by x_1, then the rest of the formula requires that \forall y\,(y\ne x_1\to\neg P(y)). In particular, for y=x_2, we have y\ne x_1, so it must be the case that \neg P(x_2).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    Posts
    95
    wow...i was like "ohh ya!!" thanks!
    Say I have this statement: "There is only one class which all its students know how to swim."
    And, I let the set of students be S and the set of classes be G, C(x, y) be "student x in class y", and P(x) be "student x knows how to swim".

    Then to show its uniqueness, can I say: \exists ! y \in G \forall x \in S, C(x,y) \to P(x) ?
    And does the "!" do any effect in here? It seems like it could have been unique without the "!".

    And can I also say this: \exists y \in G \forall x \in S, P(x) \wedge \forall k \in G, (k \neq y)\to \neg P(x) ?

    Do these mean the same?
    thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Quote Originally Posted by xEnOn View Post
    Say I have this statement: "There is only one class which all its students know how to swim."
    And, I let the set of students be S and the set of classes be G, C(x, y) be "student x in class y", and P(x) be "student x knows how to swim".

    Then to show its uniqueness, can I say: \exists ! y \in G \forall x \in S, C(x,y) \to P(x) ?
    Yes.
    And does the "!" do any effect in here? It seems like it could have been unique without the "!".
    Yes, "!" is essential here. Otherwise, nothing prevents having two different classes where all students can swim.

    And can I also say this: \exists y \in G \forall x \in S, P(x) \wedge \forall k \in G, (k \neq y)\to \neg P(x) ?

    Do these mean the same?
    Not at all. If S is nonempty and G has more than one member, then this formula is false. Indeed, it says that for some class y, every student x (not necessarily in y) can swim. In addition, when k is another class, x cannot swim. Basically, the formula says that every student can and cannot swim.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2010
    Posts
    95
    hmm...sounds like that statement was contradicting...then could I say them in this way instead?
    <br />
\exists! y \in G \forall x \in S, P(x) \wedge C(x,y)<br />
    or this...
    <br />
\exists! y \in G \forall x \in S, C(x,y) \leftrightarrow P(x)<br />
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Quote Originally Posted by xEnOn View Post
    <br />
\exists! y \in G \forall x \in S, P(x) \wedge C(x,y)<br />
    You should be able to read it and see if this is equivalent to

    \exists! y\in G\,\forall x\in S\,(C(x,y)\to P(x)). (*)

    The formula in the quote above says that there is a unique class that has all students and all of these students can swim. This is very different from (*).

    or this...
    <br />
\exists! y \in G \forall x \in S, C(x,y) \leftrightarrow P(x)<br />
    Obviously, if you replace <-> with ->, you get (*), so this is close. However, this formula says that there is a unique class that has all students that can swim and only such students.

    If you want to write (*) without !, this would be \exists y\in G\,(A(y)\land\forall z\in G\,(y\ne z\to\neg A(z))) where A(y) is \forall x \in S\, (C(x,y) \to P(x)).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2010
    Posts
    95
    cool! Thanks a lot!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: January 6th 2011, 07:23 PM
  2. Quantifier Help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 12th 2010, 07:39 AM
  3. Understanding Existential Instantiation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 25th 2008, 11:48 AM
  4. Existential Instantiation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 11th 2008, 02:30 PM
  5. False Existential
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: February 26th 2008, 05:31 AM

Search Tags


/mathhelpforum @mathhelpforum