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.

Are these if and only if equalities always true ?

1 - $\exists x \exists y \;(P(x) \;and \;Q(y))\Leftrightarrow \exists x P(x) \; and \;\exists y \;Q(y)$

2- $\exists x \exists y \;(P(x) \;or \;Q(y))\Leftrightarrow \exists x P(x) \; or \;\exists y \;Q(y)$

3- $\forall x \forall y \; (P(x) \;or \;Q(y)) \Leftrightarrow \forall x P(x) \;or\; \forall y Q(y) $

4- $\forall x \forall y \; (P(x) \;and \;Q(y)) \Leftrightarrow \forall x P(x) \;and\; \forall y Q(y) $

share|improve this question

1 Answer 1

They all hold. (1): If $P(x_0)$ and $Q(y_0)$ are both true, then certainly $P(x_0)$ and $Q(y_0)$ is. Similarly, if either of those holds, then $P(x_0)$ or $Q(y_0)$ is true.

For the universally quantified sentences, the same argument gets the right-to-left implications. For the left-to-right in 3, suppose I had $x_0, y_0$ so $P(x_0)$ and $Q(y_0)$ were both false. Then the left-hand side would fail as well. So, by the contrapositive, if I get the left-hand side I get at least one disjunct on the right. Think you can extend the argument to (4) now?

share|improve this answer
    
3 is false I think –  mehdi Aug 4 '12 at 13:42
    
P(x2) true Q(y2) false, P(x1) false Q(y1) true, then right hand side is false and left is true –  mehdi Aug 4 '12 at 13:45
    
For the left hand side you've only made two of the four possible pairings. Under a $\forall$ we need to be able to fix $x$ and then vary $y$ across all its values, and vice versa, so you also need to check $P(x_2)$ or $Q(y_1)$, as well as $P(x_1)$ or $Q(y_2)$. Only three of the four hold. –  Kevin Carlson Aug 4 '12 at 13:57
    
Sure, but I dont think there is a need to check for both cases if you have one false example –  mehdi Aug 4 '12 at 14:19
    
No, I agree with you that the right hand side is false, but I'm saying the left hand side is also false because there's a choice of $x$ and $y$ making $(P(x)$ or $Q(y))$ false. –  Kevin Carlson Aug 4 '12 at 14:52

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.