3
$\begingroup$

True or False: $\exists x(P(x)\lor Q(x))\equiv \exists xP(x)\lor \exists yQ(y)$

My intuition tells me yes, these two things are equivalent. Assume the first, take some $x_0$ s.t. $P(x)\lor Q(x)$, do a proof by cases that the second is true as well. And similarly the other way.

But the proof seems really fast, and kind of trivial. Maybe that's just because the question itself is trivial, or maybe my intuition is incorrect!

First, are those two statements indeed equivalent? Secondly, is my idea for the proof headed in the right direction?

Thanks!

$\endgroup$
  • $\begingroup$ looks OK. math.stackexchange.com/questions/755373/… is related $\endgroup$ – oks May 1 '16 at 19:00
  • 1
    $\begingroup$ You changed the statement. $\endgroup$ – John Douma May 1 '16 at 19:03
  • $\begingroup$ Yes, I messed up the question. It reads as I intended now. $\endgroup$ – kanker7 May 1 '16 at 19:04
  • $\begingroup$ This is one of those statements where a proof isn't to establish the correctness of the statement, it is to establish the correctness of the proof theory. $\endgroup$ – DanielV May 4 '16 at 4:23
2
$\begingroup$

True.
Assume $\exists x(P(x)\lor Q(x)).$ If $P(x)$ then $\exists xP(x)$, so $\exists xP(x)\lor \exists yQ(y)$. If $Q(x)$, then for $y=x$ we have $Q(y).$ So $\exists xP(x)\lor \exists yQ(y)$.

Assume $\exists xP(x)\lor \exists yQ(y)$. If $\exists xP(x)$, then for this $x$, we have $P(x)\lor Q(x)$, done. Similarly for $\exists yQ(y)$.

$\endgroup$
  • $\begingroup$ That's what I thought. Thank you! $\endgroup$ – kanker7 May 1 '16 at 19:13
  • $\begingroup$ you are welcome. $\endgroup$ – user 1 May 1 '16 at 19:14
1
$\begingroup$

Here is a proof of the result by cases using a proof checker:

enter image description here


Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

$\endgroup$
  • 1
    $\begingroup$ Thank you for cheerleader for openlogicproject.org. I spent a good deal of the weekend going through all of their exercises for fun and it was a great mental workout! $\endgroup$ – Matthew Daly Aug 19 at 1:50
  • $\begingroup$ @MatthewDaly It is a great proof checker. $\endgroup$ – Frank Hubeny Aug 19 at 1:53

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.