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

Full text PDF

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 Σ₁⁰-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 Σ₁⁰-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 Δ₂⁰ 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. Σ₂⁰-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 Δ₂⁰ spectrum of a linear ordering. J. Symb. Logic, 2001, vol. 66, pp. 470–486.

22. Frolov A.N. Δ₂⁰-copies of linear orderings. Algebra Logic, 2006, vol. 45, no. 3, pp. 201–209.

23. Frolov A.N. A note on Δ₂⁰-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.