How exactly are these two formulas different from each other? (One is valid and the other is invalid)

Question

I have this formula:

$$\forall y\exists x.\quad P(x,y)\quad \Rightarrow \quad \exists x\forall y.\quad P(x,y)$$

and this one:

$$\exists x\forall y.\quad P(x,y)\quad \Rightarrow \quad \forall y\exists x.\quad P(x,y).$$

I am told that the first one is valid and the second one isn’t.

I am trying to understand how the second formula is not valid in comparison to the first. To me, it seems as if both statements are the same exact thing and I find it very hard to distinguish between the both of them. Please explain this to me like I am 5. I’m just starting to study discrete math, so a lot of this is new to me.

This was taken from MIT OCW's Mathematics for Computer Science

Answer 1

I think you have it backwards. The second one is valid, the first is not. To see that the second is valid, suppose there exists a special $x$ such that $P(x,y)$ holds for all $y$. Then for each $y$ there is an $x$ such that $P(x,y)$, and even more so the same $x$ works for all $y$.

On the other hand, suppose that for every $y$ there is an $x$ such that $P(x,y)$. Then $x$ could be different for every different $y$, so it's not automatically guaranteed that there is an $x$ that works for all $y$.

Answer 2

In the first part of the proposition $(1)$ we have $\exists x\, \forall y$, which means there is (at least) an $x$, say $x_0$, which is suitable for every $y$ such that $P(x_0,y)$ is true. Thus, it is implied that for every $y$ we can find (at least) an $x$ (more particularly the $x_0$) such that $P(x,y)$ is true.

In the first part of the proposition $(2)$ we have $\forall y, \exists x$, which means for every $y$ we can find an $x$, which depends on the choice of $y$ ( usually denoted as $x_y$ or $x(y)$ ) such that $P(x,y)$ is true. However, this does not imply that there is a universal $x$ such that for every $y$ $P(x,y)$ is true.