I have been working on the following problem from Velleman's How to Prove book:

Are these statements true or false? The universe of discourse is the set of all people, and P(x, y) means “x is a parent of y.”

(a) ¬∃x∃y P(x, y)

I tried to solve this in the following steps:

* ¬∃x∃y P(x, y)
* ¬(There exists some x and some y such that x is a parent to y)
* x isn't parent to y

From the Universe of discourse, I conclude that there will be some x who isn't a parent to y and conclude that this statement is True.

But the answer stated here is completely different which states:

It means, There does not exist anyone who is parent of someone. Clearly its False.

Can someone explain the thought process behind this ?


$\neg\exists x\;\exists y\;P(x,y)$ is parsed as $\neg(\exists x(\exists y(P(x,y))))$

Or in English: "There does not exists two people who are parent and child."

However, I know of several such people.

Remember also that the negation of an existential quantifier, is the universal quantifier of a negation.

$$\neg\exists x\;(Q(x)) \qquad\equiv\qquad \forall x\;(\neg Q(x))$$

Which is to say: "There is no person who is ..." means "All people are not ...". Thus wise:

$$\begin{align} & \quad \neg\exists x\;\exists y\;P(x,y) \\ \equiv & \quad\forall x\; \neg\exists y \;P(x,y) \\ \equiv & \quad\forall x\; \forall y \;\neg P(x,y) \end{align}$$

So our statement also reads: "Every two people are not parent and child." This is true only if there are no exceptions.


$ \exists x \exists y P(x, y) $ would mean "there exists $x$ ( for which ) there exists $y$ such that $x$ is a parent of $y$". Now the negation at the beginning I would think is applicable to the first quantifier. So we may as well bracket it $(\lnot \exists x)$. This means there does not exists $x$. Replace this in our first interpretation and we get, "there does not exist $x$ ( for which ) there exists $y$ such that $x$ is a parent of $y$". In simple English this would mean " there is no $x$ (for which) there is a (corresponding) $y$ such that $x $ is a parent of $y$. And you should understand that this clearly means there is no one with in the world with kids. Which is what the nicer statement in the answer tells you.


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.