Nikolay Bazhenov

The study of local and global invariants of the Rogers semilattice is an important and fundamental problem in numbering theory and computability theory. Global invariants include properties such as an existence of a universal numbering, the number of minimal numberings, the cardinality of the entire semilattice, and a criterion for determining whether a semilattice is a lattice. Local invariants, in turn, describe structures, such as initial segments or intervals within the semilattice. We say that a numbering is universal if any other numbering reduces to . The study of universal numberings is important for understanding the structure of semilattices and their classification. In this paper, an existence of universal numberings is considered for finite families of computably enumerable sets located at finit levels of the Ershov hierarchy. The main result is that for any two-element family of computably enumerable sets , its Rogers semilattice, considered at the third level of the Ershov hierarchy, has universal numberings.

Following the approach of Gavryushkin, Khoussainov, and Stephan, we study countable linear orders realized by computably enumerable equivalence relations (ceers). A ceer E realizes a linear order L if there exists a computably enumerable binary relation ⊴ respecting E such that the induced quotient structure ( N / E ; ⊴ ) is isomorphic to L . The known results in this direction show that there is a highly nontrivial interplay between the computability-theoretic properties of a ceer E and the isomorphism types of orders L realizable by E . We obtain a complete characterization of well-orders L realizable by a given ceer E for the case when E realizes some ordinal α < ω ω . In particular, our characterization implies that for any ceer E with infinitely many equivalence classes, either the family of all well-orders realizable by E is contained inside the interval [ ω n ⋅ k ; ω n ⋅ ( k + 1 ) ) for some non-zero n , k < ω , or this family is cofinal in the computable ordinals. The proof of our result develops methods of fine-tuning the behavior of limit points of an E -realizable order L via the computability-theoretic properties of E .