Quantifier Positioning

Question

How does the positioning of a quantifier affect the meaning of the statement? For example, what is the difference between $\forall x : \forall y : (P(x) \land P(y))$ and $(\forall x: P(x)) \land (\forall y :P(y))$?

Answer 1

You have to be really careful in moving quantifiers: under certain circumstances you can move them without changing the meaning of the sentence, but under other circumstances it does change the meaning.

Here are a number of equivalences that do hold:

Swapping Quantifiers of the Same Type That Are Next to Each Other

$\forall x \forall y \ P(x,y) \Leftrightarrow \forall y \forall x \ P(x,y)$

$\exists x \exists y \ P(x,y) \Leftrightarrow \exists y \exists x \ P(x,y)$

Distribution Universal over Conjunction, and Existential over Disjunction

$\forall x (P(x) \land Q(x)) \Leftrightarrow \forall x \ P(x) \land \forall x \ Q(x)$

$\exists x (P(x) \lor Q(x)) \Leftrightarrow \exists x \ P(x) \lor \exists x \ Q(x)$

Prenex Laws

Where $\varphi$ is any formula and where $x$ is not a free variable in $\psi$:

$ \forall x \ \varphi \land \psi \Leftrightarrow \forall x (\varphi \land \psi)$

$ \psi \land \forall x \ \varphi \Leftrightarrow \forall x (\psi \land \varphi)$

$ \exists x \ \varphi \land \psi \Leftrightarrow \exists x (\varphi \land \psi)$

$ \psi \land \exists x \ \varphi \Leftrightarrow \exists x (\psi \land \varphi)$

$ \forall x \ \varphi \lor \psi \Leftrightarrow \forall x (\varphi \lor \psi)$

$ \psi \lor \forall x \ \varphi \Leftrightarrow \forall x (\psi \lor \varphi)$

$ \exists x \ \varphi \lor \psi \Leftrightarrow \exists x (\varphi \lor \psi)$

$ \psi \lor \exists x \ \varphi \Leftrightarrow \exists x (\psi \lor \varphi)$

Notice that the equivalence you are asking about is the application of the first two Prenex Laws:

$ \forall x \ \forall y (P(x) \land P(y)) \Leftrightarrow$

$ \forall x (P(x) \land \forall y \ P(y)) \Leftrightarrow$

$ \forall x \ P(x) \land \forall y \ P(y)$

OK ... but here are some non-equivalences:

Swapping Quantifiers of the Different Type That Are Next to Each Other

$\forall x \exists y \ P(x,y) \not \Leftrightarrow \exists y \forall x \ P(x,y)$

Distribution Universal over Disjunction, and Existential over Conjunction

$\forall x (P(x) \lor Q(x)) \not \Leftrightarrow \forall x \ P(x) \lor \forall x \ Q(x)$

$\exists x (P(x) \land Q(x)) \not \Leftrightarrow \exists x \ P(x) \land \exists x \ Q(x)$

Finally, here are some that do hold, and some that don't:

Prenex Laws for Conditionals

Where $\varphi$ is any formula and where $x$ is not a free variable in $\psi$:

$ \forall x \ \varphi \to \psi \not \Leftrightarrow \forall x (\varphi \to \psi)$ (No!)

$ \psi \to \forall x \ \varphi \Leftrightarrow \forall x (\psi \to \varphi)$ (Yes!)

$ \exists x \ \varphi \to \psi \not \Leftrightarrow \exists x (\varphi \to \psi)$ (No!)

$ \psi \to \exists x \ \varphi \Leftrightarrow \exists x (\psi \to \varphi)$ (Yes!)

$ \forall x \ \varphi \leftrightarrow \psi \not \Leftrightarrow \forall x (\varphi \leftrightarrow \psi)$ (No!)

$ \psi \leftrightarrow \forall x \ \varphi \not \Leftrightarrow \forall x (\psi \leftrightarrow \varphi)$ (No!)

$ \exists x \ \varphi \leftrightarrow \psi \not \Leftrightarrow \exists x (\varphi \leftrightarrow \psi)$ (No!)

$ \psi \leftrightarrow \exists x \ \varphi \not \Leftrightarrow \exists x (\psi \leftrightarrow \varphi)$ (No!)

Answer 2

In general, moving two formulas that differ only by the position of quantifiers are unrelated, much like formulas that differ only by placement of negation are unrelated.

However, there are some properties of quantifiers that we can exploit in order to prove to ourselves the equivalence of the two statements given above in classical first order logic. I say prove to ourselves because this kind argument is meant to give intuition not to convince a skeptic.

Premise.

$$ (\forall x . P(x)) \land (\forall y. P(y)) \tag{101} $$ Eliminate disjunction (which is invertible)

$$ \forall x . P(x) \;\;\text{and}\;\; \forall y . P(y) \tag{102} $$

Quantify over an unused variable in left statement (invertible).

$$ \forall x . \forall y . P(x) \;\;\text{and}\;\; \forall y . P(y) \tag{103} $$

Quantify over an unused variable in right statement (invertible).

$$ \forall x. \forall y. P(x) \;\;\text{and}\;\; \forall x. \forall y. P(y) \tag{104} $$

Add back $\land$ .

$$ (\forall x . \forall y. P(x)) \land (\forall x. \forall y. P(y)) \tag{105} $$

$\forall$ and $\land$ commute when the $\forall$s range over identical variables.

$$ \forall x. \forall y. P(x) \land P(y) \tag{106} $$