[Math] prove whether ∃x∀yP(x, y) logically implies ∀y∃xP(x, y) or not.

Question

logical implication in this sense really trips me up, and I don't understand it.

What I know of this problem so far is,

for some x all y are true in P(x,y)

and then I have to show whether that logically implies

for all y some x are true in P(x,y)

I know they aren't logically equivalent, but logical implication is hard for me to grasp.

If you could explain how I could relate the two to check for logical implication i would appreciate it.

Answer 1

Suppose the first statement is true. That is, for some $x$, $P(x,y)$ is true for all $y$. Let this $x$ be $n$. We can now rephrase this as "for all $y$, $P(n,y)$ is true". It follows from this that for all $y$, there exists an $x$ ($n$) such that $P(x,y)$ is true. Thus, the second statement follows from the first statement.

Now let's address why the second statement doesn't imply the first one. Consider the relation $P(x,y)$ that is true if $x - y = 1$ and false otherwise. The second statement is true, because for all $y$, $P(y + 1,y)$ is true (so there exists an $x$ with $P(x,y)$ true), but the first statement is false, as there is not an $x$ such that $x - y = 1$ for all $y$.

So (1) implies (2) but (2) does not imply (1).