Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

This article is cited in 1 scientific paper (total 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
Full-text PDF (669 kB) Citations (1)
References:
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.
Funding agency Grant number
Russian Foundation for Basic Research 15-41-02507
15-01-08252
16-31-60077
This study was supported by the Russian Foundation for Basic Research (projects nos. 15-41-02507 and 15-01-08252). A. N. Frolov's investigations were supported by the Russian Foundation for Basic Research (project no. 16-31-60077).
Received: 21.06.2017
Bibliographic databases:
Document Type: Article
UDC: 510.5
Language: Russian
Citation: R. I. Bikmukhametov, M. S. Eryashkin, A. N. Frolov, “Degree spectra of the block relation of $1$-computable linear orders”, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 159, no. 3, Kazan University, Kazan, 2017, 296–305
Citation in format AMSBIB
\Bibitem{BikEryFro17}
\by R.~I.~Bikmukhametov, M.~S.~Eryashkin, A.~N.~Frolov
\paper Degree spectra of the block relation of $1$-computable linear orders
\serial Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki
\yr 2017
\vol 159
\issue 3
\pages 296--305
\publ Kazan University
\publaddr Kazan
\mathnet{http://mi.mathnet.ru/uzku1409}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3764049}
\elib{https://elibrary.ru/item.asp?id=32265837}
Linking options:
  • https://www.mathnet.ru/eng/uzku1409
  • https://www.mathnet.ru/eng/uzku/v159/i3/p296
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki
    Statistics & downloads:
    Abstract page:346
    Full-text PDF :148
    References:50
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024