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$?
Can the order of adjacent and same quantifiers be mixed
discrete mathematicsfirst-order-logiclogicpredicate-logic
Related Solutions
You shouldn't really think of "three quantifiers" as a separate case from "two quantifiers". Think of it one quantifier at a time.
$\exists x \varphi(x)$ means that there is some $x$ that makes $\varphi(x)$ true.
$\forall y \exists x \varphi(x,y)$ means that no matter which $y$ you pick, $\exists x\varphi(x,y)$ is true; so no matter which $y$ you pick, there is some $x$ that makes $\varphi(x,y)$ true.
$\exists z\forall y\exists x\varphi(x,y,z)$ means that there is some particular $z$ so that the statement $\forall y\exists x\varphi(x,y,z)$ is true. So there is some particular $z$ so that no matter which $y$ you pick, there is some $x$ that makes $\varphi(x,y,z)$ true.
You can tell what depends on other things based on the order: in this last example, $y$ depends on nothing, but the choice of $x$ may depend on both $y$ and $z$. As a general rule, variables bound by $\forall$ quantifiers don't depend on anything, because they aren't being "chosen" (you're talking about all possibilities for them). Variables bound by $\exists$ quantifiers depend on all variables that preceded them.
I like to think of heavily-quantified statements as games, played between me and an opponent. I'm trying to make my statement true, while my opponent is trying to make it false. Whenever we see an $\exists$ quantifier, I get to pick the value of the variable; whenever we see an $\forall$, my opponent gets to pick. The statement is true if I have a winning strategy - that is, if there's a way for me to win no matter how my opponent plays.
For example, say we're looking at the sentence $\forall x\exists y\forall z(z \leq x \vee y \leq z)$, and all quantifiers are over the set of natural numbers $\mathbb{N}$. This statement is true, and here's why: first, my opponent gets to pick $x$. Whatever $x$ he picked, I'll choose $y = x + 1$. Now, no matter which $z$ he picks, $z$ will be either at most $x$ or at least $x + 1$ (because there aren't any numbers between $x$ and $x + 1$). Because I can always win this way, the original statement is true. And because we saw why this is a winning strategy, you can also see what the original statement was "really" saying: "for every $x$, there is a $y$ so that nothing is bigger than $x$ but smaller than $y$"; or, put more succinctly, "every number has a next number".
In principle, we could make up arbitrarily many distinct quantifiers. $\forall x\colon \phi(x)$ and $\exists x\colon \phi(x)$ make certain statements about the class $C:=\{\,x\mid \phi(x)\,\}$: One says that $C$ is the all-class (or that its complement is empty), the other says that $C$ is not empty. And $\exists!$ say that $C$ is a singleton. We could introduce quantifiers for quite arbitrary statements about $C$, but the most natural would perhaps be about cardinality of $C$: Stating that $C$ or its complement has at least $n$, at most $n$, more than $n$, less than $n$, or exactly $n$ elements for a fixed finite or infinitie cardinality $n$ come to mind. Of these, those with finite cardinalities are readily constructed from $\exists$ and $\forall$ (just like we do with $\exists!$).
However, any quantifiers about infinite cardinalities are problematic in a first order theory (i.e., when we can only "speak" about the objects of our universe, but not about sets of objects of our universe): There are no suitable rules of inference accompanying them. A proof of $\exists x,\phi(x)$ can consist of constructing a sing $a$ with $\phi(a)$. What should a proof of $\exists^\infty x,\phi(x)$ with $\exists^\infty$ intended to mean "there are infinitely many" look like? By exhibiting infinitely many $a_n$ with $\phi(a_n)$? You cannot do that in a first-order theory per se.
Nevertheless, outside first order formalism, some such quantifiers are very common: A very useful one is "almost all" which in the context of natural numbers is understood to mean "all but finitely many". "Almost all" $n$ have property $\phi$ is then a shortcut for $\exists n_0\in\Bbb N\colon \forall n\in \Bbb N\colon n>n_0\to \phi(n)$, a construct very common in the introduction of limits. Note how the very properties of the set of natural numbers allow us to express "all but finitely many". (In other contexts, such as measure theory, we use "almost all" with a different meaning, namely "up to a set of measure $0$")
Related Question
- Order of quantifiers and the intepretation of a sequence $(a_n)$.
- Logical propositions and predicates “quantifiers”
- Augmenting FOL with user-defined quantifiers, can we define the uniqueness quantifier
- Is there a scenario for when changing the order of different quantifiers in a nested quantifier retain the original meaning
Best Answer
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.