A c.e. equivalence relation is computable if each equivalence class is of a fixed finite cardinality with finitely many exceptions

Question

I've been working on the following quiz:

Let $E \subseteq \omega \times \omega$ be a c.e. equivalence relation and $n \in \omega$. Suppose all of $E$'s equivalence classes but finitely many classes are of cardinality $n$. Show that in fact $E$ is computable.

Here are my observations:

1. If no equivalence classes are of cardinality $n$, then one can take finitely many representatives for the equivalence classes (this might be nonuniform, but it doesn't matter). Then each equivalence class $C$ is computable, since $C$ is c.e. and so is $\omega \setminus C$, which is a finite union of the other equivalence classes, each of which is again c.e.
2. Without loss of generality, one can assume that if an equivalence class is not of cardinality $n$, then it is of cardinality $>n$, or even infinite.
3. If all equivalence classes are of cardinality $n$, then $E$ is computable, since for each $x$ one can effectively determine $x/E$ by enumerating it until having enumerated $n$ elements.

But I have hard time in reconciling the procedures for the two extreme cases. When one tries to decide if $xEy$, given $x, y$, prima facie it appears impossible to decide if $x$ or $y$ lives in an equivalence class of cardinality $n$ or $\neq n$ within a finite amount of steps.

How can I do that?

Answer 1

It is not true. For a counterexample, fix an enumeration of Turing machines, and define $E$ as $$ x \mathrel E y \iff (x=y) \lor (T_x\text{ and }T_y\text{ both halt}) $$ This is clearly recursively enumerable, and every equivalence class except one has cardinality $1$.

On the other hand, if $E$ is computable, then we can use it to decide the halting problem: Given some machine $T_x$ simply ask whether $x\mathrel E h$ where $h$ is the index of a machine that is known to halt.