$\exists x \forall y (P(y) \implies Q(x))$ and $\forall y P(y) \implies \exists x Q(x)$ are not logically equivalent 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.
 A: 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?
A: 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.$$
A: 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.
