0
$\begingroup$

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?

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How does this proof make use of the $\forall x$? Or is that component unnecessary? $\endgroup$ – Chubwagon Nov 8 '18 at 18:11
  • $\begingroup$ 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? $\endgroup$ – Chubwagon Nov 8 '18 at 18:21
  • $\begingroup$ 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. $\endgroup$ – Tony Dean Nov 8 '18 at 18:40
  • $\begingroup$ 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$".) $\endgroup$ – Tony Dean Nov 8 '18 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.