Linear Orders Realized by C.E. Equivalence Relations

Let E be a computably enumerable (c.e.) equivalence relation on the set ω of natural numbers. We say that the quotient set ω/E (or equivalently, the relation E) realizes a linearly ordered set L if there exists a c.e. relation ⊴ respecting E such that the induced structure (ω/E;⊴) is isomorphic to L. Thus, one can consider the class of all linearly ordered sets that are realized by ω/E; formally, K(E) = {L | the order-type L is realized by E}. In this paper we study the relationship between computability-theoretic properties of E and algebraic properties of linearly ordered sets realized by E. One can also define the following pre-order ≤ _lo on the class of all c.e. equivalence relations: E1 ≤ _lo E2 if every linear order realized by E1 is also realized by E2. Following the tradition of computability theory, the lo-degrees are the classes of equivalence relations induced by the pre-order ≤ _lo. We study the partially ordered set of lo-degrees. For instance, we construct various chains and anti chains and show the existence of a maximal element among the lo-degrees.