2
$\begingroup$

Question:

  1. Prove for all $\mathcal{L}$-formulae $\varphi,\psi:$

$\exists x(\varphi\vee\psi)$ is logically equivalent to $\exists x\varphi\vee\exists x\psi$

  1. Show that it is $\underline{not}$ the case that for all $\mathcal{L}$-formulae $\varphi,\psi:$

$\exists x(\varphi\wedge\psi)$ is logically equivalent to $\exists x\varphi\wedge\exists x\psi$

Answer:

For the first part:

Let,

(1) $\mathfrak{M},s\models\exists x(\varphi\lor\psi)\Leftrightarrow\exists d\in\left|\mathfrak{M}\right|s.t.\mathfrak{M},s\frac{d}{x}\models\varphi\lor\psi$

(2) $\Leftrightarrow\exists d\in\left|\mathfrak{M}\right|s.t. \mathfrak{M},s\frac{d}{x}\models\psi$

(3) $\Leftrightarrow\mathfrak{M},s\frac{d}{x}\models\varphi$ for some $d\in\left|\mathfrak{M}\right|$ or $\mathfrak{M},s\frac{d}{x}\models\psi$ for some $d\in\left|\mathfrak{M}\right|$

(4) $\Leftrightarrow\mathfrak{M},s\models\exists x\varphi$ or $\mathfrak{M},s\models\exists x\psi$

(5) $\Leftrightarrow\mathfrak{M},s\models\exists x\varphi\vee\exists x\psi$ $\square$

For the second part, it is proven with a contradictory example.

However, if we were to try and prove the validity of the statement being true in the same way as for the first part: steps (1) to (5) and replacing 'or' with 'and'. Which step would the statements not hold for and why not?

$\endgroup$
  • $\begingroup$ You get $\exists x(\phi \land \psi) \Rightarrow \exists x (\phi) \land \exists x(\psi)$ but the reverse is not true because you don't necessarily pick the same object for each of the two conjuncts. $\endgroup$ – James Apr 3 '15 at 18:46
  • $\begingroup$ The step $(3)$ you can not go back to $(2)$ because this is not the same $d$ working for $\psi$ and $\varphi$ $\endgroup$ – Elaqqad Apr 3 '15 at 18:48
  • $\begingroup$ @James Surely that would be the same for $\exists x(\varphi\vee\psi))$? $\endgroup$ – Sam Houston Apr 3 '15 at 18:49
  • 1
    $\begingroup$ Your title is wrong. $\endgroup$ – JDH Apr 3 '15 at 18:49
  • 1
    $\begingroup$ There is a time when I am alive, and there is a time when Newton is alive. However there is not a time when (I am alive and Newton is alive). $\endgroup$ – vadim123 Apr 3 '15 at 19:10
1
$\begingroup$

You get $\exists x (\phi \land \psi) \rightarrow \exists x (\phi) \land \exists x (\psi)$ but the reverse is not true because you don't necessarily pick the same object for each of the two conjuncts. For instance take a look at $$ \exists x (x = 0 \lor x = 1), \exists x(x = 0) \lor \exists x(x = 1) \text{ vs } \exists x (x = 0 \land x = 1), \exists x (x=0) \land \exists x (x=1)$$ over $\mathbb{N}$.

Notice that, in both cases when we move from the con(dis)-junction being the main connective to the quantifier being the main connective, we can't pick the same "$x$" as witnesses, this is important in the $\land$ case as you need both of them to be true of the same $x$, however in the $\lor$ case, we only need one of the to be true for some $x$.

$\endgroup$

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.