|
Discrete mathematics in relation to computer science
Enumeration degrees of the bounded sets
B. Y. Solon Ivanovo State University, 39 Ermaka str, Ivanovo 153025, Russia
Abstract:
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.
Received: 27.04.2022 Revised: 23.05.2022 Accepted: 25.05.2022
Citation:
B. Y. Solon, “Enumeration degrees of the bounded sets”, Model. Anal. Inform. Sist., 29:2 (2022), 104–114
Linking options:
https://www.mathnet.ru/eng/mais770 https://www.mathnet.ru/eng/mais/v29/i2/p104
|
|