# Prove $\exists x(\varphi\wedge\psi)$ is $\underline{not}$ logically equivalent to $\exists x\varphi\wedge\exists x\psi$

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$

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?

• 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. – James Apr 3 '15 at 18:46
• The step $(3)$ you can not go back to $(2)$ because this is not the same $d$ working for $\psi$ and $\varphi$ – Elaqqad Apr 3 '15 at 18:48
• @James Surely that would be the same for $\exists x(\varphi\vee\psi))$? – Sam Houston Apr 3 '15 at 18:49
• Your title is wrong. – JDH Apr 3 '15 at 18:49
• 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). – vadim123 Apr 3 '15 at 19:10

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