Understanding Quantifier Order

The Same Condition, a Different Requirement

In Multiple Quantifiers, we read nested statements from the outside inward and matched each quantifier with its requirement: an arbitrary input for a universal quantifier, a verified witness for an existential one. We now examine why the order of those requirements matters.

The previous tutorial established

For each real \(x\), the choice \(y=-x\) works. Now move the existential quantifier before the universal quantifier, keeping the variables, domains, and final condition unchanged:

This says that one real number \(y\) has sum zero with every real number \(x\). It is false. For any proposed \(y\), choose \(x=1-y\); then \(x+y=1\neq0\). The arithmetic condition has not changed, but the requirement on the witness has.

Dependence: What May a Witness Use?

Let \(D,E\) be fixed domains, and let \(A(x,y)\) be a condition defined for \(x\in D\) and \(y\in E\). Compare

In the first statement, \(x\) is fixed before the inner existence claim is considered. A successful choice of \(y\) may depend on \(x\). In the second statement, one \(y\) must satisfy the complete universal condition. It must work independently of which \(x\in D\) is considered.

For example, both \(\forall x\in\mathbb R,\ \exists y\in\mathbb R,\ xy=0\) and \(\exists y\in\mathbb R,\ \forall x\in\mathbb R,\ xy=0\) are true. In both cases, \(y=0\) works because \(x\cdot0=0\) for every real \(x\). Thus switching mixed quantifiers does not always change the truth value. The point is that it does not preserve truth in general.

Quantifiers of the Same Kind Can Commute

Before examining mixed orders further, consider two adjacent universal quantifiers or two adjacent existential quantifiers. For fixed domains, their order can be reversed without changing the meaning.

Proof for universal quantifiers. First suppose both domains are nonempty. Assume the statement with \(x\) first. Let \(y\in E\) be arbitrary, and then let \(x\in D\) be arbitrary. The assumed statement applies to this \(x\) and this \(y\), so \(A(x,y)\) holds. This proves the statement with \(y\) first.

Conversely, assume the statement with \(y\) first. For arbitrary \(x\in D\) and arbitrary \(y\in E\), apply that statement first to \(y\) and then to \(x\). It gives \(A(x,y)\), proving the statement with \(x\) first. If either domain is empty, both orders are true by vacuous truth: either the outer universal domain is empty, or every inner universal statement has an empty domain.

Proof for existential quantifiers. Assume the statement with \(x\) first. There is an \(x_0\in D\) and, for that value, a \(y_0\in E\) such that \(A(x_0,y_0)\). Choose \(y_0\) as the outer witness in the reversed statement and \(x_0\) as its inner witness. The same condition holds.

Conversely, witnesses \(y_0\in E\) and \(x_0\in D\) for the reversed statement can be used in the original order: choose \(x_0\), then \(y_0\). If either domain is empty, neither order can supply both witnesses, so both statements are false. This proves the two equivalences.

For example, \(\forall x\in\mathbb R,\ \forall y\in\mathbb R,\ x+y=y+x\) is equivalent to the same condition with the two universal quantifiers reversed. No symmetry assumption about a general condition \(A\) is needed for commutation: both orders test exactly the same allowed pairs.

Mixed Orders: A One-Way Implication

Proof. Suppose the premise holds. Then there is a \(y_0\in E\) such that \(A(x,y_0)\) holds for every \(x\in D\). If \(D\) is nonempty, let \(x\in D\) be arbitrary. Using \(y=y_0\) supplies an allowed witness for the inner existential claim. Since this works for arbitrary \(x\), the conclusion follows. If \(D\) is empty, the conclusion is true by vacuous truth.

This proves the implication whenever the premise is true. If \(E\) is empty, the premise is false, so the implication still holds. Finally, the additive-inverse example at the start gives a true \(\forall x\,\exists y\) statement and a false \(\exists y\,\forall x\) statement. It therefore disproves the reverse implication in general.

In this precise sense, \(\exists y\,\forall x\) is the stronger requirement: a common witness provides a witness for each individual input, but separate witnesses need not yield a common one.

Seeing the Difference on a Finite Domain

For finite nonempty domains, list the truth values of \(A(x,y)\) in a table with one row for each \(x\) and one column for each \(y\). Then \(\forall x\,\exists y\) requires a true entry in every row, whereas \(\exists y\,\forall x\) requires a column whose entries are all true.

Empty domains still require the layer-by-layer reading from the previous tutorial. In particular, if \(D=E=\varnothing\), then \(\forall x\in D,\ \exists y\in E,\ A(x,y)\) is true, but \(\exists y\in E,\ \forall x\in D,\ A(x,y)\) is false. With no outer inputs, the first statement does not require any witness at all.

Tracking Order Through Three Quantifiers

The same dependence issue appears inside longer statements. Compare the following three formulas over \(\mathbb R\):

Statement (I) is true by the argument in the previous tutorial: after arbitrary real \(x,y\) are fixed, choose \(z=x+y\).

Statement (II) is false. Take the outer input \(x=0\). If a real \(z\) worked for every real \(y\), using \(y=0\) would give \(z=0\), while using \(y=1\) would give \(z=1\). No real \(z\) satisfies both requirements.

Statement (III) is also false. A common \(z\) would have to equal \(0\) for \(x=0,y=0\), and equal \(1\) for \(x=0,y=1\). Again, this is impossible.

Negation Preserves the Order of Variables

Changing quantifier order and negating a statement are different operations. By the Negation of Nested Quantifiers theorem from the previous tutorial,

The first negation requires one input \(x\) for which all witnesses fail. The second allows a counterexample \(x\) to be chosen separately for each proposed common witness \(y\). This explains why the disproof of a common witness can use a choice such as \(x=1-y\): in that negated statement, \(y\) has already been fixed before \(x\) is chosen.

Quantifier order is therefore part of the mathematical content of a statement, not merely its notation. A correct equality or inequality at the end of an argument is insufficient if the witnesses used to obtain it depend on inputs that the statement requires them to handle uniformly.