Elementary Theories of Rogers Semilattices in the Analytical Hierarchy

Investigations of elementary theories for Rogers semilattices constitute one of the core directions in the theory of numberings. In recent years, the studies of significative differences in isomorphism types of these semilattices, witnessed by their algebraic and first-order properties, flourished (especially, in the area of numberings belonging to the levels of various recursion-theoretic hierarchies). Nevertheless, there are not many known results on the algorithmic complexity of elementary theories for Rogers semilattices. In this chapter, we investigate initial segments of Rogers semilattices in the analytical hierarchy, and we study decidability for fragments of the corresponding first-order theories. Let n be a non-zero natural number. For an arbitrary non-trivial Rogers semilattice R induced by a Σn1-computable family of sets, we obtain the following results. The ₄-fragment of the theory Th(R) in the signature of partial orders is hereditarily undecidable. The Σ₁-fragment of Th(R) in the signature of upper semilattices is decidable. Similar results hold for families in the arithmetical hierarchy, starting with the Σ40 level.