When can I move a quantifier outside the scope of another quantifier? S

Question

I've been working on some problems on paraphrasing statements with quantificational notation and polyadic predicates, and I'm a little confused as to when I can move a quantifier that's inside the scope of another quantifier.

For example, I've reached the point where I've paraphrased something as this: $$\forall x (Sx \rightarrow \exists y(Ly \land Qxy)) $$

Is it valid to re-write the above as this: $$\forall x \exists y(Sx \rightarrow (Ly \land Qxy)) $$

It seems like this is fine, since the $y$ is independent of the $Sx$ that is the antecedent of the scope of the universal quantifer.

If I can indeed move the quantifiers as above, what are some general rules for moving the existential quantifier outside the scope of the universal quantifier and vice versa?

Answer 1

Yes, the first move you made does preserve equivalence, and here are some basic rules for pulling a quantifier outside logical operators, where P does not contain any free variables x:

$P \lor \forall x \: \phi(x) \equiv \forall x (P \lor \phi(x))$

$P \lor \exists x \: \phi(x) \equiv \exists x (P \lor \phi(x))$

$P \land \forall x \: \phi(x) \equiv \forall x (P \land \phi(x))$

$P \land \exists x \: \phi(x) \equiv \exists x (P \land \phi(x))$

$P \rightarrow \forall x \: \phi(x) \equiv \forall x (P \rightarrow \phi(x))$

$P \rightarrow \exists x \: \phi(x) \equiv \exists x (P \rightarrow \phi(x))$

$\forall x \: \phi(x) \rightarrow P \equiv \exists x (\phi(x) \rightarrow P)$

$\exists x \: \phi(x) \rightarrow P \equiv \forall x (\phi(x) \rightarrow P)$

So take care of those last two: the quantifier changes if you pull it outside a conditional, and it is the antecedent of that conditional!

And because of the latter, there is no simple equivalence involving puling a quantifier outside a biconditional.

Also, you can move a universal over another universal (and same for existentials), but you can't move a universal over an existential or vice versa. That is:

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

and

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

But not:

$\forall x \exists y P(x,y) \equiv \exists y \forall x P(x,y)$