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.

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

share|improve this question
add comment

3 Answers 3

up vote 7 down vote accepted

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

share|improve this answer
    
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
show 2 more comments

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.

share|improve this answer
add comment

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.

share|improve this answer
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.