$\exists x \forall y (P(y) \implies Q(x))$ and $\forall y P(y) \implies \exists x Q(x)$ are not logically equivalent

Question

I am trying to show that the following are not logically equivalent (according to a practice question)

$\exists x \forall y (P(y) \implies Q(x))$ and $\forall y P(y) \implies \exists x Q(x)$

In the first case I am trying to find some kind of statement where $x,y$ are integers (something like $P(x)$ is the is even predicate and $Q(x)$ is odd predicate, or maybe that $Q(x)$ implies $x$ divides $y$).

I am imagining I need a scenario where one statement is True implies False, and the other is True, for the same values of $x,y$.

If $\forall y P(y)$ is false, then both implications will be true, so suppose that $\forall y$ P(y) is true. I'm not sure how to proceed from here. Hints/Clarifications appreciated.

Answer 1

hint 1:

Your statement, that the first statement is true if $\forall y P(y)$ is false, was a mistake. In your comment it seems like you thought that if $\forall yP(y)$ does not hold, then $P(y)$ is always false. It can also happen that $P(y)$ is false for some $y$ and true for some $y$.

You actually should assume, that $\forall y P(y)$ is false, but there is an $y$ such that $P(y)$ is true.

hint 2:

Consider the two cases for $\exists x Q(x)$. What happens if it is false? what if it is true?

Answer 2

With false and true respectively $0$ and $1$, the statements are$$\max_yP(y)\le\max_xQ(x)$$ and$$\min_yP(y)=1\implies\max_xQ(x)=1.$$These statements differ in truth value if$$\min_yP(y)=0,\,\max_yP(y)=1,\,\max_xQ(x)=0.$$

Answer 3

As per supinf's hints. How about this argument:

Suppose that $\exists y$ such that $P(y)$ is true, but $\forall y P(y)$ is false. Also suppose that $Q(x)$ is false for any $x$.

Then the first logical statement is false since for such a $y$ where $P(y)$ is true, we would have there exists an $x$ such that $P(y) \implies Q(x)$ is true, which is false, and so the overall statement is false.

For the second statement, since the premise $\forall y P(y)$ is false, then the statement is vacuously true. Hence the statements aren't equivalent.