I was given this statement and asked to express this with universal quantifiers.
Likes(x,y) is a Binary Relation that means that person x likes person y.
The statement given was:
"Everybody is liked by somebody*". Easy Enough, or so I thought? I put:
∀x∃y, (Likes(y,x)). Apparently this is wrong and the correct solution (that a TA displayed as the answer) is ∀y∃x (Likes(x,y)).
For clarity my question is generally :
is ∀x∃y, (P(y,x)) ≡ ∀y∃x, (P(x,y)) ?
I understand the variables are swapped, but i believe that it is logically equivalent, as i just made the "everbody" labled as x and the "somebody" labeled as "y".
Thank you!
Yes, they are equivalent.
To actually formally show this, use the following two equivalences:
$$\forall x \ \varphi(x) \Leftrightarrow \forall y \ \varphi(y)$$
$$\exists x \ \varphi(x) \Leftrightarrow \exists y \ \varphi(y)$$
where $\varphi$ is any formula, and where $\varphi(x)$ is the same as $\varphi(y)$, but with all free variables $x$ and $y$ swapped.
With these, we can do:
$$\forall x \exists y P(y,x) \Leftrightarrow \forall z \exists y P(y,z) \Leftrightarrow \forall z \exists x P(x,z) \Leftrightarrow \forall y \exists x P(x,y)$$