Degree spectra of the block relation of 1-computable linear orders
Bikmukhametov R.I.*, Eryashkin M.S.**, Frolov A.N.***
Kazan Federal University, Kazan, 420008 Russia
E-mail: *ravil.bkm@gmail.com, **mikhail.eryashkin@gmail.com, ***andrey.frolov@kpfu.ru
Received June 21, 2017
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 linea r 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.
Keywords: linear orders, 1-computability, block relation, successivity relation, spectra of relations, intrinsically computably enumerable relations
Acknowledgments. 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).
References
1. Ash C.J., Nerode A. Aspects of Effective Algebra. Crossley J.N. (Ed.). Intrinsically Recursive Relations. U.D.A. Book Co., Steel's Greek, Australia, 1981, pp. 26–41.
2. Hirschfeldt D.R. Degree spectra of intrinsically c.e. relations. J. Symb. Logic, 2001, vol. 66, no. 2, pp. 441–469. doi: 10.2307/2695024.
3. Frolov A.N. Linear orderings of low degrees. Sib. Math. J., 2010, vol. 51, no. 5, pp. 913–925.
4. Montalban A. Notes on the jump of a structure. Mathematical Theory and Computational Practice: 5th Conf. on Computability in Europe, CiE 2009. Ambos-Spies K., Lowe B., Merkle W. (Eds.). Berlin, Springer-Verlag, 2009, pp. 372–378. (Lecture Notes in Computer Science, vol. 5635).
5. Remmel J.B. Recursively categorical linear orderings. Proc. Am. Math. Soc., 1981, vol. 83, no. 2, pp. 387–391.
6. Moses M. Relations intrinsically recursive in linear orders. Z. Math. Logik Grundlag. Math., 1986, Bd. 32, S. 467–472.
7. Hirschfeldt D.R. Degree spectra of relations on computable structures in the presence of Δ20 isomorphisms. J. Symb. Logic, 2002, vol. 67, no. 2, pp. 697–720.
8. Frolov A.N. Presentations of the successor relation of computable linear orderings. Russ. Math., 2010. no. 7, pp. 64–74.
9. Chubb J., Frolov A., Harizanov V. Degree spectra of successivities of linear orderings. Arch. Math. Logic, 2009, vol. 48, no. 1, pp. 7–13.
10. Harizanov V. Degree spectrum of a recursive relation on a recursive structure. Ph.D. Thesis. Madison, USA, Univ. of Wis., 1987. 170 p.
11. Moses M. Recursive linear orders with recursive successivities. Ann. Pure Appl. Logic, 1984, vol. 27, no. 3, pp. 253–264. doi: 10.1016/0168-0072(84)90028-9.
12. Frolov A.N. Low linear orderings. J. Logic Comput., 2012, vol. 22, no. 4, pp. 745–754. doi: 10.1093/logcom/exq040.
13. Alaev P.E., Frolov A.N., Thurber J. Computability on linear orderings enriched with predicates. Algebra Logic, 2009, vol. 48, no. 5, pp. 313–320.
14. Frolov A.N. Scattered linear orderings with no computable presentation. Lobachevskii J. Math., 2014, vol. 35, no. 1, pp. 19–22. doi: 10.1134/S199508021401003X.
15. Zubkov M.V. Initial segments of computable linear orders with additional computable predicates. Algebra Logic, 2009, vol. 48, no. 5, pp. 321–329. doi: 10.1007/s10469-009-9068-7.
16. Turner W.P. Computable linear orders and Turing reductions. Master's Thesis. Univ. of Conn., 2012.
17. Bikmukhametov R.I. Initial segments of computable linear orders with computable natural relations. Russ. Math., 2016, vol. 60, no. 6, pp. 12–20. doi: 10.3103/S1066369X16060025.
18. Bikmukhametov R.I. Σ20-initial segments of computable linear orders. Algebra Logic, 2014, vol. 53, no. 3, pp. 266–267. doi: 10.1007/s10469-014-9288-3.
19. Bikmukhametov R.I. Codings on linear orders and algorithmic independence of natural relations. Lobachevskii J. Math., 2014, vol. 35, no. 4, pp. 326–331. doi: 10.1134/S1995080214040131.
20. Bikmukhametov R.I. Algorithmic independence of natural relations on computable linear orders. Uchenye Zapiski Kazanskogo Universiteta, Seriya Fiziko-Matematicheskie Nauki, 2013, vol. 155. no. 3, pp. 80–90. (In Russian)
21. Miller R. The Δ20 spectrum of a linear ordering. J. Symb. Logic, 2001, vol. 66, pp. 470–486.
22. Frolov A.N. Δ20-copies of linear orderings. Algebra Logic, 2006, vol. 45, no. 3, pp. 201–209.
23. Frolov A.N. A note on Δ20-spectra of linear orderings and degree spectra of the successor relation. Russ. Math., 2013, vol. 57, no. 11, pp. 65–68. doi: 10.3103/S1066369X13110078.
24. Frolov A., Harizanov V., Kalimullin I., Kudinov O., Miller R. Spectra of high n and non-low n degrees. J. Logic Comput., 2012, vol. 22, no. 4, pp. 745–754. doi: 10.1093/logcom/exq041.
For citation: Bikmukhametov R.I., Eryashkin M.S., Frolov A.N. Degree spectra of the block relation of 1-computable linear orders. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2017, vol. 159, no. 3, pp. 296–305. (In Russian)
The content is available under the license Creative Commons Attribution 4.0 License.
