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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.