TY - JOUR
T1 - Rogers semilattices of limitwise monotonic numberings
AU - Bazhenov, Nikolay
AU - Mustafa, Manat
AU - Tleuliyeva, Zhansaya
N1 - Funding Information:
The work was supported by Nazarbayev University Faculty Development Competitive Research Grants 021220FD3851. N. Bazhenov was supported by the Russian Science Foundation (project no. 18‐11‐00028). M. Mustafa and Zh. Tleuliyeva were partially supported by MESRK grant No. AP08856834. Part of the research contained in this paper was carried out while N. Bazhenov was visiting the Department of Mathematics of Nazarbayev University, Nur‐Sultan. The authors wish to thank Nazarbayev University for its hospitality.
Publisher Copyright:
© 2022 Wiley-VCH GmbH
PY - 2022
Y1 - 2022
N2 - Limitwise monotonic sets and functions constitute an important tool in computable structure theory. We investigate limitwise monotonic numberings. A numbering ν of a family (Formula presented.) is limitwise monotonic (l.m.) if every set (Formula presented.) is the range of a limitwise monotonic function, uniformly in k. The set of all l.m. numberings of S induces the Rogers semilattice (Formula presented.). The semilattices (Formula presented.) exhibit a peculiar behavior, which puts them in-between the classical Rogers semilattices (for computable families) and Rogers semilattices of (Formula presented.) -computable families. We show that every Rogers semilattice of a (Formula presented.) -computable family is isomorphic to some semilattice (Formula presented.). On the other hand, there are infinitely many isomorphism types of classical Rogers semilattices which can be realized as semilattices (Formula presented.). In particular, there is an l.m. family S such that (Formula presented.) is isomorphic to the upper semilattice of c.e. m-degrees. We prove that if an l.m. family S contains more than one element, then the poset (Formula presented.) is infinite, and it is not a lattice. The l.m. numberings form an ideal (w.r.t. reducibility between numberings) inside the class of all (Formula presented.) -computable numberings. We prove that inside this class, the index set of l.m. numberings is (Formula presented.) -complete.
AB - Limitwise monotonic sets and functions constitute an important tool in computable structure theory. We investigate limitwise monotonic numberings. A numbering ν of a family (Formula presented.) is limitwise monotonic (l.m.) if every set (Formula presented.) is the range of a limitwise monotonic function, uniformly in k. The set of all l.m. numberings of S induces the Rogers semilattice (Formula presented.). The semilattices (Formula presented.) exhibit a peculiar behavior, which puts them in-between the classical Rogers semilattices (for computable families) and Rogers semilattices of (Formula presented.) -computable families. We show that every Rogers semilattice of a (Formula presented.) -computable family is isomorphic to some semilattice (Formula presented.). On the other hand, there are infinitely many isomorphism types of classical Rogers semilattices which can be realized as semilattices (Formula presented.). In particular, there is an l.m. family S such that (Formula presented.) is isomorphic to the upper semilattice of c.e. m-degrees. We prove that if an l.m. family S contains more than one element, then the poset (Formula presented.) is infinite, and it is not a lattice. The l.m. numberings form an ideal (w.r.t. reducibility between numberings) inside the class of all (Formula presented.) -computable numberings. We prove that inside this class, the index set of l.m. numberings is (Formula presented.) -complete.
UR - http://www.scopus.com/inward/record.url?scp=85126903044&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85126903044&partnerID=8YFLogxK
U2 - 10.1002/malq.202100077
DO - 10.1002/malq.202100077
M3 - Article
AN - SCOPUS:85126903044
SN - 0942-5616
VL - 68
SP - 213
EP - 226
JO - Mathematical Logic Quarterly
JF - Mathematical Logic Quarterly
IS - 2
ER -