Rogers semilattices of limitwise monotonic numberings

2022

Closed access Metadata (CSL-JSON)
DOI 10.1002/malq.202100077
Data confidence 70 medium
How this score is calculated

It is built from checkable properties of the record itself: whether the article has a DOI, how many independent sources confirmed its data, whether the required fields are filled in, and how recent the latest confirmation is. Disagreement between sources and a missing identifier lower it. A value of 80 or above means the record was published without further checking; 60 to 79 means it is published at reduced confidence, with a manual check advisable. A record verified by an editor by hand is never pushed below 90 by a recalculation. This scores our data about the article, not the article itself.

Abstract

Abstract Limitwise monotonic sets and functions constitute an important tool in computable structure theory. We investigate limitwise monotonic numberings. A numbering ν of a family is limitwise monotonic (l.m.) if every set is the range of a limitwise monotonic function, uniformly in k. The set of all l.m. numberings of S induces the Rogers semilattice . The semilattices exhibit a peculiar behavior, which puts them in‐between the classical Rogers semilattices (for computable families) and Rogers semilattices of ‐computable families. We show that every Rogers semilattice of a ‐computable family is isomorphic to some semilattice . On the other hand, there are infinitely many isomorphism types of classical Rogers semilattices which can be realized as semilattices . In particular, there is an l.m. family S such that 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 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 ‐computable numberings. We prove that inside this class, the index set of l.m. numberings is ‐complete.