$\forall x P(x) \land \exists x Q(x) \equiv \forall x \exists y (P(x) \land Q(y))$

Question

I'm trying to learn first-order logic. Why are these formulas equivalent? I understand the first formula, but the second I can't understand. I'm saying: for all elements of a set, they have the $P$ property and one (or more) has the $Q$ property?

Answer 1

Before diving into a proof of equivalence, let's develop intuition a bit.

First note that bound variables can be renamed. Rewriting the left-hand side as

$$ \forall x P(x) \wedge \exists y Q(y) $$

brings it a little closer to the right-hand side. In general, $\exists y (P \wedge Q)$ is a stronger claim than $\exists y P \wedge \exists y Q$ because in the former the same $y$ must work for both $P$ and $Q$. However, when $P$ does not contain $y$, which is what we mean when we write $P(x)$ in $\forall x \exists y (P(x) \wedge Q(y))$, then the choice of $y$ is indifferent to the satisfaction of $P(x)$.

By the same argument, the choice of $x$ has no bearing on the satisfaction of $Q(y)$. Hence for the satisfaction of $\forall x \exists y (P(x) \wedge Q(y))$, $P(x)$ must hold for all $x$ and $Q(y)$ must hold for some $y$: just like for the left-hand side.

---

For a formal proof, you need to fix a proof system. With a semantic tableau approach, for example, an abridged proof may look like the following.

We first separate the equivalence into two implications and prove that

$$ \forall x P(x) \wedge \exists y Q(y) ~~\text{ implies }~~ \forall u \exists v (P(u) \wedge Q(v)) \enspace, $$

leaving the other half of the proof to the interested reader. (Note the bound variable renaming to avoid confusion.)

We discharge our proof obligation by showing that

$$ \forall x P(x) \wedge \exists y Q(y) \wedge \neg\forall u \exists v (P(u) \wedge Q(v)) ~~~~~~~~~(*)$$

is unsatisfiable. By instantiating $y$ and $u$ with constants $a$ and $b$, respectively, we quickly find that if $(*)$ is satisfiable, so is

$$ P(b) \wedge Q(a) \wedge \neg(P(b) \wedge Q(a)) \enspace. $$

Since the latter is clearly unsatisfiable, we have proved the implication.

---

Finally, note that the right-hand side is in prenex normal form; that is, all quantifiers have been pulled up front. The right-hand side can be derived from the left-hand side by a sequence of equivalence-preserving transformations designed to produce a formula in prenex normal form. You only need to prove the correctness of those transformations once.

It is also interesting to note that there is a "better" prenex normal form formula equivalent to the left-hand side formula, namely

$$\exists y \forall x (P(x) \wedge Q(y)) \enspace. $$

Intuitively, it stresses the independence of $y$ from the choice of $x$.