Is this equivalence true?

Question

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.

Answer 1

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)

Answer 2

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)).