# Unique Existential Quantifier

• February 26th 2011, 12:27 AM
xEnOn
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?

Attachment 20955Wouldn'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 $x$s that is different from all of the other $y$s 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!
• February 26th 2011, 01:24 AM
emakarov
Quote:

Originally Posted by xEnOn
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)$.
• February 26th 2011, 11:57 PM
xEnOn
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!
• February 27th 2011, 05:10 AM
emakarov
Quote:

Originally Posted by xEnOn
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.
Quote:

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.

Quote:

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.
• February 27th 2011, 06:30 AM
xEnOn
hmm...sounds like that statement was contradicting...then could I say them in this way instead?
$
\exists! y \in G \forall x \in S, P(x) \wedge C(x,y)
$

or this...
$
\exists! y \in G \forall x \in S, C(x,y) \leftrightarrow P(x)
$
• February 27th 2011, 09:13 AM
emakarov
Quote:

Originally Posted by xEnOn
$
\exists! y \in G \forall x \in S, P(x) \wedge C(x,y)
$

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

Quote:

or this...
$
\exists! y \in G \forall x \in S, C(x,y) \leftrightarrow P(x)
$

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))$.
• February 28th 2011, 10:07 AM
xEnOn
cool! Thanks a lot! :D