What does ∀x∃y actually mean?

Question

I get that it's more or less (all x)(exists y). However,

∀x∃yP(x, y) → ∃x∀yP(x, y) evaluates as false.

∀x∀yP(x, y) → ∀y∀xP(x, y) evaluates as true, which I honestly can't explain.

I don't understand how the 2nd statement can be true seeing as (all x)(all y) implies (all y)(all x) is true, where as (all x)(exists y) implies that (exists x)(all y) is false. The way I see it (all x)(all y) covers any x or y that exists. I probably have some fundamental misunderstanding of the subject.

Answer 1

where as (all x)(exists y) implies that (exists x)(all y) is false

No, it doesn't. It merely does not imply that (exists x)(all y) is true. It's important that you learn at the very beginning that "doesn't imply that $A$ is true" is not the same as "implies that $A$ is false".

The fact that I put milk in my coffee this morning does not imply that it will rain tomorrow. That is different from saying that "the fact that I put milk in my coffee implies that it will not rain tomorrow".

To go back to your main question, you have to work out some habits when reading statements including quantifiers. There are two ways of doing this, depending on your temperament and preferences. It is like deciding whether to turn the bath taps on and off with your left foot or your right: try both, and see which works best.

1. Reading from the inside to the outside: $\forall x \exists y$ is talking about the statement "there exists a $y$ such that...". When does that statement hold? It holds "for all $x$".
2. Reading from the outside to the inside: $\forall x \exists y$ is talking about a statement that holds for all $x$. What is that statement? It is a statement about "there exists a $y$ such that…".

Now, taking your examples:

First statement

As described above, this statement is saying that $\forall x\exists y P(x,y)$ does not imply that $\exists y\forall x P(x,y)$ is true. It is not saying that $\forall x\exists y P(x,y)$ implies that $\exists y\forall x P(x,y)$ is false.

Proving non-implication is easy. All you have to do is find one case where the left-hand side is true and the right-hand side is false. My favourite one is that "everyone has a mother" (for all $x$ there exists a $y$ such that $y$ is $x$'s mother) is true but "there is somebody who is everyone's mother" (there exists a $y$ such that for all $x$, $y$ is $x$'s mother) is false.

One-and-a-halfth statement

You didn't ask about it but here is the answer anyway.

The first statement backwards is true. $\exists y\forall x P(x,y)$ does imply that $\forall x\exists y P(x,y)$ is true. For consider: if all men are descended for Adam (there exists a $y$, Adam, such that for all $x$, $x$ is descended from $y$), then every man has an ancestor (for all $x$, there exists a $y$, Adam, such that $x$ is descended from $y$). All you do is take the value of $y$ which makes the left-hand statement true, and note that it will always make the right-hand statement true as well.

Second statement

There may be clever people who can find a direct proof that $\forall x\forall y P(x,y)$ implies $\forall y\forall x P(x,y)$. Let's not be clever.

First, note that $\forall x\forall y P(x,y)$ is the same as saying that there are no $x$ and $y$ such that $P(x,y)$ is false.

Next, note that this is the same as saying that there are no $y$ and $x$ such that $P(x,y)$ is false.

Finally, note that this is the same as saying that $\forall y\forall y P(x,y)$.

Answer 2

Let's make it clear with a concrete example. Let $x$ and $y$ be integers and let $P(x,y)$ mean $x < y$.

Clearly, for every $x$ there exists some $y > x$. However, there does not exist an integer $x$ where $x < y$ for all integers $y$ (since there is no least integer). This is why the first implication doesn't hold.

In the second, you have "for all" for both $x$ and $y$. You are correct that this covers every choice of $x$ and $y$ and the order does not matter.

Answer 3

Here is the proof that statement 2 is true: 

Let P be some statement involving x and y.

"$\forall x,\forall y, P(x,y)$" means given any object x and any object y, the statement P is true about them.

Similarly,

"$\forall y, \forall x, P(x,y)$" means given any object y, paired with any object x, the statement P is true about them.

Recall that if A and B are statements, the meaning of $$ A\rightarrow B$$ is that "Whenever A is true, B must also be true (Stated more simply, A implies B).

With this in mind, to prove that $$\forall x,\forall y,P(x,y) \rightarrow \forall y,\forall x,P(x,y),$$ we think of the statement $$\forall x,\forall y,P(x,y)$$ as A.

Similarly, we think of the statement $$\forall y,\forall x, P(x,y)$$ as B;

and having made such definitions, it will be safe in the following proof to use each capital letter interchangeably with the statement it represents.

We must show that A implies B:

Suppose A is true. We let y be any object paired with any other object x. Now here comes the trick:

let b be another name for y and a be another name for x.*

Then since "$\forall x,\forall y,P(x,y)$ is true, and that b and a are merely just objects, we know that P(a,b) must also be true because of A; but b is y and a is x, so P(x,y) must also be true. Thus, "$\forall y,\forall x,P(x,y)$," is true. This is the statement B. Thus B is also true.

Altogether, this means that whenever A is true, B is then true; and thus by definition of $A \rightarrow B$, it follows that $A \rightarrow B$ is true.

From our definitions of A and B, we now know for certain that $\forall x, \forall y, P(x,y) \rightarrow \forall y, \forall x, P(y,x)$ is a true statement. This completes the proof.

The following asterisks are merely auxillary statements that I love to point out. You don't need to think about them to understand the proof.

*The x and y in the "A" statement are actually local to that statement and are hence what some call dummy variables: they could be replaced with a and b and the idea that the statement corresponds to would remain unchanged).

**When x and y are in the universe of discourse, of course.