Prove or give counter example: $\forall x \exists y(Q(y)\wedge P(x))\vDash \exists y\forall x(Q(y)\wedge P(x))$

I think this statment is true:

$x$ and $y$ are not free, so I can use the following logical equivalences: $$\forall x(\alpha \vee \beta) \equiv \alpha \vee \forall x(\beta)$$ $$\exists x(\alpha \vee \beta) \equiv \alpha \vee \exists x(\beta)$$

$\forall x\exists y(Q(y)\wedge P(x))\Rightarrow\exists y(Q(y)\wedge\forall xP(x)) \Rightarrow \exists y(\forall xP(x)\wedge Q(y))\Rightarrow\forall xP(x)\wedge \exists yQ(y) \Rightarrow\exists y(\forall xP(x)\wedge Q(y))\Rightarrow\exists y( Q(y)\wedge\forall xP(x))\Rightarrow\exists y(\forall x( Q(y)\wedge P(x)))$

$\mathbf{\Rightarrow\exists y\forall x( Q(y)\wedge P(x))}$

$$$$ Did I get it right ? Thank you!


Your first step:

$$\forall x\exists y(Q(y)\wedge P(x))\Rightarrow\exists y(Q(y)\wedge\forall xP(x))$$

is not an instance of the two equivalence principles you mention, since the $\exists$ is between the $\forall$ and the $\land$

What you can instead is:

$$\forall x\exists y(Q(y)\wedge P(x))\Leftrightarrow \forall x\exists y(P(x)\wedge Q(y))\Leftrightarrow\forall x (P(x)\wedge \exists yQ(y))$$

and go from there

(indeed, note that your steps 3 and 5, as well as 2 and 6, are identical ... that should have told you something went wrong!)

  • $\begingroup$ Thank you for your answer! How do I continue from here (since you said I'm not using the quivalence principles I mention right)? $\endgroup$ – rose12 Aug 12 '18 at 20:06
  • $\begingroup$ @rose12 commute, bring the $\forall$ in, commute, bring the $\exists$ out, commute, and bring the $\forall$ out $\endgroup$ – Bram28 Aug 12 '18 at 20:10

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.