Isomorphism Types of Rogers Semilattices in the Analytical Hierarchy
A numbering of a countable family S is a surjective map from the set of natural numbers ω onto S. A numbering ν is reducible to a numbering µ if there is an effective procedure which given a ν-index of an object from S, computes a µ-index for the same object. The reducibility between numberings gives rise to a class of upper semilattices, which are usually called Rogers semilattices. This chapter studies Rogers semilattices for families S ⊂ P (ω) belonging to various levels of the analytical hierarchy. We prove that for any non-zero natural numbers m ≠ n, any non-trivial Rogers semilattice of a -computable family cannot be isomorphic to a Rogers semilattice of a -computable family. One of the key ingredients of the proof is an application of the result by Downey and Knight on degree spectra of linear orders.