# Is this equivalence true?

Is this equivalence true?

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

Here is what I did so far.

If the LHS is true, then there exists a x such that P(x) is true and a y such that Q(y) is true.

If the RHS is false, then there exists a x such that P(x) is false and a y such that Q(y) is false.

Thus both statements are equivalent.

-
You proved the same implication twice. You needed to assume RHS is true or that LHS is false. –  Asaf Karagila Dec 6 '12 at 7:55
The $\exists x$ on the RHS must be a typo. –  Dan Christensen Dec 6 '12 at 14:09
The $\exists x$ might well be a typo, but it might also be intentional --- a vacuous quantifier that doesn't affect the meaning of the formula, since $x$ doesn't occur in its scope. –  Andreas Blass Dec 6 '12 at 15:58
As it stands, it is syntactically incorrect. On the RHS, $x$ is quantified twice. –  Dan Christensen Dec 6 '12 at 18:26

Assuming the $\exists x$ on the RHS is a typo...

Let U be a non-empty domain of quantification.

$\exists x (x\in U)$

This approach makes the end-result more widely applicable. In mathematics, there may be multiple domains of quantification within a proof, even within a statement.

Then it is easy to prove:

$\forall x\in U (P(x)) \wedge \exists y (Q(y)) \leftrightarrow \forall x\in U \exists y (P(x) \wedge Q(y))$

Formal proof (using DC Proof 2.0): http://dcproof.com/Smiley.htm (commentary in blue)

-

Pay attention to when the universal quantifier ($\forall$) is used and when the existential quantifier ($\exists$) is used.

For the LHS to be true, P(x) has to be true for all x and Q(y) has to be true for some y. For the LHS to be false, P(x) has to be false for some x or Q(y) has to be false for all y.

For the RHS to be true, P(x) and Q(y) have to be true for all x and some y. For RHS to be false, P(x) has to be false for some x or Q(y) has to be false for all y (or all x, which is irrelevant since Q(y) does not depend on x and redundant since the statement would already be false by P(x)).

-