Logic Quantifier

80 Views Asked by At

If $∃ x ∀ y$ $P(x,y)$ is false and that the domain of discourse is nonempty. Is $∀ x ∃ y P(x,y)$ also false?

I know that by de Morgan laws $∃x∀y P(x,y)$ can become $∀x∃y ⌐P(x,y)$ and that would be true because we know that $∃{x} \forall {y} P(x,y)$ is false.

But is there anything that says something about the negation on $P(x,y)$ when proposition has the same quantifier that can help to determine the value of $∀x∃y P(x,y)$?

2

There are 2 best solutions below

2
On

No, here's a counter example, suppose $\mathrm{P}(x,y)$ is “$x\geqslant y$”, and that the domain of discourse is that of the natural numbers, then $\exists x\,\forall y\,\mathrm{P}(x,y)$ is certainly false, however $\forall x\,\exists y\,\mathrm{P}(x,y)$ is true.

0
On

Say our universe is a group of people, and $P(x,y)$ means "$x$ is friends with $y$". Then your first sentence, $\exists x\forall yP(x,y)$ means there's one person who's friends with everyone - that's a very popular person! But $\forall x\exists yP(x,y)$ just means "everyone has a friend". If that weren't true, we'd have at least one very lonely person in our group.

It's perfectly reasonable that we might have someone super popular, and if we do it will certainly be that no one's lonely - but if we don't have anyone super popular, that doesn't have anything to do with other peoples' loneliness. For example, if Jack is friends with Jill, Jill is friends with James, and James is friends with Joanne, but Jack hates James and Joanne, and Joanne hates Jill and Jack, then no one's friends with everyone - but no one's a loner. On the other hand, Jack, Jill, James, and Joanne could all hate each other, in which case everyone's lonely. These extremes show that knowing that $\exists x \forall y P(x,y)$ is false doesn't tell you anything about whether $\forall x\exists y P(x,y)$ is true - it could go either way.