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.
Best Answer
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?