# Proving a formula is valid in first-order logic.

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?

• The bracketing has gone awry on the RHS. – Peter Smith Nov 8 '18 at 17:50
• The bracketing is the same as in my problem. The $\forall x$ appears outside the main implication. – Chubwagon Nov 8 '18 at 17:51

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.

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.

• How does this proof make use of the $\forall x$? Or is that component unnecessary? – Chubwagon Nov 8 '18 at 18:11
• This is how I'm trying to think about it. $p(x)\implies q(x)$ is either 1) satisfied or 2) not. If it is, it is because either both $q(a)$ is true or because $p(a)$ is false. If $A=\{a:q(a)=T\}=\emptyset$, but $B=\{b:p(b)=T\}\neq \emptyset$ then the right hand side fails to be true precisely when $x=b$, right? It goes without saying that the RHS is true for all values of $x$ that satisfy the right, but is that all we are trying to prove? – Chubwagon Nov 8 '18 at 18:21
• That's a fair question and I have been sloppy in my solution. Now 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. – Tony Dean Nov 8 '18 at 18:40
• I think your sets $A$ and $B$ correctly show the fallacy in the proposition and illustrate the general case in the counterexample I presented in my previous comment. I have revised my answer to reflect this. (I assume you meant "$x \in B$" when you said "$x=b$".) – Tony Dean Nov 8 '18 at 18:59