Predicate logic formulas such that statement doesn't hold

197 Views Asked by At

I'm brushing up on my logic skills and have some trouble finding formulas such that

$$\exists x (\varphi\to\psi)\Rightarrow ((\exists x\,\varphi)\to(\exists x\,\psi))$$

doesn't hold. For it to hold I could easily just set $\varphi$ to ⊥, but not holding seem to be harder. If it had been $\forall x$ rather than $\exists x$ it would be easy to define a formula that holds for some $x$ but not all, but that doesn't seem to work with $\exists x$. Any help would be much appreciated.

2

There are 2 best solutions below

0
On BEST ANSWER

All you need is a counterexample: a scenario where the left side holds but the right side does not hold.

Easy:

Take a world with 2 objects, $a$ and $b$. Let $a$ have property $\varphi$, and say that neither of them have property $\psi$.

Then $\exists x \ ( \varphi(x) \to \psi(x) )$ is true, since we can simply point to $b$: it does not have property $\varphi$, so for $b$, the left side of the conditional is false, making the whole conditional true.

However, we also have that $\exists x \ \varphi(x)$ is true (point to $a$), but $\exists x \ \psi(x)$ is false, and hence the conditional $\exists x \ \varphi(x) \rightarrow \exists x \ \psi(x)$ is false.

2
On

Any $x$ such that $\phi(x)$ does not hold, is also an $x$ such that $\phi(x) \implies \psi(x)$ holds as well, regardless of $\psi$.

But if there is some $x$ such that $\phi(x)$ does hold, but no $x$ where $\psi(x)$ holds, the implication on the right hand side is false.