# What does ∀x∃y actually mean?

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.

• So you say you don't understand why "for all x and y that exist" is the same as "for all y and x that exist"? Sep 27, 2016 at 5:07
• How about $\forall x \exists y P(x,y) \to \exists x \exists y P(x,y)$ ? Is that true? (Then they are only weakened, not strengthened)
– Emil
Sep 27, 2016 at 5:18
• "for all men there exists a father" does not implies that "there is a father for all men"... Sep 28, 2016 at 6:07

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…".

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

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

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.

• It seems that the "for all" for both $x$ and $y$ is what is confusing pajkatt the most. Sep 27, 2016 at 5:13
• Well for all is to AND as summation is to addition. Perhaps that analogy and a demonstration of the distributive properties of AND may help? Sep 27, 2016 at 5:14
• I'm not sure I like your concrete example. In any model of the sentence $\forall x\exists yP(x,y)$ either the relation $P$ contains a directed cycle, or else the universe is infinite. Both alternatives seem implausible under your interpretation.
– bof
Sep 27, 2016 at 5:14
• @bof Good point. I will change the example. Sep 27, 2016 at 5:18
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.

∀x∃yP(x, y) → ∃x∀yP(x, y)

evaluates as false.

1) ∀x∃y: For every x there exists a y

2) ∃y∀x: There exists a y (such that) for every x

Consider this example:

1) Everyone is married to someone (ie. For every person there exists a person to whom he/she is married) True

2) Someone is married to everyone (ie. There is someone who is married to everyone) False

Therefore evaluates as false.

Also this

∀x∀yP(x, y) → ∀y∀xP(x, y)

Note: Here you can't say everyone is married to everyone in the first place. Even if you do it's pointless to see the implied statement then. Since first itself is a false statement.

For the universe of people and tasty food in a food competition:

1) Everyone can eat all food. ∀x∀yP(x, y)

2) All food can be eaten by everyone. ∀y∀xP(x, y)

Which kinda makes sense why the second one is true! I guess. If you have better example for second example pls comment! :) I'll change the last bit!