Об одном вычислимом представлении низких линейных порядков

Фролов А.Н.

Казанский Приволжский федеральный университет, г. Казань, 420008, Россия

Полный текст PDF

Аннотация

В 1998 г. в своей обзорной работе Р. Доуни сформулировал план исследования и описания достаточных условий вычислимой представимости линейных порядков в виде проблемы описания порядковых свойств P таких, что для любого низкого линейного порядка L из выполнимости условия P(L) следует существование вычислимого представления L.

 Настоящая работа содержит исследования в рамках плана Р. Доуни. В работе показано, что каждый низкий линейный порядок, фактор-порядок (другими словами, конденсация) которого есть η (порядковый тип естественного упорядочения натуральных чисел) и который не содержит бесконечного сильно η-схожего интервала, имеет вычислимое представление посредством 0"-вычислимого изоморфизма. Счетный линейный порядок называется сильно η-схожим, если существует некоторое натуральное число k такое, что каждый максимальный блок порядка имеет мощность не больше k.

 В работе доказано также, что вышеприведенный результат не верен для 0'-вычислимого изоморфизма вместо 0"-вычислимого, а именно: построен низкий линейный порядок, конденсация которого есть η и который не содержит бесконечного сильно η-схожего интервала, не имеющий вычислимого представления посредством 0'-вычислимого изоморфизма.

Ключевые слова: линейный порядок, вычислимое представление, низкая степень, сильно η-схожий линейный порядок

Литература

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. – V. 122, No 3. – P. 871–880.

3. Thurber J. Every low₂ Boolean algebra has a recursive copy // Proc. Am. Math. Soc. – 1995. – V. 123, No 12. – P. 3859–3866.

4. Knight J.F., Stob M. Computable Boolean algebras // J. Symb. Logic. – 2000. – V. 65, No 4. – P. 1605–1623. – doi: 10.2307/2695066.

5. Harris K., Montalban A. Boolean algebra approximations // Trans. Am. Math. Soc. – 2014. – V. 366, No 10. – P. 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. – V. 52, No 1–2. – P. 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. Computability theory and linear orderings // Handbook of Recursive Mathematics / Eds. Yu.L. Ershov, S.S. Goncharov, A. Nerode, J.B. Remmel. – Amsterdam: Elsevier, 1998. – P. 823–976.

9. Frolov A.N. Δ⁰₂-copies of linear orderings // Algebra logic. – 2006. – V. 45, No 3. – P. 201–209. – doi: 10.1007/s10469-006-0017-4.

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

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

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

13. Kach A., Montalbán A. Cuts of linear orders // Order. – 2011. – V. 28, No 3. – P. 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. – V. 48, No 5. – P. 313–320. – doi: 10.1007/s10469-009-9067-8.

15. Frolov A., Zubkov M. Increasing η-representable degrees // Math. Logic Q. – 2009. – V. 55, No 6. – P. 633–636. – doi: 10.1002/malq.200810031

16. Kach A. Computable shuffle sums of ordinals // Archive for Math. Logic. – 2008. – V. 47, No 3. – P. 211–219. – doi 10.1007/s00153-008-0077-3.

17. Montalban A. Notes on the jump of a structure // Ambos-Spies K., Lowe B., Merkle W. (Eds.) Mathematical Theory and Computational Practice. CiE 2009. Lecture Notes in Computer Science, V. 5635. – Berlin, Heidelberg: Springer, 2009. – P. 372–378.

Поступила в редакцию

12.09.17

Фролов Андрей Николаевич, доктор физико-математических наук, старший научный сотрудник кафедры алгебры и математической логики

Казанский (Приволжский) федеральный университет

ул. Кремлевская, д. 18, г. Казань, 420008, Россия

E-mail:  andrey.frolov@kpfu.ru,  a.frolov.kpfu@gmail.com

Для цитирования: Фролов А.Н. Об одном вычислимом представлении низких линейных порядков // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2017. – Т. 159, кн. 4. – С. 518–528.

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)

Контент доступен под лицензией Creative Commons Attribution 4.0 License.