Swapping quantifiers

Question

In his book "Analysis 1", Terence Tao writes:

Swapping two “for all” quantifiers is harmless: a statement such as

"For all real numbers a, and for all real numbers b, we have (a+b)^2 = a^2+2ab+b^2"

is logically equivalent to the statement

"For all real numbers b, and for all real numbers a, we have (a+b)^2 = a^2+2ab+b^2"

(why? The reason has nothing to do with whether the identity (a+b)^2 = a^2+2ab+b^2 is actually true or not).

Concerning this kind of exercises I find it difficult to explain why this is true. What would be a correct solution to this exercise? For me it is clear, but I don't know how to prove it. Isn't it obvious?

Answer 1

You say it's obvious, and I think that's right; of course, the problem is how to prove it, as you say.

I think for this purpose it's best to think in terms of counterexamples.

Take the sentence "$\forall x\forall y(x+y$ is even$)$". Clearly this is false (in the integers), because there is a counterexample: for instance, "$x=3$, $y=1$."

Now consider the "swapped" version "$\forall y\forall x(x+y$ is even$)$". Then $y=1, x=3$ is a counterexample again - in fact, it's really the same counterexample!

My point is that any counterexample to $\forall x\forall y P(x, y)$ is also a counterexample to $\forall y\forall x P(x, y)$. Maybe for niceness you rearrange how you write it - e.g. you tell me the value of the first variable first, and the second variable second - but it's still really the same counterexample.

So what? Well, a universal sentence is true iff it has no counterexamples! So saying

"$\forall x\forall y P(x, y)$" and "$\forall y\forall x P(x, y)$" have the same counterexamples

is the same as saying

"$\forall x\forall y P(x, y)$" and "$\forall y\forall x P(x, y)$" are either both true (no counterexamples) or both false (some counterexample(s), which breaks each).

---

So how does this help you prove it?

Well, you're asking how to prove a basic fact about logic, which means we need to dig into the messy details of exactly how we axiomatize logic in the first place. There are many equivalent ways of doing this, so it's impossible to give a precise answer without first specifying a system, but in most of these the argument goes roughly as follows:

• Suppose for contradiction that $\forall x\forall y P(x, y)$ is true but $\forall y\forall x P(x, y)$ is false.

• Since $\forall y\forall x P(x, y)$ is false, there exists a counterexample: $y=a, x=b$.

• But then $x=b, y=a$ is a counterexample to $\forall x\forall y P(x, y)$, contradicting what we assumed earlier.

Answer 2

The proof is straight forward if, as usually the case in analysis, each quantifier is explicitly restricted to some set as follows:

$\forall a\in X: \forall b \in Y: R(a,b)$

or equivalently...

1. $\forall a:[a\in X \implies \forall b: [b\in Y \implies R(a,b)]]$

2. Suppose $p\in Y$.

3. Suppose further that $q\in X$.

4. From (1), (2) and (3), we have $R(q,p)$

5. From (3), we conclude $\forall a: [a\in X \implies R(a,p)]]$

6. From (2), we conclude $\forall b:[b\in Y \implies \forall a: [a\in X \implies R(a,b)]]$

or equivalently...

$\forall b\in Y: \forall a \in X: R(a,b)$ as required.