Rogers semilattices of limitwise monotonic numberings

Nikolay Bazhenov, Manat Mustafa, Zhansaya Tleuliyeva

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)213-226
Number of pages14
JournalMathematical Logic Quarterly
Volume68
Issue number2
DOIs
Publication statusAccepted/In press - 2022

ASJC Scopus subject areas

  • Logic

Fingerprint

Dive into the research topics of 'Rogers semilattices of limitwise monotonic numberings'. Together they form a unique fingerprint.

Cite this