Proving a formula is valid in first-order logic.

Question

I'm asked to verify the following formula is valid:

$$\exists x (p(x)\implies q(x)) \iff (\forall x [p(x)\implies\exists x \ q(x)])$$

For the first direction, I want to assume that $p(x)\implies q(x)$ is true for some $a$, so $p(a)\implies q(a)$. I don't understand how this implies the RHS however. Take, for instance, $p(x)$ to be false when $x=a$, but true for all other $x$, and $q(x)$ is always false. Then, the LHS would be true, but the RHS would be false. Am I thinking about the problem incorrectly?

Answer 1

You are right; this equivalence does not hold. And the counterexample you give works.

In fact, we can just consider a domain with just two objects $a$ and $b$, where only $b$ has property $p$, and neither has property $q$.

Then $p(a) \to q(a)$ is true because $p(a)$ is false, and hence $\exists x~( p(x) \to q(x))$ is true.

But $(p(b) \to \exists x~q(x))$ is false, since $p(b)$ is true and $\exists x \ q(x)$ is false. Hence $\forall x~(p(x) \to \exists x~q(x))$ is false.

Answer 2

I am suspicious that this problem is ill formed or intentionally confusing. Note that $x$ is bound twice in the RHS, once by the "$\forall x$" and again by the "$\exists x$". Since it is bound a second time by the "$\exists x$", that instance of $x$ is independent of the instance bound by the "$\forall x$". So the formula is equivalent to the more transparent

$\exists x(p(x)\implies q(x))\iff (\forall x[p(x)\implies\exists y q(y)])$

I believe this proposition is false. Suppose $p(x)$ is "$x$ is odd" and that $q(x)$ is "$x \ne x$", The LHS is satisfied for $x=0$ for then $p(x)$ is false so that the implication is true. But on the RHS, if we take $x=1$, then $\exists y p(y)$ must be satisfied, but it cannot be.