8
$\begingroup$

How can I get the negation of $\exists!$ (unique existential quantification)? if it's $\forall$, So if I wanna re-negate the last one, I'll get $\exists$ but it's not the same as what we started with! Did I do something wrong here?

For example: $$P : \exists! x\in \mathbb{R} \text{ such that } x^2 = 0$$ it means $\exists x \in \mathbb{R}\text{ such that } x^2 = 0\wedge x $ is unique, So the negation is $\forall x \in \mathbb{R}\space x^2 \ne 0 \vee x \text{ isn't unique}$ is this a false statement?

$\endgroup$
5
  • 1
    $\begingroup$ Out of curiosity, what do you need to do this for? $\endgroup$
    – littleO
    Nov 3, 2012 at 17:42
  • 1
    $\begingroup$ See Uniqueness_quantification and negate the equivalent expression that uses ordinary existential and universal quantification. $\endgroup$
    – user2468
    Nov 3, 2012 at 17:47
  • 2
    $\begingroup$ Maybe I'm just lacking context, but this all seems too fancy for something that should be pretty simple. It seems like a negation of "there exists unique" is just "there does not exist or there exists more than one". $\endgroup$
    – littleO
    Nov 3, 2012 at 17:51
  • $\begingroup$ You want to be careful to use parentheses to clarify the scope of the quantifier and the variables it's quantifying. So $\forall x\in \mathbb{R}((x^2 \neq 0)\lor ((x^2 = 0)\implies \exists y\in\mathbb{R}(y\neq x \land y^2=0))$ $\endgroup$
    – amWhy
    Nov 3, 2012 at 18:46
  • $\begingroup$ Actually, I see my statement immediately above is "redundant", i.e., it is enough, for the op's purposes, to write either $\forall x\in \mathbb{R}((x^2 = 0)\implies \exists y\in\mathbb{R}(y\neq x \land y^2=0))$ OR $\forall x\in \mathbb{R}((x^2 \neq 0)\lor \exists y\in\mathbb{R}(y\neq x \land y^2=0))$ $\endgroup$
    – amWhy
    Nov 3, 2012 at 19:48

5 Answers 5

Reset to default
22
$\begingroup$

I think the best thing to do is unpack what $\exists !$ means.

$\exists ! x \phi(x)$ is shorthand for $$\exists x (\phi(x) \wedge \forall y (\phi(y) \rightarrow y=x))$$

so negating this gives $$\forall x(\neg \phi(x) \vee \exists y(\phi(y) \wedge y \ne x))$$ which is to say: either no $x$ satisfies $\phi$ or there is a $y$ distinct from $x$ which satisfies $\phi$.

This is of the form $\forall x (\neg A \vee B)$, which is the same as $\forall x(A \to B)$, so we could write $$\forall x(\phi(x) \to \exists y(\phi(y) \wedge y \ne x))$$ which is to say: if $x$ satisfies $\phi$ then there is a $y$ distinct from $x$ which does too. This is closer to how I'd think intuitively about the negation of $\exists!$.

Unfortunately there isn't a very succinct way of writing it.

$\endgroup$
6
$\begingroup$

The symbol $\exists !$ means "there exists a unique", and is not really a unit, it carries two conditions: existence and uniqueness. The negation of $A$ and $B$ is not $A$ or not $B$, in symbols:

$$\lnot (A \wedge B) = \lnot A \vee \lnot B.$$

The negation of "there exists" is "there does not exist". The uniqueness assumes existence, and its negation is plurality. So it seems to me that the negation is

There does not exist, or there exist many, such that...

$\endgroup$
4
$\begingroup$

Just write it out, unfold definitions and keep pushing the negation inwards

$\neg \exists ! x, P(x)$

$\neg \exists x, (P(x) \wedge (\forall y, P(y) \to y=x))$

$\forall x, \neg (P(x) \wedge (\forall y, P(y) \to y=x))$

$\forall x, \neg P(x) \vee \neg (\forall y, P(y) \to y=x)$

$\forall x, \neg P(x) \vee \exists y, \neg (P(y) \to y=x)$

$\forall x, \neg P(x) \vee \exists y, P(y) \wedge y\not = x$

You can read this as saying that for each $x$ we must not have $P(x)$ or there's some $y$ satisfying $P(y)$ which isn't $x$. So that could happen if there's absolutely nothing satisfying $P(x)$, or if there's multiple things satisfying it.

$\endgroup$
2
$\begingroup$

Using the simplest definition of $\exists!$ I know, which is $$\langle \exists! x :: P(x) \rangle \;\equiv\; \langle \exists y :: \langle \forall x :: P(x) \equiv x = y \rangle \rangle \;,$$ the negation you're looking for is $$\langle \forall y :: \langle \exists x :: P(x) \equiv x \not= y \rangle \rangle \;.$$

$\endgroup$
3
  • $\begingroup$ Interesting. However the negation is not performed correctly, it should be $\langle \forall y :: \langle \exists x :: P(x) \not\equiv x = y \rangle \rangle$. $\endgroup$
    – Marc van Leeuwen
    May 18, 2013 at 6:16
  • $\begingroup$ @MarcvanLeeuwen I think it is correct, since $P \equiv (E \not= F)$ (my version) is equivalent to $P \equiv \lnot(E = F)$, which is equivalent to $P \not\equiv (E = F)$ (your version). $\endgroup$
    – MarnixKlooster ReinstateMonica
    May 18, 2013 at 11:54
  • $\begingroup$ You are right, although I certainly did not see this immediately. Your point is that for constant Boolean values $A,B$ one has that saying $A\not\equiv B$, which one might as well write $A\neq B$ because they are just values, is the same as saying $A=\lnot B$ (by truth tables or by the excluded middle if you like). I'll give you +1. $\endgroup$
    – Marc van Leeuwen
    May 18, 2013 at 13:02
0
$\begingroup$

Take $\exists! x : E(x)$ if you want to negate that, you have to take $\exists x : E(x) \Rightarrow \exists y\neq x : E(y)$.

$\endgroup$
2
  • $\begingroup$ Let's see if it works. First, $\exists ! x : x=0$. Your negation seems to claim that $\exists x : x=0 \implies \exists y \neq x : y = 0.$ So, $x=0$ and $y=0$ yet $x \neq y$? $\endgroup$
    – Fly by Night
    Nov 3, 2012 at 18:02
  • 1
    $\begingroup$ @FlybyNight: What you appear to be saying is that the negation of a true statement is false... is there a problem with that? The problem with Stefan's answer is that, as written, the $x$ before the $\Rightarrow$ needn't be the same as the $x$ after the $\Rightarrow$. The whole statement needs to be quantified by $\forall x$ and the first $\exists x$ needs to be removed. $\endgroup$
    – Clive Newstead
    Nov 4, 2012 at 10:00

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