Rogers semilattices of limitwise monotonic numberings
Bazhenov N. Mustafa M. Tleuliyeva Z.
May 2022John Wiley and Sons Inc
Mathematical Logic Quarterly
2022#68Issue 2213 - 226 pp.
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.
Text of the article Перейти на текст статьи
Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., Novosibirsk, 630090, Russian Federation
Department of Mathematics, School of Sciences and Humanities, Nazarbayev University, 53 Qabanbay Batyr Avenue, Nur-Sultan, 010000, Kazakhstan
Sobolev Institute of Mathematics
Department of Mathematics
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026