Degree spectra of the block relation of 1-computable linear orders
R. I. Bikmukhametov, M. S. Eryashkin, A. Frolov · DOAJ (DOAJ: Directory of Open Access Journals) · 2017
In this paper, we study the intrinsically computably enumerable relations on linear orderings, such as the successor relation on computable linear orderings and the block relation on 1-computable linear orderings. For ease of reading, the linear ordering, in which the signature is enriched with the successor relation, is called 1-computable linear ordering. This notion is consistent with the known results. We have proved that for any 0'-computable linear ordering L there exists a 1-computable linear ordering, in which the degree spectrum of the block relation coincides with the Σ10-spectrum of the linear ordering L. The degree spectrum of the block relation of a linear ordering R is called the class of Turing degrees of the images of the block relation on computable presentations of R; and Σ10-spectrum of a linear ordering L is called the class of Turing enumerable degrees of L. This obtained result provides a number of examples of the spectra of the block relation of 1-computable linear orderings. In particular, the class of all enumerable high n degrees and the class of all enumerable non-low n degrees are realized by the spectra of the block relation of some 1-computable linear orderings.