1
$\begingroup$

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

1 Answers 1

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?

  • 0
    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.2012-08-04