Are these statements equivalent (quantifiers)?

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

-

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)$$

-
so $\neg (\forall x \exists y) \neg P(x,y) = \neg \forall x \neg \exists y \neg P(x,y)$ ? –  PopularScience Dec 7 '12 at 1:12
why does the negation sign go from left to right? –  PopularScience Dec 7 '12 at 1:16
It can be brought from inside out, too, you get the same result: moving a negation sign in, or out, of quantified statements reverses the quantifier. –  amWhy Dec 7 '12 at 1:17
to deny that a statement is true for all x, you need only assert the existence of an x such that the statement is false. To deny the existence of an x for which something is true, then you assert that for all x, it is not true that that something is true. –  amWhy Dec 7 '12 at 1:39
@amWhy Don't you have to obtain a contradiction to prove the statement in question false? I don't see how. –  Dan Christensen Dec 7 '12 at 5:25

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.

-

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.

-