RUS  ENG
Full version
JOURNALS // Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki // Archive

Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2017 Volume 159, Book 3, Pages 296–305 (Mi uzku1409)

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



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024