I'm given this definition of an equivalence relation.
Let $\phi(x)$ and $\psi(x)$ be formulas (with the same set of free variables) written in some fixed language $\ell$. We say that $\phi$ and $\psi$ are logically equivalent, and write
$\phi \equiv \psi$, if:For all sets M, with any interpretations of the symbols of $\ell$ in M and for any
tuple m from M, we have M$\models \phi(m)$ if and only if M$\models \psi(m)$.
I proved that this is an equivalence relation on the set of all formulas,
but now I don't know how to prove that all the equivalence classes are infinite and the fact that there are infinite equivalence classes.
Any help will be appreciated.
Best Answer
To show that the classes are infinite, observe that for any sentence $\phi,$ $$\phi\equiv \phi\land\phi\equiv \phi\land\phi\land\phi\equiv\ldots.$$
To show that there are infinitely many equivalence classes assuming you're working in first order logic with equality, we can write the statement "$M$ has $2$ elements" as $$ \forall x\forall y(x\ne y\to \forall z(z=x\lor z=y))\land\exists x\exists y(x\ne y)$$ and we can similarly write the statement "$M$ has $n$ elements" for any $n\in\mathbb N.$ These statements are in different equivalence classes and there are an infinite number of them.