On the transversals of a ceer

Abstract

We study immunity properties of the transversals of computably enumerable equivalence relations (or, briefly, ceers), where a transversal is a set which picks at most one element from every equivalence class of the given equivalence relation. Among transversals, a particular role is played by the principal transversal, whose members are the least elements of the various equivalence classes. While hyperimmunity of the principal transversal implies hyperimmunity of every infinite transversal, we show that this fails both for immunity and hyperhyperimmunity. In both cases, counterexamples are taken from the class of interval ceers, that is, ceers whose equivalence classes are either singletons or intervals of maximal length consisting of consecutive elements of some given c.e. set. We also look into the class of hyperdark ceers, that is, those ceers with infinitely many classes, whose infinite transversals are all hyperimmune, analyzing how this property relates to other computability theoretic properties of the infinite transversals. We make some preliminary observations on the hyperhyperdark ceers, that is, those ceers with infinitely many classes, whose infinite transversals are all hyperhyperimmune.