This article is cited in
1 paper
Degree spectra of the block relation of $1$-computable linear orders
R. I. Bikmukhametov,
M. S. Eryashkin,
A. N. Frolov Kazan Federal University, Kazan, 420008 Russia
Abstract:
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
$\mathbf0'$-computable linear ordering
$L$ there exists a
$1$-computable linear ordering, in which the degree spectrum of the block relation coincides with the
$\Sigma_1^0$-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
$\Sigma_1^0$-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.
Keywords:
linear orders, $1$-computability, block relation, successivity relation, spectra of relations, intrinsically computably enumerable relations.
UDC:
510.5 Received: 21.06.2017