Isomorphism Types of Rogers Semilattices in the Analytical Hierarchy. / Bazhenov, Nikolay; Ospichev, Sergey; Yamaleev, Mars.
Lecture Notes Series, Institute for Mathematical Sciences. World Scientific, 2024. p. 97-114 (Lecture Notes Series, Institute for Mathematical Sciences; Vol. 42).Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review
}
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 -
ID: 60401971