Confused as to why these two statements would not be equal

Question

$$∀x ∃y ∀z p(x,y,z) ≠ ∀x ∀z ∃y p(x,y,z)$$

I need to prove this is true, but am confused since the only difference in the two statements is that the order of the $∀z$ and $∃y$ is reversed.

Answer 1

Here is an example where they are not equivalent. Interpreting the symbols, Suppose that our variables can take values in $\mathbb R \setminus \{0\}$ and that $p(x,y,z)$ is said to hold if $xyz = 1$. Then the right-hand statement is true: Whenever we have some non-zero $x$ and $z$, then we can let $y = 1/xz$ to ensure that $xyz = 1$. Thus, in these semantics, the formula $(\forall x) (\forall z) (\exists y) p(x,y,z)$ is true.

However, Let $x = 1$ and let $y$ be arbitrary. Then for $z \neq 1/y$. Then $xyz \neq 1$. This proves the negation of $(\forall x) (\exists y) (\forall z) p(x,y,z)$, so this formula is false.

Do you think you could formalize this?

Answer 2

This is because in the LHS, the existing $y$ must only be a function of $x$ NOT $z$ but in the RHS, $y$ can be a function of both $x$ and $z$. This is why the RHS and LHS are not equivalent.

Answer 3

It often helps to break these formulas down into quasi-English to see what they're trying to say.

For the left-hand side:

"For every $x$, there exists a $y$, such that for every $z$, $p(x, y, z)$ is true."

Or, alternatively,

"No matter what $x$ I pick, I can always find a $y$ that will make $p(x, y, z)$ true for all values of $z$."

For the right-hand side:

"For every $x$, and every $z$, there exists a $y$, such that $p(x, y, z) is true."

Or:

"No matter what $x$ and $z$ I pick, I can always find a $y$ to make $p(x, y, z)$ true."

Can you see the difference?

To prove that they're not the same, you need to find a case where one side holds but the other doesn't - and the left side is more restrictive than the right (because the right side allows for you to pick a different $y$ for each value of $z$, whereas the left side says that there's a single $y$ that makes the statement true regardless of $z$).

If I remove $x$ from the statements, I could use something like this to show the difference:

$q(y, z) = (y = z + 1)$, i.e. my statement $q$ is that "$y$ is one more than $z$". So $\forall z \exists y q(y, z)$ means "For every $z$, there exists a $y$ such that $q$ is true" which makes sense - if you pick $z$, I pick the $y$ that's one more than it. On the other hand, $\exists y \forall z q(y, z)$ means "There exists a $y$ such that $q$ is true for all $z$", i.e. there's a magical number that is always one more than every number in existence, which is clearly untrue.

Answer 4

First, let me point out that the order of quantifier can really change the meaning of statements.

Consider: $\forall x \exists y \ x<y$ is true for the natural numbers, since for every every number you can find a greater number.

However, $\exists y \forall x \ x<y$ is false, since it is not true that there is a number greater than all numbers.

To demonstrate the non-equivalence of your two statements, consider as a domain the integers, and interpret $p(x,y,z)$ as $x+y=z$

Then the left claim says: "for all integers $x$ there is some integer $y$ such that for all integers $z$ it holds that $x+y=z$ .... which is false, since for whatever $x$ and $y$ you have, you can point to $z=x+y+1$ to show that $x+y=z$ does not hold.

The right claim says: "for all integers $x$ and $z$ there is some integer $y$ such that $x+y=z$ ... which is true, since for $y$ you can just pick $z-x$

Answer 5

Since all you've done is reorder the quantifiers, let's simplify the situation by reducing the number of variables and quantifiers so the reason is obvious.

Let $X$ be the set of all people, let $Y$ be the set of all mothers, and let the propositional function $P(x,y)$ be the statement "$y$ gave birth to $x$." Now, are the following two statements logically equivalent?

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

The first statement says "For every person $x$, there is at least one mother $y$ such that $y$ gave birth to $x$." In other words, it says "Every person was born to at least one mother."

The second statement says "There is at least one mother $y$ such that, for every person $x$, $y$ gave birth to $x$." In other words, it says "There is at least one mother that has given birth to all people."

No, they are certainly not equivalent! Reordering the quantifiers of a statement changes the meaning of the statement.