Isolation from Side in 2-Computably Enumerable Degrees
- PDF / 143,652 Bytes
- 4 Pages / 612 x 792 pts (letter) Page_size
- 2 Downloads / 146 Views
olation from Side in 2-Computably Enumerable Degrees M. M. Yamaleev1* (submitted by M. M. Arslanov) 1 Kazan Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia
Received March 26, 2020; revised March 26, 2020; accepted June 29, 2020
Abstract—In this work we consider isolation from side in different degree structures, in particular, in the 2-computably enumerable wtt-degrees and in low Turing degrees. Intuitively, a 2-computably enumerable degree is isolated from side if all computably enumerable degrees from its lower cone are bounded from above by some computably enumerable degree which is incomparable with the given one. It is proved that any properly 2-computably enumerable wtt-degree is isolated from side by some computable enumerable wtt-degree. Also it is shown that the same result holds for the low 2-computable enumerable Turing degrees. DOI: 10.3103/S1066369X20080095 Key words: 2-computably enumerable set, wtt-degree, Turing degree, isolation from side.
INTRODUCTION This work is devoted to investigation of structural properties of computably enumerable (further, c. e.) and 2-c. e. degrees of unsolvability. In the work we consider Turing and wtt-degrees of unsolvability, and also isolation from side property, which is a variant of isolation for 2-c. e. degrees. Isolated 2-c. e. Turing degrees were first considered in the work by B. Cooper and X. Yi [1], where they proved that isolated 2-c. e. Turing degrees exist. Intuitively, it is a 2-c. e. degree d for which there exists a c. e. degree c < d such that there is no c. e. degree strictly between d and c. It is easy to see that the degree c in this case is maximal (and even greatest) c. e. degree strictly below d. Also by the well-known Sacks Density Theorem [2], the concept of isolation can be applied only for properly 2-c. e. degrees (i. e. degrees that do not contain c. e. sets). Isolated 2-c. e. degrees were found to be useful in the series of constructions (e.g., see [3]) and allowed to employ properness of considered 2-c. e. degrees. However, unfortunately, it turned out that non-isolated properly 2-c. e. degrees existed too, and, moreover, such degrees were as “common” as isolated ones (see [4]–[6]). Thus, we cannot say that the isolation property can characterize properly 2-c. e. degrees. However, such characterization followed by interpretation of c. e. degrees in the structure of 2-c. e. degrees in the language of partial ordering solves in a natural way the well-known problem of definability of c. e. degrees within 2-c. e. degrees (the problem was stated in a series of works, e. g., in [7] and [8]). The searching of characteristic properties of properly 2-c. e. degree was a motivation for this work, and, following the program stated in [9], we show in the current paper that the property of isolation from side holds for any properly 2-c. e. Turing degree as well as for any properly 2-c. e. wtt-degree. Isolation from side was used implicitly in [10] and [11], and it was distinguished and defined in [12]. In this work we use the following Defi
Data Loading...
