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.

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?

share|improve this question
    
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

3 Answers 3

up vote 5 down vote accepted

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

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

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

share|improve this answer
    
Indeed I think you're correct in how I was thinking about the parenthesis :/ –  CptSupermrkt 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.

share|improve this answer

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.