My text claims that the following is true, but this seems erroneous to me. Am I correct in believing that this is an error in the text?
$$\neg(\exists x \forall y \;(x \geq y)) \iff \forall x\; \neg(\forall y, (x\geq y))$$
Thank you for your help!
$\begingroup$
$\endgroup$
5
-
$\begingroup$ They are negations of each other, so it is erroneous. $\endgroup$– DHMOCommented Apr 18, 2017 at 15:16
-
$\begingroup$ The edited version of the claim is not erroneous. For any $P$, we have (at least in classical logic) $\neg(\exists x, P) \iff \forall x, \neg P$ ($P$ can have many free variables, in your case, it has 2). $\endgroup$– Maxime RamziCommented Apr 18, 2017 at 15:30
-
$\begingroup$ Oops, I made a mistake in copying the first part. Are these then equivalent? The first statement suggests that there is an object greater than/equal to all other objects, but the second seems to be a different statement $\endgroup$– MakMakCommented Apr 18, 2017 at 15:31
-
$\begingroup$ And you can proceed with $\forall x \exists y \neg(x \geq y)$ and then $\forall x \exists y (x \ngeq y)$. $\endgroup$– amrsaCommented Apr 18, 2017 at 15:38
-
2$\begingroup$ The right hand side says: For any x you choose, the statement $(\forall y, (x\geq y))$ will not be true. The left hand side says: It is not possible to choose an x to make the statement true. In other words, "you will always fail" and "you will never succeed". These are the same thing. $\endgroup$– Jaap ScherphuisCommented Apr 18, 2017 at 15:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It's correct.
In general you have:
$$\neg \exists x \phi \Leftrightarrow \forall x \neg \phi$$
for any variable $x$ and formula $\phi$. Informally that makes sense: if it is not true that there is something for which something holds, then apparently that something does not hold true for everything, and vice versa. Or, given that typically $\phi$ says something about $x$, i.e expresses some property of $x$: If there isn't anything with some property, then everything does not have that property, and vice versa.
Now, in your case, $\phi$ happens to be $\forall y \ x \ge y$, which may be somewhat confusing given the presence of another quantifier, but the general rule always applies, so just plug it in, and you get:
$$\neg \exists x \forall y \ x \ge y \Leftrightarrow \forall x \neg \forall y \ x \ge y$$
