Enumeration degrees of the bounded sets

B. Y. Solon

Modelirovanie i analiz informacionnyh sistem, Tome 29 (2022) no. 2, pp. 104-114

Résumé

The term “total enumeration degree” is related to the fact that the $e$-degree is total if and only if it contains a graph of some total function. In a number of works by the author and a group of mathematicians from the University of Wisconsin-Madison, the so-called “graph-cototal enumeration degrees” were considered, i.e. $e$-degrees containing the complement of the graph of some total function $f(x)$. In this article, the next step is taken – the enumeration degrees of sets bounded from above or below by a graph of a total function are considered. More precisely, the set $A$ is bounded from above if $A=\{\langle x,y\rangle:y f(x)\}$ for some total function $f(x)$ and the set $A$ is bounded from below if $A=\{\langle x,y\rangle:y > f(x)\}$ for some total function $f(x)$. The article presents a number of results showing the existence of nontotal enumeration degrees containing bounded sets, and the constructed $e$-degrees are quasi-minimal. An important result is the one stating that bounded sets have the Friedberg property related to the jump inversion.

Détail

Keywords: enumeration degrees, quasi-minimal enumeration degrees, bounded sets.