Does order of qualifiers matter in FOL formula?

Question

In preparing for an exam, I'm working through old exam questions and am now trying to figure out if the following first-order formula is valid. FYI, $m$ is a binary predicate.

$$(\forall x \,\exists y: m(x,y)) \implies (\exists y \, \forall x: m(x,y))$$

If I were to turn the original formula into English, I would say: "IF for all $x$ and some $y$, $m(x,y)$ is true, THEN for all $x$ and some $y$, $m(x,y)$ is true." This seems trivially true and I'm wondering if the order of the qualifiers matters and I'm reading the formula incorrectly?

Digging deeper, I reduced the given formula to this:

$$(\exists x\, \forall y: m(x,y)) \vee (\exists y \, \forall x: m(x,y))$$

In English this is: "For all $y$ and some $x$, $m(x,y)$ is true" OR "For all $x$ and some $y$, $m(x,y)$ is true." Which seems valid to me, though it would helpful to know the actual predicate formula of $m(x,y)$. It also seems to be making a somewhat different statement than the original formula so either I've interpreted the original formula incorrectly, I've reduced it to this one incorrectly, or I'm interpreting this one incorrectly.

Can anyone shed some light if I have the right thought process? Thank so much for the help!

Answer 1

The order of quantifiers is crucial to the meaning of a statement.

For example, let us look at the natural numbers. We have the following statement:

$$\forall x \in \mathbb{N}: \exists y \in \mathbb{N}: y = x+1$$

Here, $p(x,y)$ means that $y = x+1$. This simply says that if $x$ is a natural number (for example $6$), there exists another natural number $y$ such that $y = x+1$. In this case, $7 = 6 + 1$ is such a natural number.

However, let us change the order of the quantifiers for a moment:

$$\exists y\in \mathbb{N}: \forall x\in \mathbb{N}: y = x + 1$$

Translated into everyday language, this statement means: There exists a natural number $y$ such that for all natural numbers $x$, the equation $y = x+1$ holds. You can see quickly that this statement is complete nonsense. If you take $x = y$, then the equation $y = x + 1$ would imply $0 = 1$, which is wrong.

Be careful when translating the logical statements into everyday language. $$\forall x \, \exists y$$

should not be translated as "for all $x$ and some $y$", because the order of the quantifiers allows $y$ to depend on $x$. Your original translation implies $y$ to be completely independent of $x$.

If you want to say "for all $x$ something is true and for some $y$ something is true", you'll have to use the $\wedge$ (and) sign, e.g.

$$(\forall x: A(x)) \wedge (\exists y: B(y)).$$