Proof of Why or Why Not some equivalence holds

Question

How do I prove that this equivalence $$\lnot\exists x\,\forall y\,(P(x)\Rightarrow\lnot Q(x,y))\equiv \forall x\,\exists y\,(P(x)\land Q(x,y))$$ holds or not?

I remember that $A\implies B\equiv\lnot A\lor B$. Would this help with this?

Answer 1

A few more equivalences you need to remember: $\neg\exists\equiv\forall\neg$, $\neg\forall\equiv\exists\neg$, and $$\neg(p\to q)\equiv(p\land\neg q) \tag{NegImp} $$ The last follows from the equivalence you remember plus De Morgan, plus $q\equiv\neg\neg q$, which is another equivalence you'll need. Can you take it from there?

No? OK, here: $$\begin{align} \neg\exists x\forall y\,(P(x)\to \neg Q(x,y)) &\iff \forall x\neg\forall y\,(P(x)\to \neg Q(x,y)) \tag{$\neg\exists\equiv\forall\neg$} \\ &\iff \forall x\exists y\,\neg\,(P(x)\to \neg Q(x,y)) \tag{$\neg\forall\equiv\exists\neg$} \\ &\iff \forall x\exists y\,(P(x)\land \neg\neg Q(x,y)) \tag{by NegImp} \\ &\iff \forall x\exists y\,(P(x)\land Q(x,y)) \tag{$q\equiv\neg\neg q$} \\ \end{align}$$