prove or disprove logical inference

Question

I need to prove or disprove the logical inference of the formula b from formula a:

$$ a = \exists y (\forall x P(x) \implies Q(y)) $$ $$ b = \forall x (P(x) \implies \exists y Q(y)) $$

$$ P(x) \space and \space Q(x) \space are \space single-place \space ratios $$

Meaning , to show either that every model that satisfy a also satisfy b or to show that there is a model that satisfy a but not satisfy b.

By intuition , I think that I need to prove this , meaning every model that works for a will word for b but I don't know how to approach this.

Answer 1

Let the domain be $\mathbb{N}$, let $P(x)$ be the statement that $x$ is prime, and let $Q(y)$ be the statement that $y \notin \mathbb{N}$.

Then the statement $a$ is clearly true, since the statement $\forall x P(x)$ is false.

Consider that $$\neg b =\neg \forall x [P(x) \Longrightarrow \exists y Q(y)]$$ is equivalent to $$\exists x P(x) \ \& \ \forall y (\neg Q(y)),$$ which is true.

This model provides a counterexample to the statement that $$a \Longrightarrow b$$ is a tautology.

Answer 2

$a$ can be rewritten using prenex normal form (nonempty universe assumption), then unprenexing it:

$$\begin{array} {rl} % a &= \exists y ~(\forall x~ Px \implies Qy) % \\ &= \exists y ~\exists x~(Px \implies Qy) % \\ &= \exists x ~\exists y~(Px \implies Qy) % \\ &= \exists x ~(Px \implies \exists y ~ Qy) % \\ &= \forall x ~Px \implies \exists y ~ Qy % \end{array}$$

$b$ can be treated similarly:

$$\begin{array} {rl} % b &= \forall x ~(Px \implies \exists y ~ Qy) % \\ &= \exists x ~ Px \implies \exists y ~ Qy % \end{array}$$

So the question becomes determining whether:

$$\forall x ~Px \implies \exists y ~ Qy \vDash \exists x ~ Px \implies \exists y ~ Qy$$

So the counter examples are exactly those when $\exists y ~Qy$ is false, and $\exists x ~ Px$ is true, and $\forall x ~ Px$ is false.