4
$\begingroup$

I am trying to understand the negation of propositional logic with regards to universal and existential quantifiers. I want to know if the negation of $∃x, P(x)$ is $∃x, \neg P(x)$ is true or false. I believe that this is true. I know that the negation of a universal quantifier is usually an existential quantifier, and I believe the negation of an existential quantifier is still an existential quantifier. Can anybody let me know if I am correct?

$\endgroup$
1
  • $\begingroup$ False. The negation is $\forall x, \lnot P(x)$. $\endgroup$
    – robjohn
    May 5 '15 at 22:55
3
$\begingroup$

The negation of “there is some $x$ such that $P(x)$” is “not $P(x)$ for any $x$.”

In other words, “for all $x$, not $P(x)$.”

Formally: $\forall x,\neg P(x)$.


Intuitively, the negation of an existential quantifier boils down to the use of a universal quantifier after all, but in quite a sneaky way: the non-existence of something is equivalent to all things not being that something.

For example, let $U(x)$ be the statement that “$x$ is a unicorn.” Then, the statement $\neg[\exists x:U(x)]$ “unicorns don't exist” is equivalent to the statement that “$\textit{every}\text{thing}$ that does exist is not a unicorn,” that is, $[\forall x:\neg U(x)]$. The latter worded statement is in blatant defiance of English semantics (though grammatically correct), but it nevertheless shows where the universal quantifier is hidden in the picture.

$\endgroup$
2
$\begingroup$

False: $\neg \left(\exists x : P(x) \right) \equiv \forall x, \, \neg P(x)$.

Think of this logically. The statement $\exists x : P(x)$ means that there exists (one or more) $x$ so that $P(x)$ is true. Your incorrect negation says that there exists one $x$ so that $P(x)$ is false.

For example, consider the statement: there exists a black horse.

The incorrect negation would be: there exists a horse that is not black.

The correct negation would be: for each horse, that horse is not black.

$\endgroup$
2
  • $\begingroup$ This makes sense. Thank you for clarifying. Would it be right to assume then that the negation of a universal quantifier is an existential quantifier, and the negation of an existential quantifier is a universal quantifier? $\endgroup$
    – Omar N
    May 5 '15 at 22:59
  • $\begingroup$ Yes. Precisely. $\endgroup$
    – MathMajor
    May 5 '15 at 22:59
1
$\begingroup$

Not quite. The negation of an existential quantifier is a universal quantifier. To see this, take an example:

If I claimed that there exists a mad man in town X, then to prove me wrong, you will have to verify that every person in town X is not mad. Not that there exists a person in town X who is not mad, because basically that says nothing about whether or not my statement is true.

$\endgroup$
1
$\begingroup$

As others have mentioned, the answer to your question is no, but it may help to see an example of how to negate statements appropriately. The basic idea is to "push the negation through," changing all $\exists$ signs to $\forall$ and vice-versa and then negate the proposition $P$.

I actually asked a generalized question about negating quantifiers a good while back. You can see the basic idea as follows: suppose we have $$ (\exists x\in\mathbb{R})(\forall y\in\mathbb{R})(y>x).\tag{1} $$ What would be the negation of this? Using the idea of "pushing the negation through": $$ (\forall x\in\mathbb{R})(\exists y\in\mathbb{R})(y\leq x).\tag{2} $$ Can you see how $(2)$ is the negation of $(1)$? It may help further to consider a more linguistic problem that was asked a while back.

$\endgroup$
1
$\begingroup$

When you think about existence and universal, it helps to translate from colloquial English to math-y English to symbols.

The negation of exists is universal.

English: There is an apple in the basket.

Math-y English: there exists some apple (in the basket is true).

Symbols $\exists x P(x)$

When you negate you get the following:

English: There are no apples in the basket.

Mathy-y English: for all apples (in the basket is false)

Symbols: $\forall x ~P(x)$


The negation of universal is existence.

English: All apples are in the basket.

Math-y English: for all apples (in the basket is true)

Symbols: $\forall x P(x)$

When you negate you get the following:

English: There is an apple not in the basket.

Math-y English: there exists some apple (in the basket is false)

Symbols: $\exists x ~P(x)$


Think about this a little while, it will make sense.

$\endgroup$

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.