Working on P.D. Magnus. forallX: an Introduction to Formal Logic (p. 268, exercise B. 8).
In order to achieve what is being requested, I chose:
- domain: $\{0, 1\}$
- interpretation: $R$ as "$=$"
We can make $\forall x\exists yR(x,y)$ true, noting…
$$
\exists yR(0,y) \land \exists yR(1,y) \equiv (0 = 0 \lor 0 = 1) \land (1 = 0 \lor 1 = 1)
$$
is true.
Now, I can make $\exists x\forall yR(x,y)$ false, taking into account the logical equivalence:
$$\neg\exists x\forall yR(x,y) \equiv \forall x\exists y \neg R(x,y)$$
Then,
$$
\exists y\lnot R(0,y) \land \exists y\lnot R(1,y) \equiv (0 \neq 0 \lor 0 \neq 1) \land (1 \neq 0 \lor 1 \neq 1)
$$
is true, which means that $\exists x\forall yR(x,y)$ is false.
Does it correctly show that pair of sentences are not logically equivalent?
Best Answer
Yes, this is a counterexample and it proves the statement "There is a binary relation $R$ such that $\forall x\exists yR(x,y)\longleftrightarrow \exists x\forall yR(x,y)$ is wrong", and it means they are not logically equivalent for all $R$.