The order of quantifiers

Question

I am reviewing for an exam, and I have come across a question that does not contain a solution, so I wanted to verify my answer.

Question 1: If $\exists y \forall x P(x, y)$ is true, then $\forall x \exists y P(x, y)$ is also true.

To me that appears true, because if there exists at least one particular value of $y$ that works for every $x$, then for every $x$ there is at least one $y$ value that satisfies $P(x, y)$.

Question 2: If $\forall x \exists y P(x, y)$ is true, then $\exists y \forall x P(x, y)$ is also true.

I think this one is false. There can exists some value of $y$ that satisfies $P(x, y)$ for every value of $x$, but that does not mean that the value is the same for every $x$.

Am I correct?

Answer 1

Yes. The two statements read as:

1) There exists a $y$ such that for all $x \dots$

2) For all $x$, there exists a $y \dots$

The first statement says that I can pick a $y$ so that no matter what $x$ you give me, $P(x,y)$ will be true.

The second says that you can pick any $x$, and I can pick a $y$ that makes $P(x,y)$ true.

We might rewrite it to exemplify this:

1) There exists a $y$ such that for all $x^* \dots$

2) For all $x^*$, there exists a $y^* \dots$

So you can see that, in the first statement, $y$ exists independent of $x$ chosen, while in the second, $y^*$ is the value corresponding to $x^*$.

Thus, the implication is that $(1)\Rightarrow (2)$ (simply take $y^*$ to be $y$) but not vice versa.

Answer 2

Correct. To demonstrate that something does not follow, it is often helpful to provide a concrete counterexample, e.g. you could assume that $P(x,y)$ stands for $x$ has $y$ as a parent. So then $\forall x \exists y P(x,y)$ becomes the claim that everyone has a parent (true), but $\exists y \forall x P(x,y)$ becomes the claim that there is someone who is the parent of everyone (false)