Are these statements equivalent (quantifiers)?

Question

$\neg \forall x \exists y \neg P(x,y)$ is equal to $\exists x \exists y \neg P(x,y)$

I had to make sure, because I wasn't sure at all.

Answer 1

Is $\;\;\neg \forall x \exists y \neg P(x,y)\;\;$ equal to $\;\;\exists x \exists y \neg P(x,y)\;\;$?

No. See the following chain of equivalences to see why not:

$$\neg \forall x \exists y \neg P(x,y) \;\;\equiv \;\;\exists x \neg \exists y \neg P(x, y) \;\; \equiv \;\;\exists x \forall y \neg\neg P(x, y) \;\; \equiv \;\; \exists x\forall y P(x, y)$$

We used the facts that $\lnot \forall \varphi(x) \equiv \exists x \lnot \varphi(x)\;$ and $\;\lnot \exists x \varphi(x) \equiv \forall x \lnot \varphi(x)$.

---

Alternatively, again using the equivalences $\lnot \forall \varphi(x) \equiv \exists x \lnot \varphi(x)\;$ and $\;\lnot \exists x \varphi(x) \equiv \forall x \lnot \varphi(x)$:

$$\neg \forall x \exists y \neg P(x,y) \;\;\equiv\;\; \neg \forall x \neg \forall y P(x,y) \;\;\equiv\;\; \neg\neg \exists x \forall y P(x,y)\;\;\equiv \;\;\exists x \forall y P(x,y)$$

Answer 2

To get an intuitive grip on it, simplify matters by letting $Q(x,y)$ mean $\lnot P(x,y)$, so that you can rewrite the statements as $\lnot\forall x\exists y~Q(x,y)$ and $\exists x\exists y~Q(x,y)$, respectively. The second statement is easy to understand: it just says that there’s at least one pair of objects $a$ and $b$ for which $Q(a,b)$ is true.

To see in more intuitive terms what the first statement says, look at its negation, $\forall x\exists y~Q(x,y)$: this just says that for each $x$ there is a $y$ making $Q(x,y)$ true. Its negation (i.e., the original statement $\lnot\forall x\exists y~Q(x,y)$) must therefore say that there is at least one object $a$ such that no $y$ makes $Q(a,y)$ a true statement. What if this $a$ is the only object in the domain of discourse? Then $\lnot\forall x\exists y~Q(x,y)$ is true but $\exists x\exists y~Q(x,y)$ is false.

However, you should also be able to manipulate the expressions formally as in amWhy’s answer, using the facts that $\lnot\exists x~\varphi(x)\equiv\forall x~\lnot\varphi(x)$ and $\lnot\forall x~\varphi(x)\equiv\exists x~\lnot\varphi(x)$. In words, you can move a negation through a quantifier if you change the quantifier from $\forall$ to $\exists$ or from $\exists$ to $\forall$, whichever is relevant.

Answer 3

Here is a counter-example: Let the domain of quantification be $U=\{ x, y \}$ with distinct $x$ and $y$. And let $P$ be the "is equal to" relation on $U$. Then the LHS is false while the RHS is true.