Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to write a statement in logic symbols that says there is a unique $x$ such that $P(x)$ is true. I've heard of writing this down as $\exists !x P(x) $. But I think I'm not allowed to use the symbol $\exists !$. Now I'm trying to write an equivalent statement without using that symbol. I've come up with two statements, but I'm not sure if one of them is correct:

  1. $\exists x ,\lnot \exists y (P(x) \land P(y) \land \lnot (x=y))$

  2. $\exists x P(x) \land \lnot \exists y (P(y) \land \lnot (x=y))$

My doubt with the first one is that I've never seen a construction like $\exists x, \lnot \exists y (...)$.

My doubt with the second one is that I'm not sure if the variable $x$ in this part $\lnot \exists y (P(y) \land \lnot (x=y))$ is interpreted as a free variable or as the variable with the property $\exists x P(x) $.

share|improve this question
1  
Remember that $\lnot\exists y(\dots)$ is the same as $\forall y\lnot(\dots)$ –  Thomas Andrews Jul 10 '13 at 19:14
    

4 Answers 4

up vote 4 down vote accepted

Remember that $\lnot\exists y(\dots)$ is the same as $\forall y\lnot(\dots)$, your first one is equivalent to:

$$\exists x\forall y \left(\lnot P(x)\lor \lnot P(y)\lor(x=y)\right)$$

So, as another poster said, all you'd need is $\exists x:\lnot P(x)$ to prove this statement. So this statement is actually saying something more complicated.

The second statement is correct, although I'd mind the parentheses there:

$$\exists x \left(P(x) \land \lnot \exists y \left(P(y) \land \lnot (x=y)\right)\right)$$

and again you can replace $\lnot\exists y$ with $\forall y\lnot$, which other answers above have done.

But I prefer to think of $\exists!$ as being shorthand for "there is one, and at most one." That is, two completely separate statements joined by $\land$. So I'd write it as:

$$\left(\exists xP(x)\right)\land\forall y\forall z \left(\left(P(y)\land P(z)\right)\implies y=z\right)$$

share|improve this answer
    
In your last statement, could I replace: $\forall y : \forall z$ with $\forall (y,z)$ ? Alex Kocurek tells me the parenthesis are incorrect in my second statement. Is this correct ? –  Kasper Jul 10 '13 at 19:27
    
Yeah, $\forall y,z$ is technically shorthand for $\forall y\forall z$, @Kasper –  Thomas Andrews Jul 10 '13 at 19:28

In your second expression, you have all the right pieces (propositions) covered, but you need to check which parentheses you need to "put the pieces together".

Note that in what you wrote:

$$\color{blue}{\bf \exists x P(x)} \land \color{red}{\bf \lnot \exists y (P(y) \land \lnot ({\color{black}{\bf x}}=y))}$$

...we have the conjunction of two statements (joined by $\land$). The appearance of $x$ in the right hand expression is unrelated to its appearance in the left hand (blue) proposition. That is, $x$ is unbound on the right. We want to say that its appearance on the right is the same $x$ we are bounding on the left, so we need a large bracket to enclose everything that follows $\exists x$. That gives us:

$$\color{blue}{\bf \exists x \Big[P(x) \land \lnot \exists y (P(y) \land \lnot (x=y))\Big]}\tag{$\dagger$}$$

And with the added bracket, all is good: $\dagger$ is now equivalent to $\exists\, !\, x \,P(x)$.

share|improve this answer
    
That is what I wanted to know ! Thank you :) –  Kasper Jul 10 '13 at 19:59
    
You're welcome, Kasper! –  amWhy Jul 10 '13 at 19:59
    
@amWhy: The color coding gets them everytime! :-) +1 –  Amzoti Jul 11 '13 at 1:56

Your second statement is almost correct, but you need some parentheses. You want to say "There is an $x$ such that $P(x)$ and no other $y$ different from $x$ is such that $P(y)$." This is formalized as: $$\exists x [P(x) \wedge \forall y (x \neq y \rightarrow \neg P(y))]$$

where $x \neq y$ abbreviates $\neg (x = y)$. Alternatively, you can write: $$\exists x [P(x) \wedge \neg\exists y (x \neq y \wedge P(y))]$$

which is like your answer, with appropriate parentheses.

share|improve this answer

The first one is not correct. Consider the case where $\forall x, \neg P(x)$; then it is true that there exists $x$ such that no $y$ satisfies at the same time $P(x)$ and other conditions.

The second one is correct (assuming the right parentheses). Maybe if you rewrite it as $\exists x (P(x) \wedge \forall y (P(y) \Rightarrow x=y))$ it will be clearer.

share|improve this answer
    
Would the second one be incorrect if I write it like this: $\exists x (P(x)) \land \lnot \exists y (P(y) \land \lnot (x=y))$ I think this is incorrect, but I'm not sure why. Is this because it's not clear what is meant with the $x$ in the second part ? –  Kasper Jul 10 '13 at 19:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.