Enumeration Degrees of the Bounded Sets
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 enume...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2022-06-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1649 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1818-1015 2313-5417 |