Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
add comment

2 Answers

up vote 0 down vote accepted

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)

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.