2
$\begingroup$

Is: $\exists x (P(x) \land Q(x)) \rightarrow \exists x P(x) \land \exists x Q(x) $ logically valid?.

I cant found an intepretation in wich the formula is false.

$\endgroup$
  • 2
    $\begingroup$ Yes, it is logically valid. The opposite implication is not logically valid. $\endgroup$ – André Nicolas Jun 29 '13 at 4:47
5
$\begingroup$

Yes, indeed it is valid. No counterexample to be found.

If there exists an $x$ for which both ($P(x)$ and $Q(x)$) hold, then there certainly exists an $x$ for which $P(x)$ holds, and there exists an $x$ for which $Q(x)$ holds.

The converse implication is not valid, however. If there exists an $x$ that's a pumpkin and there exists an $x$ that is green, it does not follow that there exists an $x$ that is a green pumpkin.

$\endgroup$
  • $\begingroup$ @Amzoti I don't know where I came up with "green pumpkin"...it would have been a better counter example to the converse if I had used: exists an odd number and exists an even number, but there does not exist a number that is both odd and even. $\endgroup$ – Namaste Jun 30 '13 at 0:27
1
$\begingroup$

Yes, it's valid. If there is something which is both $P$ and $Q$, then there is something which is $P$ AND there is something which is $Q$ (viz. the same thing which was both $P$ and $Q$).

$\endgroup$
  • $\begingroup$ In "How to prove it" by Velleman, The existential quantifier does not distribute over conjunction but over disjunction.The example in the book is P(X) means x is bright-eyed, Q(X) bushy-tailed. Then the hypothesis of the given conditional here would be there exists someone who is both bright-eyed and bushy-tailed. the conclusion of the given conditional here would be there exists someone who is bright eyed and there is also someone who is bushy-tailed.The way the book explained it there's no way the existential quantifier distributes over disjunction, but ur explanation makes total sense !! $\endgroup$ – Mustafa Adam Jul 2 '13 at 16:18
  • $\begingroup$ So existentials do distribute over disjunction. What this means is $\exists x (\varphi \vee \psi)$ is logically equivalent to $\exists x \varphi \vee \exists x \psi$. This isn't the case for conjunction: while $\exists x (\varphi \wedge \psi)$ does, as stated above, logically entail $\exists x \varphi \wedge \exists x \psi$, the second does not logically entail the first. To see a simple example, let $\varphi = P(x)$ and $\psi = \neg P(x)$. $\endgroup$ – Alex Kocurek Jul 2 '13 at 17:02
  • $\begingroup$ I get it now. I think in my humble opinion the book was not accurate at all in explaining this point. It states after explaining the universal quantifier distribution over conjunction that and I quote " However the corresponding distributive law does not work for the existential quantifier ." it also states that " They don't mean the same thing AT ALL". So what about the universal quantifier and conjunction. Is that an equivalency (biconditional) ? $\endgroup$ – Mustafa Adam Jul 2 '13 at 19:18
  • $\begingroup$ He probably meant that $\exists x (P(x) \wedge Q(x))$ doesn't mean the same thing as (i.e. isn't equivalent to) $\exists x P(x) \wedge \exists x Q(x)$. However, $\forall x (P(x) \wedge Q(x))$ is logically equivalent to $\forall x P(x) \wedge \forall x Q(x)$, so there's a sense in which these universal sentences "mean the same thing". The situation is reverse for disjunction (viz. existentials distribute over disjunction, but not universals) as noted above. In the disjunctive case, $\forall x P(x) \vee \forall x Q(x)$ logically entails $\forall x (P(x) \vee Q(x))$, but not conversely. $\endgroup$ – Alex Kocurek Jul 3 '13 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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