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?
Best Answer
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)$