Appearance of other quantifiers in rules of conversion to prenex normal form.

Question

Take the following conversion to prenex normal form rule (as described in the Wikipedia article):

$ \left (\forall x \phi \right )\wedge\psi $ is equivalent to $\forall x \left(\phi \wedge \psi \right)$, provided $x$ does not appear as a free variable in $\psi$.

My background is from reading through Velleman's How To Prove It and trying to prove statements involving quantifiers via "mechanical" equivalences and not via the more "textual" techniques explained in the book. Velleman in general is very light on the logic, presumably because he's trying to introduce the bare minimum required to be "eloquent" in proof reading and writing, and not what would be necessary to understand what a proof is and how it works at a more fundamental and theoretical level, but I digress.

The question is, in the rule above, can the $\psi$ formula contain other quantifiers, as long as it does not contain $x$ as a free variable? For example, suppose $\mathcal{F}$ and $\mathcal{G}$ are families of sets. Can

$$\forall y \left[\forall A \left(A\notin\mathcal{F} \vee y \notin A \right) \wedge \exists B \left( B\in\mathcal{G}\wedge y \in B \right) \right]$$

be replaced with

$$\forall y \forall A \left[\left(A \notin \mathcal{F} \vee y \notin A \right) \wedge \exists B \left( B\in\mathcal{G}\wedge y \in B \right) \right]$$

if we let $\exists B \left( B\in\mathcal{G}\wedge y \in B \right)$ take the role of $\psi$ and $A$ take the role of $x$, noting that $A$ does not appear as a free variable in the former?

My intuition says no, since then through a couple of additional manipulations we could conclude that the following formulas are also equivalent:

$$\forall y \forall A \exists B \left[\left(A\notin\mathcal{F} \vee y \notin A \right) \wedge \left( B\in\mathcal{G}\wedge y \in B \right) \right]$$

$$\forall y \exists B \forall A \left[\left(A\notin\mathcal{F} \vee y \notin A \right) \wedge \left( B\in\mathcal{G}\wedge y \in B \right) \right]$$

So this would imply that the order of $\forall A$ and $\exists B$ does not matter, which doesn't sound right, but I'd like to get a more grounded answer.

Answer 1

In general, we have :

$\forall x\varphi(x) \land \psi \equiv \forall x(\varphi(x) \land \psi) \, \,$, provided that $x$ is not free in $\psi$;

but also :

$\sigma \land \exists y \chi(y) \equiv \exists y (\sigma \land \chi(y)) \, \,$, provided that $y$ is not free in $\sigma$.

THus, we can "Add" the two cases having :

$\forall x\varphi(x) \land \exists y \chi(y) \equiv \forall x \exists y (\varphi(x) \land \chi(y))$.

Your concern - it seems to me - is : may I "switch" the quantifiers ? In general no, but in this case yes, because the quantified variables are "separated".

Consider the simple example :

$\forall x(x \ge 0) \land \exists y (y=0)$

According to the above rules, it is equivalent to :

$\forall x \exists y [(x \ge 0) \land (y=0)]$;

we can easily check that, for any $n \in \mathbb N$, it is enough to choose $0$ as value for $y$ and we have that :

$n \ge 0 \land 0=0$

is satisfied in $\mathbb N$.

But the same holds for : $\exists y \forall x [(x \ge 0) \land (y=0)]$; in order to satisfy it, it is enough to choose $0$ for $y$, and the formula will be satisfied for any $n \in \mathbb N$.