# $\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.

• why are both sides true when $\forall y P(y)$ is false? – supinf Jan 20 at 18:25
• @supinf I meant both implications. – IntegrateThis Jan 20 at 18:27
• I still do not understand it. – supinf Jan 20 at 18:28
• @supinf for the statement on the right, it would imply False -> Something is True. For the first statement, it would be exists an x, for all y (P(y)=False -> Q(x)) which is also true? Maybe I am confused. – IntegrateThis Jan 20 at 18:30

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?

• I have added my own overall answer, if you could check its correctness that would be appreciated. – IntegrateThis Jan 21 at 4:08

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.$$

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.
• This is correct. Alternatively, you could also use concrete statements for $P$ and $Q$ to show that the implications are not equivalent. – supinf Jan 21 at 8:47