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).

Answer 2

The statements $\forall y \exists x P(x, y)$ and $\exists x \forall y P(x, y)$ say similar things. The primary difference is whether the choice of $x$ is permitted to change with $y$. The former, $\forall y \exists x P(x, y)$, allows for $x$ to change with $y$, whereas the latter, $\exists x \forall y P(x, y)$, doesn't. There has to be some fixed $x$ that makes $P(x, y)$ true, regardless of what you substitute in for $y$.

So, if $\exists x \forall y P(x, y)$, then regardless of the value of $y$, we can use this universally acceptable choice of $x$ for our given $y$. Our choice of $x$ is allowed to change when $y$ changes, but in this case, it is unnecessary. We still have $\forall y \exists x P(x, y)$.

Let's take two examples over the integers. Let \begin{align*} P(x, y) &: x + y = 0 \\ Q(x, y) &: xy = 0. \end{align*}

Note that $\forall y \exists x P(x, y)$ is true; given any integer $y$, we may simply choose $x$ to be $-y$. Tell me a number $y$ (you might say "$27$" for example), and I can come back with a good $x$ ("$-27$", I'd retort). Changing $x$ will change the $y$ necessary to make $P(x, y)$ true. There is no one $x$ such that $x + \underline{\hspace{7pt}} = 0$, regardless of what integer you put in the blank space. This is why $\exists x \forall y P(x, y)$ is false.

On the other hand, $\exists x \forall y Q(x, y)$ is true: take $x = 0$ for example. No matter what the value of $y$ is, $Q(0, y)$ is always true. This implies $\forall y \exists x Q(x, y)$. If you tell me a number $y$ ("$316$", you might say), I can come back with an $x$ ("$0$", I'd say) that makes $Q(x, y)$ true. For this reason, $\forall y \exists x Q(x, y)$ is true, and hopefully you can see how it is implied by $\exists x \forall y Q(x, y)$.

Answer 3

$ 1. \:\exists x \forall y P(x,y) \\ 2.\:\forall y P(a,x) \: (1. existential \: specification)\\ 3.\:P(a,b)\:(2.\:universal\:specification)\\ 4.\:\exists x P(x,b)\:(3.\:existential\:generalization)\\ 5.\:\forall y \exists x P(x,y) \:(4.\:universal\:generalization)$

$$ \exists x \forall y P(x,y) \to \forall y \exists x P(x,y) $$