I am looking for an example of an equivalence relation which is recursively enumerable but not recursive. I found the following statement: If R is an equivalence relation r.e. which is not recursive. Then for each $n$ there are infinitely many classes whose size is different than $n$.
I will appreciate any clue to prove this statement or to construct such relation.
$x R y \iff x = y \vee \phi_x(x) = \phi_y(y)$ (where $\phi_i$ is an enumeration of the partial recursive functions).
This works because the halting problem is undecidable, so it cannot be determined recursively whether $\phi_x(x)$ and $\phi(y)$ halt and are equal.