Generate QR code
Open Access
Subscription Access
A low scattered linear order of rank 2 with no computable copy
https://doi.org/10.26907/0021-3446-2025-10-88-93
Abstract
In R. Downey’s 1998 survey, the question was posed: describe order properties P such that for any low linear order L, if P(L) holds, then L has a computable copy. This paper shows that the property of being scattered is not such a property. Namely, a low scattered linear order of rank 2 with no computable copy is constructed.
About the Author
M. V. Zubkov
Kazan Federal University
Russian Federation
Russian Federation
Maxim V. Zubkov
18 Kremlyovskaya str., Kazan, 420008
References
1. Jockusch C.G., Soare R.I. Degrees of orderings not isomorphic to recursive linear orderings, Ann. Pure Appl. Logic 52 (1–2), 39–61 (1991).
2. Downey R.G., Moses M.F. On choice sets and strongly nontrivial self-embeddings of recursive linear orders, Math. Logic Quart. 35, 237–246 (1989).
3. Downey R.G. Computability theory and linear orderings, Handbook of recursive mathematics, V. 2, 823–976 (North-Holland, Amsterdam, 1998).
4. Фролов А.Н. Delta 0 2-копии линейных порядков, Алгебра и логика 45 (3), 354–370 (2006).
5. Фролов А.Н. Линейные порядки низкой степени, Сиб. матем. журн. 51 (5), 1147–1162 (2010).
6. Алаев П.Е., Тербер Дж., Фролов А.Н. Вычислимость на линейных порядках, обогащенных предикатами, Алгебра и логика 48 (5), 549–563 (2009).
7. Frolov A.N. Low linear orderings, J. Logic and Comput. 22 (4), 745–754 (2012).
8. Зубков М.В. Достаточные условия существования bfzero prime -предельно монотонных функций для вычислимых eta -схожих линейных порядков, Сиб. матем. журн. 58 (1), 107–121 (2017).
9. Фролов А.Н. Вычислимая представимость счетных линейных порядков, Итоги науки и техн. Соврем. матем. и ее прил. Темат. обз. 158, 81–115 (2018).
10. Frolov A., Zubkov M. The simplest low linear order with no computable copies, J. Symb. Logic 89 (1), 97–111 (2024).
11. Зубков М.В. Об одном классе низких линейных порядков, имеющих вычислимые представления, Алгебра и логика 61 (5), 552–570 (2022).
12. Зубков М.В., Фролов А.Н. Вычислимые линейные порядки и предельно монотонные функции, Итоги науки и техн. Соврем. матем. и ее прил. Темат. обз. 157, 70–105 (2018).
13. Rosenstein J.G. Linear orderings (Acad. Press Inc., New York–London, 1982).
14. Kach A., Montalb´an A. Cuts of linear orders, Order 28, 593–600 (2011).
15. Lerman M. On recursive linear orderings, Lect. Notes Math. 859, 132–142 (1981).
16. Frolov A. Scattered linear orderings with no computable presentation, Lobachevskii J. Math. 35 (1), 19–22 (2014).
17. Frolov A., Zubkov M. Low scattered linear orders, J. Logic and Comput. 35 (2), article exae008 (2025).
18. Soare R.I. Recursively enumerable sets and degrees (Springer-Verlag, Heidelberg, 1987).
19. Montalb´an A. Notes on the jump of a structure, J. Logic and Comput. 5635, 372–378 (2009).
Review
For citations:
Zubkov M.V. A low scattered linear order of rank 2 with no computable copy. Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika. 2025;(10):88-93. (In Russ.) https://doi.org/10.26907/0021-3446-2025-10-88-93
Views:
114
Email this article 