Does universal quantification order matter?

Question

For example if I have $$\forall a \in A \forall b_2 \in B \forall b_1 \in B((a,b_1)\notin R \lor (b_1, b_2)\notin R)$$ is is the same as

$$\forall b_2 \in B \forall b_1 \in B \forall a \in A ((a,b_1)\notin R \lor (b_1, b_2)\notin R)$$

and other variations thereof? Is this true in general? I ask because I think it is the same thing since there is not a "dependency" between these 3 variables but I might be wrong.

Answer 1

Universal quantifiers if not separated by other types of quantifiers (existential for example) are interchangeble IF they do not depend on each other.

Example where the exchange is possible: $$\forall a \in A,\, \forall b \in B : p(a,b) = T$$ $$\forall b \in B,\, \forall a \in A : p(a,b) = T$$

Example where the exchange cannot be performed:

$$\forall a \in A,\, \forall b \in (B \setminus \{a\}) : p(a,b) = T$$

in the second example you can observe that the second universal quantifier depends on the first since the set $(B \setminus \{a\})$ does not contain the element chosen by the first universal quantifier.

indeed like you said in your proposition the universal quantifiers are all togheter and they are independent so you can swap them the way you like.

Answer 2

Yes, you can permute universal quantifiers. You can also permute existential quantifiers - "$\exists x\exists y\varphi(x, y)$" is equivalent to "$\exists y\exists x\varphi(x, y)$".

You cannot, however, swap different types of quantifiers: e.g. "$\forall x\exists y(x<y)$" and "$\exists y\forall x(x<y)$" mean very different things!

EDIT: Another thing you can't do is swap similar quantifiers across a different kind of quantifier: "$\forall x\exists y\forall z(p(x, y, z))$" is not the same as "$\forall z\exists y\forall x(p(x, y, z))$". (For example, take $p(x, y, z)$ to be the formula "$y>x$ and not ($y>z>x$);" only one of the sentences above is true in the integers with the usual ordering!)

Answer 3

Yes, universal quantification expressions are always equivalent for whichever order you chose for the quantifiers.

To see why this is true, consider the interpretation of a sentence $\forall a\in A \forall b\in B f(a,b)$. This is true iff $\forall b\in B f(a,b)$ is true for whichever $a$, which in turn is true iff $f(a,b)$ is true for whichever $a$ and $b$. Going the other way, we realize that then $\forall b\in B \forall a \in A f(a,b)$ is true iff $\forall a\in A \forall b\in B f(a,b)$ is true.