RUS  ENG
Full version
JOURNALS // Modelirovanie i Analiz Informatsionnykh Sistem // Archive

Model. Anal. Inform. Sist., 2022 Volume 29, Number 2, Pages 104–114 (Mi mais770)

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.

UDC: 510.676, 519.7

MSC: 03D25

Received: 27.04.2022
Revised: 23.05.2022
Accepted: 25.05.2022

DOI: 10.18255/1818-1015-2022-2-104-114



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024