Geodesic
Enumeration degrees of the bounded sets
Modelirovanie i analiz informacionnyh sistem, Tome 29 (2022) no. 2, pp. 104-114 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: enumeration degrees, quasi-minimal enumeration degrees, bounded sets. 
@article{MAIS_2022_29_2_a2,
     author = {B. Y. Solon},
     title = {Enumeration degrees of the bounded sets},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {104--114},
     year = {2022},
     volume = {29},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2022_29_2_a2/}
}
TY  - JOUR
AU  - B. Y. Solon
TI  - Enumeration degrees of the bounded sets
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2022
SP  - 104
EP  - 114
VL  - 29
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MAIS_2022_29_2_a2/
LA  - ru
ID  - MAIS_2022_29_2_a2
ER  - 
%0 Journal Article
%A B. Y. Solon
%T Enumeration degrees of the bounded sets
%J Modelirovanie i analiz informacionnyh sistem
%D 2022
%P 104-114
%V 29
%N 2
%U http://geodesic.mathdoc.fr/item/MAIS_2022_29_2_a2/
%G ru
%F MAIS_2022_29_2_a2
B. Y. Solon. Enumeration degrees of the bounded sets. Modelirovanie i analiz informacionnyh sistem, Tome 29 (2022) no. 2, pp. 104-114. http://geodesic.mathdoc.fr/item/MAIS_2022_29_2_a2/

[1] U. Andrews, H. Ganchev, R. Kuyper, S. Lempp, J. Miller, A. Soskova, M. Soskova, “On cototality and the skip operator in the enumeration degrees”, Transactions of the American Mathematical Society, 372:3 (2019), 1631–1670 | DOI | MR | Zbl

[2] B. Solo, S. Rozhkov, “Enumeration degrees of the bounded total sets”, in International Conference on Theory and Applications of Models of Computation, Springer, 2006, 737–745 | DOI | MR | Zbl

[3] S. Rozhkov, “Properties of e-degrees of the bounded total sets”, Automatic Control and Computer Sciences, 44:7 (2010), 452–454 | DOI

[4] H. Rogers Jr, Theory of recursive functions and elfective computability, McGraw-Hill, New York, 1967 | MR

[5] M. G. Rosinas, “Chastichnie stepeni i r-stepeni”, Siberian Mathematical Journal, 15:6 (1974), 1323–1331

[6] S. B. Cooper, “Partial degrees and the density problem. Part 2: The enumeration degrees of the $\Sigma2$ sets are dense”, The Journal of symbolic logic, 49:2 (1984), 503–513 | DOI | MR | Zbl

[7] M. G. Rosinas, Operacia skachka dlja nekotorih vidov svodimosti, VINITI Dep 3185-76

[8] K. McEvoy, “Jumps of quasi-minimal enumeration degrees”, The Journal of symbolic logic, 50:3 (1985), 839–848 | DOI | MR | Zbl

[9] J. Case, “Enumeration reducibility and partial degrees”, Annals of mathematical logic, 2:4 (1971), 419–439 | DOI | MR | Zbl