Co-computably enumerable equivalence relation

An equivalence relation on the natural numbers is co-computably enumerable when its complement as a set of pairs is computably enumerable. Inequivalence can then be positively recognized, even when equivalence cannot be decided. This is sufficient for a semidecidable least-representative transversal.

For a co-computably enumerable equivalence relation, the least element of each equivalence class forms a complete transversal of a set family. Membership is semidecidable: run the finitely many inequivalence tests against smaller numbers in parallel and accept when all succeed. Infinitely many classes are needed only to make the resulting transversal infinite.