3
$\begingroup$

Let us consider the statement $\exists x P(x)$ - translated into English, "there exists an $x$ in our universe of discourse such that $P(x)$ is true." In writing the negation of this, we are taught to switch quantifiers ($\exists \leftrightarrow \forall$) and to negate that statement $P(x)$.

Thus,

$$\neg (\exists x P(x)) = \forall x (\neg P(x))$$

However, humor me for a second. Let's consider what negation is - it is the "logical complement." The negation of a statement is always false when the statement is true, and vice versa. In that light, why would we not say the following is also the negation?

$$\neg (\exists x P(x)) = \not \exists x P(x)$$

Or, taking this a bit further, why would we not write this as well?

$$\forall x (\neg P(x)) = \not \exists x P(x)$$

Both seem to imply the same thing: there does not exist an $x$ such that $P(x)$ is true (and thus for all $x$, $P(x)$ is false, or, rather, $\neg P(x)$ is true).

So is there some underlying reason why we don't do negations in this way? As far as I can tell, they mean the same thing, yet I always have seen the $\forall$ version as above. Looking around MSE, I've only seen some posts which have $\neg \exists$ (basically the same as $\not \exists$), but they're only in the context of simplifying a logical expression.

So I guess, if indeed these are logically equivalent, my follow-up question would be - why is $\forall$ considered a simplification of $\neg \exists$ or $\not \exists$?

My only guess is that "$\not \exists$" isn't a standard notation, or so I recall from some notes my complex analysis professor gave us last semester. Or perhaps to say "for all $x$, this is false" more immediately is understood (or a more "direct" way of saying it) than "there does not exist $x$ such this is true?"

(Footnote of note: I haven't had much education in predicate logic and such. We went over it for a little while in one of my classes so I understand some basics like the above but we never went into much detail. So I apologize if this question is poorly framed or worded.)

$\endgroup$
  • 1
    $\begingroup$ The idea of "there exists no $x$ such that $P(x)$ is true" is equivalent to "for all $x$, $P(x)$ is not true". I think it is just easier to work with something like "for all $x$, $P(x)$ is not true" rather than saying "there is no $x$ such that $P(x)$ is true". $\endgroup$ – Dave Jan 1 at 0:11
  • $\begingroup$ Okay, that resolves one doubt of mine regarding their equivalence. Though it then raises my follow up question - why is the latter phrasing favored? $\endgroup$ – Eevee Trainer Jan 1 at 0:12
  • 1
    $\begingroup$ I edited my comment to say that I think the "for all" statement is easier to work with than "there exists no..". I'm not entirely sure why one is used over the other, but in fact I know some people who often phrase it as "there exists no...". $\endgroup$ – Dave Jan 1 at 0:14
4
$\begingroup$

The two statements are equivalent, the reason why we write it that way it is because it is easier to deal/prove it. It is irrelevant which way it is easier to say it, the important thing is being able to use.

Just consider the statement $\exists x \in \mathbb Z, x^2+(x+1)^2 \mbox{ is even}$. This is not true, now try to show that this is false.

Try to prove separately each of the following two statements:

  • $\not\exists x \in \mathbb Z, x^2+(x+1)^2 \mbox{ is even}$
  • $\forall x \in \mathbb Z, x^2+(x+1)^2 \mbox{ is odd}$

It is easier to deal with the second one.

$\endgroup$
  • 1
    $\begingroup$ Ahhhh, I see, I can't believe I looked over something so basic. Thanks for your insight, I appreciate it. ^_^ $\endgroup$ – Eevee Trainer Jan 1 at 0:20
  • 2
    $\begingroup$ Good answer, +1. This is basically what I was trying to say with the "for all" statements being easier to work with. $\endgroup$ – Dave Jan 1 at 0:26
3
$\begingroup$

Which form to consider simpler is basically a matter of taste and convention.

There are some accounts of predicate logic that consider $\exists$ the only primitive quantifier and treat $\forall x\,\varphi$ as an abbreviation for $\neg\exists x\neg\varphi$.

My impression is that this is something of a minority option these days, but it is not wrong as such.

$\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.