# How can one simplify $¬(¬∃x, P(x))$ and $\neg(\neg\forall x,P(x))$?

What I've learned so far:

$\lnot$($\forall$$x, P(x)) = \exists$$x$, $\lnot$P($x$)

$\lnot$($\exists$$x, P(x)) = \forall$$x$, $\lnot$P($x$)

So far so good (I hope!)

But what about negating a negative "for all" or "there exists":

$\lnot$($\lnot$$\forall$$x$, P($x$)) $=$ ???

$\lnot$($\lnot$$\exists$$x$, P($x$)) $=$ ???

One of the problems says, for example:

Let F(x, y) be the statement "x can fool y." Write "Nobody can fool themselves" with quantifiers, negate it, and then write the negation in English:

• Quantifiers: $\lnot$$\exists$$x$ $F(x, x)$
• Negation: $\exists$$x F(x, x) • English: Someone can fool themselves. I feel that this is right, but I want to be sure: when you negate an entire statement that already has a negative quantifier, that quantifier simply loses the "not," and DOESN'T become the opposite quantifier? - You are right, double negation essentially ends up 'canceling' earlier negation, when it is outside the existential/universal quantification. And if you want to be more picky, a more accurate negation could be 'There exists at least one person who can fool himself' – Sudeep Jul 3 '13 at 2:13 Arrrggh, but see, that messes up how I learned this. I imagined that the "not" sign just gets carried across, from left to right, flipping everything. So I was expecting the negation to be ∃x ¬F(x,x), because it would get applied to F(x,x), after cancelling out the opening "not" :( – CptSupermrkt Jul 3 '13 at 2:15 Wait a sec, so are you saying ∃x F(x,x) == ∀x¬F(x,x) ??? – CptSupermrkt Jul 3 '13 at 2:19 So in other words, my negation ∃x F(x,x) is incorrect, and the correct negation to ¬∃x F(x,x) is ∀x¬F(x,x) ??? Edit: forget that, I'm confusing myself now. Just gonna shut up and read rather than taking stabs at it. – CptSupermrkt Jul 3 '13 at 2:23 @Sudeep: you are very incorrect!: ¬∃x,F(x,x)≡∀x,¬F(x,x). The latter is NOT the negation of the former!: the latter is equivalent to the former. If we negate \lnot \exists x, F(x, x), then we have \lnot (\lnot \exists x, F(x, x)) \equiv \exists x, F(x, x).\;. If we merely push the negation through, which is not negating the proposition, we do have that \lnot \exists x, F(x, x) \equiv \forall x, \lnot F(x, x). Please remove your incorrect comments so as not to confuse any future users! – amWhy Jul 3 '13 at 15:40 show 2 more comments ## 3 Answers In this case, as with propositions, when you have \lnot (\lnot [\text{foo}]), we have "double negation": effectively canceling, leaving you only with [\text{foo}] So,$$\lnot(\lnot \forall x, P(x)) \equiv \forall x, P(x)\lnot(\lnot \exists x, P(x)) \equiv \exists x, P(x)$$Your first translation is correct:$$\lnot \exists x, F(x, x)$$Note that$$\lnot \exists x, F(x, x)\equiv \forall x, \lnot F(x, x)$$And the negation of this is$$\lnot(\lnot \exists x, F(x, x)) \equiv \exists x, F(x, x)$$Added: Your translation of the negation of the proposition is correct, given the domain is that of "all people": "There exists someone who can fool him/herself," which is less awkwardly stated as "Someone can fool themselves." - Okay, so I guess my point of friction here is, I don't understand why the outer negative "cancels" on the quantifier, but has no effect on P(x). – CptSupermrkt Jul 3 '13 at 2:25 Because in ¬(∀x, P(x)) = ∃x, ¬P(x), the negation affects BOTH the quantifier and the P(x). So what is it about the opening negation on a quantifier that kills the negation from affecting the rest? – CptSupermrkt Jul 3 '13 at 2:26 Your negation is correct above. – amWhy Jul 3 '13 at 2:30 Sudeep is incorrect: \lnot \exists x, F(x, x) is equivalent to \forall x \lnot F(x, x), so the second is NOT the negation of the first!. Your negation is absolutely correct in your posted answer. – amWhy Jul 3 '13 at 2:32 Oh, phew, thanks! In that case, the only question is, why does P(x) not get affected by a negation if the opening quantifier is negated? Is this just something I'll need to remember as a rule, like if the opening quantifier has a negative, and the whole statement gets negated, the single and only thing to do is just remove the negation on the quantifier, and NOT apply it to the rest of the statement? – CptSupermrkt Jul 3 '13 at 2:35 show 3 more comments I think you are confusing yourself by distinguishing between \neg \exists x \ F(x, x), and \neg(\exists x \ F(x, x)) when in fact both are exactly the same. So we would have$$\neg(\neg \exists x \ F(x, x)) \equiv \exists x \ F(x, x)$\$

-
Indeed I think you're correct in how I was thinking about the parenthesis :/ –  CptSupermrkt Jul 3 '13 at 2:56