# Can we move quantifiers to the left in predicate logic?

Say I have part of a query in the form: ∃xa(...)∧∃xb(...)∧∃xc(...), where a, b, and c are attributes and the ellipses can be anything (I'm looking for a general rule). Is this equivalent to saying ∃xa,xb,xc(...∧...∧...) - i.e. compacting all the existential quantifiers into one and 'anding' their domains together?

For example, if I have the query:

would it be correct (albeit unwieldy) to write it as:

{ xpid | ∃xpname,xcolor,xsid,xsname,xaddress,xcost,ysid,ysname,yaddress,ycost( PARTS(xpid,xpname,xcolor) ∧ SUPPLIERS(xsid,xsname,xaddress... (and then the rest of the query)

• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. Commented Apr 9, 2014 at 9:57
• Please don't crosspost on different SE sites simultaneously! Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration or repost. It may be prudent to include links in either direction and explain why the particular perspective of the other site seems useful. Commented Apr 9, 2014 at 11:43

If all the quantified variables are distinct, then you can safely move all quantifiers to the left. This is the only obstruction to this procedure. You can always ensure that all quantified variables are distinct by renaming them. For example, starting with $$(\forall x P(x)) \lor (\forall x Q(x)),$$ we first rename the second variable to $y$, $$(\forall x P(x)) \lor (\forall y Q(y)),$$ and then move the quantifiers to the left, $$\forall x \forall y (P(x) \lor Q(y)).$$ This is equivalent to the original formula.