Is $\forall x\,\exists y\, Q(x, y)$ the same as $\exists y\,\forall x\,Q(x, y)$?

Certainly not. In that useful "loglish" dialect (a halfway house between the formal language and natural English), the first says

For any $x$, there is a $y$ such that $Qxy$.

The second says

For some $y$, all $x$ are such that $Qxy$.

These are quite different. Compare

For any natural number $x$, there is some number $y$, such that $x < y$. True (for any number, there's a bigger one).

For some natural number $y$, any number $x$ we take is such that $x < y$. False (there is no number larger than all numbers!).

A more general comment. The whole point of the quantifier-variable notation is to enforce clarity as to the relative scope of logical operators.

To take a simple case, consider the English "Everyone's not yet arrived". This is structurally ambiguous. You can easily imagine contexts where the natural reading is "It isn't the case that everyone has arrived", and other contexts where the natural reading is "Not everyone has arrived". Compare, however,

$\neg\forall xAx$

$\forall x\neg Ax$

Here, in the language of first-order logic, the order of the logical operators ensures that each sentence has a unique parsing, and there is no possibility of structural ambiguity.


Switching the order of quantifiers is often not valid. In particular, we change the meaning of a statement when we switch the order of different quantifiers whose scope is the entire statement - as in this case - and it is usually not valid to switch a leading quantifier with a nested one.

In this case, we have:

$$\forall x \exists yQ(x, y) \not\equiv \exists y \forall x Q(x, y)$$

For example:

Let $Q(x, y)$ means "x loves y". Domain of $x, y$ : people

  • The left hand side would read, effectively:

    $\forall x \exists y Q(x, y)$: "Everyone loves somebody" (every person loves somebody);

  • The right-hand side would read, effectively:

    $\exists y \forall x Q(x, y)$: "There is someone whom everyone loves." Or alternatively, "there is someone who is loved by everyone."

Those are not at all equivalent statements.


Because I really hate the real world analogies (after an exam I was forced to read nearly 300 answers mumbling "every pot has a lid" analogies), let me give you a mathematical way of understanding this without evaluating the actual formulas.

Let $M$ be an arbitrary structure for our language, let $A(x)=\{y\in M\mid M\models Q(x,y)\}$. So given a point $m\in M$ we match it the set $A(m)$ of all those which are satisfying $Q$ with $m$.

  1. The first sentence $\forall x\exists yQ(x,y)$ tells us that for every $m\in M$, $A(m)$ is non-empty.

  2. The second sentence $\exists y\forall xQ(x,y)$ tells us that there is some $y$ such that $y\in A(m)$ for all $m$. That is to say that the intersection of all $A(m)$ is not empty.

We can immediately draw the conclusion that the second sentence implies the first. If the intersection of all the $A(m)$'s non-empty then certainly no $A(m)$ can be empty.

On the other hand it is also quite clear that the second sentence implies that the intersection of all the $A(m)$'s is not empty, they all contain at least one shared point. The first sentence makes no such requirement, so it's not difficult to construct a structure where the first sentence is true but the second is false.


The answer is no.

Here's the way I like to think about it myself: $\forall x \exists y Qxy$ allows for a different $y$ for each $x$, but $\exists y \forall x Qxy$ requires the same $y$ work for all $x$.

Sometimes people get confused due to this construction: "There exists a $y$ for all $x$ such that $Q(x, y)$ holds." The placing of the "such that" is critically important.


Besides to @Asaf's and @amWhy's detailed answer, I am noting an example, maybe, it paves just a small piece of the way. Consider $M=\mathbb Z$ and $$Q(x,y): x+y=0$$ Obviously, for all $x\in\mathbb Z$, there is a $y\in\mathbb Z$ such that $Q(x,y)$ be a true statement. Now, think about this sentence: There is an $y\in\mathbb Z$ such that for all integers $x$, $x=-y$. Clearly, it is wrong. Because if for example $y=a$ then we can't write $-a=x$ when $x$ is freely moving alongside the set $\mathbb Z$. So, your claim is not true in general.