TY - CHAP

T1 - Isomorphism Types of Rogers Semilattices in the Analytical Hierarchy

AU - Bazhenov, Nikolay

AU - Ospichev, Sergey

AU - Yamaleev, Mars

N1 - The work of M. Yamaleev was supported by Russian Science Foundation, project No. 18-11-00028. The work of S. Ospichev was funded by RFBR according to the research project No. 17-01-00247. The work of N. Bazhenov was supported by Nazarbayev University Faculty Development Competitive Research Grants N090118FD5342.

PY - 2024

Y1 - 2024

N2 - 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 Π1m-computable family cannot be isomorphic to a Rogers semilattice of a Π1n-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.

AB - 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 Π1m-computable family cannot be isomorphic to a Rogers semilattice of a Π1n-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.

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85179413785&origin=inward&txGid=044a7610d9bee10cfcf9b0cc87ebbd21

UR - https://www.mendeley.com/catalogue/794424c0-ee54-386c-a064-f8504ea5d3d6/

U2 - 10.1142/9789811278631_0004

DO - 10.1142/9789811278631_0004

M3 - Chapter

SN - 9811278628

T3 - Lecture Notes Series, Institute for Mathematical Sciences

SP - 97

EP - 114

BT - Lecture Notes Series, Institute for Mathematical Sciences

PB - World Scientific

ER -