On a computable presentation of low linear orders

A.N. Frolov

Kazan Federal University, Kazan, 420008 Russia

E-mail:  andrey.frolov@kpfu.ru

Received September 12, 2017

Full text PDF

Abstract

R. Downey in the review paper of 1998 stated the research program on studying and des­cription of sufficient conditions of computable representability of linear orders, namely, the problem of des­cription of the order type P such that, for any low linear order L, from P(L) it follows that L has a computable presentation.

 This paper is a part of the program initiated by R. Downey. We have shown that each low linear order with η condensation and no infinite strongly η-like interval has a computable presentation via a 0"-computable isomorphism. The countable linear order is called η-like if there exists some natural number k such that each maximal block of the order has power no more than k.

 We have also proven that the above-discussed result does not hold for 0'-computable isomorphism instead of 0"-computable. Namely, we have constructed a low linear order L with η condensation and no infinite strongly η-like interval such that L is not 0'-computably isomorphic to a computable one.

Keywords: linear order, computable presentation, low degree, strongly η-like linear order

Acknowledgments. This study was supported by the Russian Foundation for Basic Research (project no. 16-31-60077).

References

1. Soare R.I. Recursively Enumerable Sets and Degrees. Heidelberg, Springer-Verlag, 1987. XVIII, 437 p.

2. Downey R.G., Jockusch C.G.,Jr. Every low Boolean algebra is isomorphic to a recursive one. Proc. Am. Math. Soc., 1994, vol. 122, no. 3, pp. 871–880.

3. Thurber J. Every low₂ Boolean algebra has a recursive copy. Proc. Am. Math. Soc., 1995, vol. 123, no. 12, pp. 3859–3866.

4. Knight J.F., Stob M. Computable Boolean algebras. J. Symb. Logic, 2000, vol. 65, no. 4, pp. 1605–1623. doi: 10.2307/2695066.

5. Harris K., Montalban A. Boolean algebra approximations. Trans. Am. Math. Soc., 2014, vol. 366, no. 10, pp. 5223–5256. doi: 10.1090/S0002-9947-2014-05950-3.

6. Jockusch C.G., Soare R.I. Degrees of orderings not isomorphic to recursive linear orderings. Ann. Pure Appl. Logic, 1991, vol. 52, nos. 1–2, pp. 39–64. doi: 10.1016/0168-0072(91)90038-N.

7. Downey R.G., Moses M.F. On choice sets and strongly nontrivial self-embeddings of recursive linear orderings. Z. Math. Logik Grund. Math., 1989, Bd. 35, S. 237–246.

8. Downey R.G. Handbook of Recursive Mathematics. Computability Theory and Linear Orderings. Ershov Yu.L., Goncharov S.S., Nerode A., Remmel J.B. (Eds.). Amsterdam, Elsevier, 1998, pp. 823–976.

9. Frolov A.N. -copies of linear orderings. Algebra Logic, 2006, vol. 45, no. 3, pp. 201–209. doi: 10.1007/s10469-006-0017-4.

10. Frolov A.N. Linear orderings of low degree. Sib. Math. J., 2010, vol. 51, no. 5, pp. 913–925. doi: 10.1007/s11202-010-0091-7.

11. Frolov A.N. Low linear orderings. J. Logic Comput., 2012, vol. 22, no. 4, pp. 745–754. doi: 10.1093/logcom/exq040.

12. Frolov A. Scattered linear orderings with no computable presentation. Lobachevskii J. Math., 2014, vol. 35, no. 1, pp. 19–22. doi: 10.1134/S199508021401003X.

13. Kach A., Montalbn A. Cuts of linear orders. Order, 2011, vol. 28, no. 3, pp. 593–600. doi: 10.1007/s11083-010-9194-9.

14. 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. doi: 10.1007/s10469-009-9067-8.

15. Frolov A., Zubkov M. Increasing -representable degrees. Math. Logic Q., 2009, vol. 55, no. 6, pp. 633–636. doi: 10.1002/malq.200810031.

16. Kach A. Computable shuffle sums of ordinals. Arch. Math. Logic, 2008, vol. 47, no. 3, pp. 211–219. doi: 10.1007/s00153-008-0077-3.

17. Montalban A. Mathematical Theory and Computational Practice. CiE 2009. Lecture Notes in Computer Science. Ambos-Spies K., Lowe B., Merkle W. (Eds.). Notes on the Jump of a Structure. Vol. 5635. Berlin, Heidelberg, Springer, 2009, pp. 372–378.

For citation: Frolov A.N. On a computable presentation of low linear orders. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2017, vol. 159, no. 4, pp. 518–528. (In Russian)

The content is available under the license Creative Commons Attribution 4.0 License.