Given the statement $$\{(\exists x(P(x)\to Q(x))),(\exists y P(y))\}\vdash(\exists x Q(x))$$
Show that there is no natural deduction proof for the statement.
I know I need to use the completeness property of natural deduction in the predicate case, but I need some help exhibiting a contradiction. I know that I need to find a interpretation where the $(\exists x(P(x)\to Q(x)))$and $(\exists y P(y))$ holds for any predicate P and Q, but $(\exists x Q(x))$ is false. But I'm having trouble coming up with anything.
I can understand showing the entailment $\{(\exists x(P(x)\to Q(x))),(\exists y P(y))\}\nvDash(\exists x Q(x))$ for one choice of $P$ and $Q$, but to get the correct answer, it seems like I need to show that for any $P$ and $Q$, the entailment doesn't hold.
Counterexample: consider a bag with $n$ balls inside, $n−1$ of which are Black and the last one is Red.
Interpret $P$ as "is Black" and interpret $Q$ as "is White".
Clearly: $∃yPy$ is satisfied by this interpretation, while $∃xQx$ is not (no White balls).
What about $∃x(Px→Qx)$ ? Call $r$ the Red ball: it is such that both $P$ an $Q$ do not hold of it. Thus, $Pr → Qr$ is True (False $\to$ False is True) and thus the above interpretation satisfies $∃x(Px→Qx)$.
Having found an interpretation that satisfies the premises and not the conclusion, we can conclude that: