Is there a negation of uniqueness quantifier? I need to negate an expression which includes a uniqueness quantifier.
Negation of Uniqueness Quantifier
-
0An additional answer is here: http://math.stackexchange.com/a/394873/11994 – 2013-09-23
3 Answers
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.
$\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.
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:
- $\;\;\;\rm\exists!\, x:Q(x) \iff \exists x:\forall y\;(\neg Q(y) \oplus x=y)$
- $\rm\neg \exists x:R(x) \iff \forall x:\neg R(x)$
- $\;\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.
-
0+1 for mentioning (1). By the way, I prefer to write $\not\equiv$ instead of $\oplus$, since not only are both operators associative and symmetric, they are even mutually associative: $P \equiv (Q \not\equiv R)$ is equivalent to $(P \equiv Q) \not\equiv R$. And to $\lnot(P \equiv Q \equiv R)$. – 2013-06-24