Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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)$.
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.
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!
