Negation of Uniqueness Quantifier

Question

Is there a negation of uniqueness quantifier? I need to negate an expression which includes a uniqueness quantifier.

Answer 1

Just expand the quantifier:

$$ \exists ! x ~ P(x) \equiv \exists x ~ (P(x) \wedge (\forall y ~ P(y) \rightarrow y = x)) $$

and apply the usual negation rules for quantifiers.

Answer 2

$\exists!x \varphi(x)$ is an abbreviation for $$\exists x[\varphi(x)\land\forall y(\varphi(y)\to x=y)]\;;$$ if you go through the usual negation machinery ($\lnot\exists x\psi(x)$ is equivalent to $\forall x \lnot\psi(x)$, De Morgan’s laws, etc.), you get $$\forall x[\lnot \varphi(x) \lor \exists y(\varphi(y)\land \lnot(x=y))]\tag{1}$$ for the negation.

Alternatively, you can reason out intuitively that it’s $$(\forall x \lnot\varphi(x)) \lor \exists x\exists y(\lnot(x=y)\land\varphi(x)\land\varphi(y)):\tag{2}$$ either $\phi(x)$ is false for all $x$, or it’s true for at least two different values of $x$. It’s a good exercise to try to show that $(1)$ and $(2)$ are equivalent.

Answer 3

Let $\rm A \oplus B$ denote exclusive disjunction (it can be represented as $\rm\neg(A\iff B)$ if desired), and note three facts about unique existence and negated quantification:

1. $\;\;\;\rm\exists!\, x:Q(x) \iff \exists x:\forall y\;(\neg Q(y) \oplus x=y)$
2. $\rm\neg \exists x:R(x) \iff \forall x:\neg R(x)$
3. $\;\rm \neg \forall x:S(x)\iff\exists x:\neg S(x) $

Putting this all together:

$$\rm \neg\exists!\, x: P(x) \iff \neg(\exists x:\forall y\;(\neg P(y) \oplus x=y))$$ $$\qquad\qquad\quad\rm\iff \forall x\;\neg \forall y (\neg P(y)\oplus x=y)$$ $$\qquad\qquad\qquad\;\rm\iff \forall x\; \exists y:\neg(\neg P(y)\oplus x=y)$$ $$\qquad\qquad\qquad\quad\;\;\iff \forall x \; \exists y:(\neg P(y)\iff x=y)$$ Alternatively, one can write $\rm P(y)\iff x\ne y$ inside the parentheses.