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:

My answer:

  • 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?

  • $\begingroup$ 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' $\endgroup$
    – Sudeep
    Jul 3 '13 at 2:13
  • $\begingroup$ 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" :( $\endgroup$ Jul 3 '13 at 2:15
  • $\begingroup$ Wait a sec, so are you saying ∃x F(x,x) == ∀x¬F(x,x) ??? $\endgroup$ Jul 3 '13 at 2:19
  • $\begingroup$ 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. $\endgroup$ Jul 3 '13 at 2:23
  • $\begingroup$ @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! $\endgroup$
    – amWhy
    Jul 3 '13 at 15:40

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."

  • $\begingroup$ 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). $\endgroup$ Jul 3 '13 at 2:25
  • $\begingroup$ 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? $\endgroup$ Jul 3 '13 at 2:26
  • $\begingroup$ Your negation is correct above. $\endgroup$
    – amWhy
    Jul 3 '13 at 2:30
  • $\begingroup$ 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. $\endgroup$
    – amWhy
    Jul 3 '13 at 2:32
  • $\begingroup$ 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? $\endgroup$ Jul 3 '13 at 2:35

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

  • $\begingroup$ Indeed I think you're correct in how I was thinking about the parenthesis :/ $\endgroup$ Jul 3 '13 at 2:56

So, you try to assume that the negations don't cancel each other out if you have an even number of negations before the quantifiers. You will then need to follow the exchange rules more thoroughly.

If ¬(∀x, P(x)) = ∃x, ¬P(x), and if ¬(∃x, P(x)) = ∀x, ¬P(x), then it follows that

¬¬(∃x, P(x)) = ¬∀x, ¬P(x)

¬∀x, ¬P(x)=(∃x, ¬ ¬P(x)).

You could consequently suppose that were it the case that P(x) is a proposition, then it would follow that you could infer ¬¬∃x, P(x)=∃x, P(x) this way (which amWhy does in the comment above). This though implies that in predicate logic, P(x) would be a proposition (but is P(x) for all, or for some? Is P(x) a proposition in predicate logic?). But, the formula ¬¬(∃x, P(x)) presupposes the proposition at hand is ¬¬∃x, P(x), not P(x). So, the even number of negations get eliminated before any quantifier exchanges happen. That said, if you were to allow that P(x) is a proposition and ¬¬∃x, P(x) were both propositions, then you could eliminate the even number of negations either way.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.