what is the negation of $\exists^{=1}x\phi(x)$?

Question

I need to understand the negation of counting quantifiers, so in my understanding negation of $\exists^{=n}x \phi(x)$ should be $\exists^{<n}x \neg \phi(x) \lor \exists^{>n}x \neg \phi(x) $. Hence, the negation for $\exists^{=1}x\phi(x)$ is given as follows ? $$\exists^{<1}x \neg \phi(x) \lor \exists^{>1}x \neg \phi(x)$$ Which can be written as follows ? $$\phi(x) \lor \exists^{>1} x \neg \phi(x)$$ Am I doing it right ?

Answer 1

It is a good idea to say it out loud:

$\exists ^{=1} x\phi(x)$ means "there is exactly one $x$ such that $\phi(x)$". So the negation is that "there is not exactly one $x$ such that $\phi(x)$". In other words, either there are less than one $x$ such that $\phi(x)$ or there are more than one $x$ such that $\phi(x)$. So your answer (the first formulation) is nearly right, except that you have incorrectly negated $\phi(x)$.

The same ideas apply to any $n$.

As for the second formulation, $\exists^{<1}x \phi(x)$ is the same as $\neg \exists x \phi(x)$, which is the same as $\forall x \neg\phi(x)$. Sometimes people write $P(x)$ to mean the same as $\forall x P(x)$, but I think it would be confusing in this context.

Answer 2

Not quite: The negation of the existence of exactly $n$ objects having the property $\phi$ is that either less than $n$ or more than $n$ objects do have the property $\phi$: There is no negation. Consider the statement "There is exactly one even prime number": This will be false either if there exist no even prime numbers at all, or if there exists more than one number which is even and prime; "even and prime" will be unnegated in both of those disjuncts.

So in general,

$$\neg \exists^{=n} x \phi(x)\\ = \exists^{<n} x \phi(x) \lor \exists^{>n} x \phi(x)$$

(For an derivation of how this equality comes about, see the last paragraph.)

---

Now for the meaning of $\exists^{<n} x \phi(x)$: This means that there do not exist $n$ objects which are mutually distinct and all have the property $x$, that is,

$$\exists^{<n} x \phi(x)\\ = \neg \exists x_1 \ldots \exists x_n (x_1 \neq x_2 \land \ldots \land x_1 \neq x_n \land \ldots \land x_{n-1} \neq x_n \land \phi(x_1) \land \ldots \phi(x_n)) $$

And $\exists^{>n}$ just means that there exist at least $n+1$ distinct objects with the property $\phi$, i.e.,

$$\exists^{>n} x \phi(x)\\ = \exists x_1 \ldots \exists x_n \exists x_{n+1} (x_1 \neq x_2 \land \ldots \land x_1 \neq x_{n+1} \land \ldots x_n \neq x_{n+1} \land \phi(x_1) \land \ldots \land \phi(x_{n+1})) $$

---

Thus, we have

$$\neg \exists^{=1}x \phi(x)\\ = \exists^{<1} x \phi(x) \lor \exists^{>1} x \phi(x)\\ = \neg \exists x_1 \phi(x_1) \lor \exists x_1 \exists x_2 (x_1 \neq x_2 \land \phi(x_1) \land \phi(x_2))\\ = \text{"There is no object of which $\phi$ holds, or there are at least two distinct objects of which $\phi$ holds"} $$

If you want, you can rewrite $\neg \exists x \phi(x)$ as $\forall x \neg \phi(x)$, and, if your textbook permits for the convention of dropping universal quantifiers, rewrite $\forall x \neg \phi(x)$ as $\neg \phi(x)$, thereby obtaining

$$\neg \phi(x) \lor \exists x_1 \exists x_2 (x_1 \neq x_2 \land \phi(x_1) \land \phi(x_2))$$

Note that the negation of $\phi$ in the first disjuncts comes from $\neg \exists$ which is the translation of $\exists^{<1}x \phi(x)$, while $\phi$ in the second disjunct remains unnegated.

---

As suggested by Bram28 in the comments, this can be systematically derived from the positive =n quantifier. "Exactly $n$" means "at least $n$ and not more than $n$", that is,

$$\exists^{=n} x \phi(x)\\ = \exists^{\geq n} x \phi(x) \land \neg \exists^{\geq n+1} x \phi(x)$$

where

$$\exists^{\geq n} x \phi(x)\\ = \exists x_1 \ldots \exists x_n (x_1 \neq x_2 \land \ldots \land x_1 \neq x_n \land \ldots \land x_{n-1} \neq x_n \land \phi(x_1) \land \ldots \land \phi(x_n))$$

It is obvious that "$< n$" = "not $\geq n$", and "$ > n$" = "$\geq n+1$".

With these observations, we have (I am using "$=$" for definitional equivalence, and "$⟚$" for logical equivalence):

$$\begin{align*} & \neg \exists^{=n} x \phi(x) & \\ = &\neg (\exists^{\geq n} x \phi(x) \land \neg \exists^{\geq n+1} x \phi(x)) & \text{(def. } \exists^{=n} \text{)}\\ ⟚\ & \neg \exists^{\geq n} x \phi(x) \lor \neg \neg \exists^{\geq n+1} x \phi(x)) & \text{(DeMorgan's law)}\\ ⟚\ & \neg \exists^{\geq n} x \phi(x) \lor \exists^{\geq n+1} x \phi(x)) & \text{(double negation elimination)}\\ = & \exists^{<n} x \phi(x) \lor \exists^{>n} x \phi(x) & \text{(def. } <n, >n \text{)} \end{align*}$$

which is precisely the equation in the first paragraph.