= Solution
The <equivalence classes> of an <equivalence relation> are nonempty, pairwise disjoint, and partition $\mathbb N$. To construct a <transversal of a set family> for them, choose the least member of each class. Its set is
$$
\boxed{S=\{n\in\mathbb N:\forall m<n\;m\not\sim n\}.}
$$
Every class has a least element by the <well-ordering principle for the natural numbers>, and that element satisfies the displayed condition. A nonleast element fails it because a smaller equivalent element exists. Therefore \b[$S$ meets every class in exactly one point], not merely infinitely many classes.
The <complement> of $\sim$ is <semidecidable>, so for a given $n$ run the finitely many semidecision procedures for $m\not\sim n$, $0\leq m<n$, in parallel. Accept $n$ once all have accepted. If $n$ is a least representative, all finitely many computations halt; otherwise at least one never accepts. For $n=0$, the empty list of tests succeeds immediately. This proves that $S$ is <semidecidable>. Equivalently, enumerate inequivalent pairs and output $n$ once all pairs $(m,n)$ with $m<n$ have appeared, dovetailing the requirements over all $n$. This is the <semidecidable least-representative transversal> of a <co-computably enumerable equivalence relation>. Infinitely many classes make $S$ infinite, but that hypothesis is unnecessary for the existence and semidecidability of a complete transversal.
Back to article page
