Does the LHS implies the RHS?

Question

$\forall y~[ \exists x~[ P(x) \land {L(x,y)} ]] \colon \exists x~[P(x) \land {∀y~[L(x,y)]}]$

Let $L(x,y) := x$ loves $y ; P(x) := x$ eats pizza

I understand LHS as: Everyone is loved by someone and that particular someone eats pizza and RHS as: There is someone who eats pizza and loves everyone. Is it correct that LHS implies RHS?

Answer 1

This isn't true.

Suppose there are four people, Adam, Brenda, Charlie and Darya, such that:

• Adam, Brenda and Charlie eat pizza, but Darya does not;
• Adam likes Brenda and Charlie, but not Darya; and
• Brenda likes Adam and Darya, but not Charlie; and
• Charlie doesn't like anyone.

Then everyone is liked by someone who eats pizza, so $\forall y \exists x [P(x) \wedge L(x,y)]$ is satisfied.

However, there is not someone who eats pizza and loves everyone, since Adam doesn't like Darya, Brenda doesn't like Charlie, and Charlie doesn't like anyone (and Darya doesn't eat pizza). So $\exists x[ P(x) \wedge \forall y\ L(x,y)]$ is not satisfied.

---

P.S. A counterexample can be constructed with only three people, but it's easier to intuit with four, since a three-person example requires talking about people liking or not liking themselves.

---

P.P.S. This is an instance of quantifier alternation, since the second formula is equivalent to $\exists x \forall y [P(x) \wedge L(x,y)]$. The general principle at work is that, for any formula $\varphi(x,y)$, it is always true that the implication $\exists y \forall x\ \varphi(x,y) \to \forall x \exists y\ \varphi(x,y)$ is true, but the converse is often false.