Can the order of adjacent and same quantifiers be mixed?

Question

So can we mix say $\forall x \forall y$ to $\forall y \forall x$ or $\exists y \exists x$ to $\exists x \exists y$ for any possible predicate? And in general, could you mix the order of quantifiers up to a differing quantifier, so $\forall x \exists y \exists z$ could be changed to $\forall x \exists z \exists y$?

Answer 1

Yes, quantifiers of the same type are commutative:

$$\forall u \forall v \phi \equiv \forall v \forall u \phi \text{ and }\exists u \exists v \phi \equiv \exists v \exists u \phi$$

for all variables $u, v$ and formulas $\phi$.

If two subformulas are logically equivalent, so are all formulas they occur in, so $\forall x \exists y \exists z \phi \equiv \forall x \exists z \exists y \phi$ also.

However, $\forall$ and $\exists$ are not commutative with each other: $$\exists v \forall u \phi \vDash \forall u \exists v \phi$$ but $$\forall u \exists v \phi \not \vDash \exists v \forall u \phi$$ i.e., whenever $\exists v \forall u \phi$ is true so is $\forall u \exists v \phi$, but not vice versa.

---

The proof comes down to the fact the variable assignments and quantification over them can be swapped on the meta level:

First observe that for a variable assignment $v$ and two objects $a, b$, $$v'' = v[x \mapsto a][y \mapsto b] = v[y \mapsto b][x \mapsto a] = v'$$ -- for two distinct variables $x$ and $y$, it doesn't matter in which order we compute the assignment modifications. Then:

$\newcommand{\A}{\mathfrak{A}} \begin{align*} & \A \models_v \forall x \forall y \phi\\ \iff & \text{for all $x$-variants $v'$ of $v$ : } \A \models_{v'} \forall y \phi\\ \iff & \text{for all $x$-variants $v'$ of $v$ and all $y$-variants $v''$ of $v'$: } \A \models_{v''} \phi\\ \iff & \text{for all $y$-variants $v''$ of $v'$ and all $x$-variants $v'$ of $v$: } \A \models_{v'} \phi\\ \iff & \text{for all $y$-variants $v''$ of $v'$ : } \A \models_{v''} \forall x \phi\\ \iff & \A \models_v \forall y \forall x \phi \end{align*}$

The middle step is justified because we can swap the two "all"s in the meta language (English) -- becaue that's just how the meaning of "all" works.

Analogous for the commutativity of existence.