Is $\exists x[p(x)\to ¬ q(x)]$ equivalent to $\exists xp(x)\to\exists x ¬q(x).$?

Question

I have to show that $\exists x[p(x)\to ¬ q(x)]$ is not equivalent to $\exists xp(x)\to\exists x ¬q(x)$.

Using well-known equivalences, it seems impossible to prove that the two formulas are equivalent.

But how can I prove that the two formulas are not equivalent? any idea? I tried several examples and I am stuck.

Answer 1

The two formulas are not equivalent. Consider a domain with exactly two elements, $0$ and $1$. For $0$, both properties $p$ and $q$ hold. For $1$, the property $p$ is false but the property $q$ holds.

Thus, with this interpretation, the formula $\exists x p(x)$ is true (because of $0$) but $\exists x \lnot q(x)$ is false (since $q$ holds for both elements of our domain). Hence, $\exists x p(x) \to \exists x \lnot q(x)$ is false.

According to this interpretation, for $x = 1$, $p(x) \to \lnot q(x)$ is true (since $p$ is false for $1$), so $\exists x (p(x) \to \lnot q(x))$ is true.

We have shown that there exists a domain and an interpretation of the predicates $p$ and $q$ such that the formulas $\exists x p(x) \to \exists x \lnot q(x)$ and $\exists x (p(x) \to \lnot q(x))$ do not have the same truth value. Therefore, the two formulas are not equivalent.

Answer 2

We know theorem $$(\exists x) (R \lor S) \Leftrightarrow \big((\exists x)R \lor (\exists x)S \big)$$ Now is enough to remember, that $A \Rightarrow B$ is same as $\neg A \lor B$. So we can write: $$(\exists x) (R \Rightarrow S) \Leftrightarrow \big((\exists x)\neg R \lor (\exists x)S \big) \quad (1)$$

From another hand $$(\exists x)\neg R \Rightarrow (\exists x)S \Leftrightarrow \big((\forall x)\neg R \lor (\exists x)S \big) \quad (2)$$ As we see $(1)$ and $(2)$ have essential difference in right hand in quantifiers.