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.

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

share|improve this question
    
An additional answer is here: math.stackexchange.com/a/394873/11994 –  Marnix Klooster Sep 23 '13 at 14:57
add comment

3 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

$\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.

share|improve this answer
add comment

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.

share|improve this answer
    
+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)$. –  Marnix Klooster Jun 24 '13 at 4:39
add comment

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.