Бикмухаметов Р.И., Еряшкин М.С., Фролов А.Н.
Казанский Приволжский федеральный университет, г. Казань, 420008, Россия
Аннотация
Работа посвящена исследованию внутренне вычислимо перечислимых отношений на линейных порядках, таких как отношение соседства на вычислимых линейных порядках и отношение блока на 1-вычислимых линейных порядках. Для удобства изложения линейные порядки, сигнатура которых обогащена отношением соседства, называются 1-вычислимым линейным порядком. Этот термин согласуется с известными результатами.
Доказывается, что для каждого 0'-вычислимого линейного порядка L существует 1-вычислимый линейный порядок, спектр отношения блока которого совпадает с Σ10-спектром линейного порядка L. Спектром отношения блока линейного порядка R называется класс тьюринговых степеней образа отношения блока на вычислимых представлениях R, а Σ10-спектром линейного порядка L – класс тьюринговых перечислимых степеней представлений L.
Этот результат позволяет получить ряд примеров спектров отношения блока 1-вычислимых линейных порядков. В частности, класс всех перечислимых n-высоких степеней и класс всех перечислимых степеней, не являющихся n-низкими, реализуются спектрами отношения блока некоторых 1-вычислимых линейных порядков.
Ключевые слова: линейные порядки, 1-вычислимость, отношение блока, отношение соседства, спектр отношения, внутренне вычислимо перечислимые отношения
Благодарности. Работа выполнена при финансовой поддержке РФФИ (проекты № 15-41-02507 и 15-01-08252). Кроме того, исследования А.Н. Фролова поддержаны РФФИ (проект № 16-31-60077).
Литература
1. Ash C.J., Nerode A. Intrinsically recursive relations // Crossley J.N. (Ed.) Aspects of Effective Algebra. – U.D.A. Book Co., Steel's Greek, Australia, 1981. – P. 26–41.
2. Hirschfeldt D.R. Degree spectra of intrinsically c.e. relations // J. Symb. Logic. – 2001. – V. 66, No 2. – P. 441–469. – doi: 10.2307/2695024.
3. Frolov A.N. Linear orderings of low degrees // Sib. Math. J. – 2010. – V. 51, No 5. – P. 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 / Eds. K. Ambos-Spies, B. Lowe, W. Merkle. – Berlin: Springer-Verlag, 2009. – P. 372–378. (Lecture Notes in Computer Science, V. 5635.)
5. Remmel J.B. Recursively categorical linear orderings // Proc. Am. Math. Soc. – 1981. – V. 83, No 2. – P. 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. – V. 67, No 2. – P. 697–720.
8. Frolov A.N. Presentations of the successor relation of computable linear orderings // Russ. Math. – 2010. – No 7. – P. 64–74.
9. Chubb J., Frolov A., Harizanov V. Degree spectra of successivities of linear orderings // Arch. Math. Logic. – 2009. – V. 48, No 1. – P. 7–13.
10. Harizanov V. Degree spectrum of a recursive relation on a recursive structure: Ph.D. Thesis. – Madison, USA: University of Wisconsin, 1987. – 170 p.
11. Moses M. Recursive linear orders with recursive successivities // Ann. Pure Appl. Logic. – 1984. – V. 27, No 3. – P. 253–264. – doi: 10.1016/0168-0072(84)90028-9.
12. Frolov A.N. Low linear orderings // J. Logic Comput. – 2012. – V. 22, No. 4. – P. 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. – V. 48, No 5. – P. 313–320.
14. Frolov A.N. Scattered linear orderings with no computable presentation // Lobachevskii J. Math. – 2014. – V. 35, No 1. – P. 19–22. – doi: 10.1134/S199508021401003X.
15. Zubkov M.V. Initial segments of computable linear orders with additional computable predicates // Algebra Logic. – 2009. – V. 48, No 5. – P. 321–329. – doi: 10.1007/s10469-009-9068-7.
16. Turner W.P. Computable linear orders and Turing reductions: Master's
Поступила в редакцию
21.06.17
Бикмухаметов Равиль Ильдарович, кандидат физико-математических наук, научный сотрудник кафедры алгебры и математической логики
Казанский (Приволжский) федеральный университет
ул. Кремлевская, д. 18, г. Казань, 420008, Россия
E-mail: ravil.bkm@gmail.com
Еряшкин Михаил Сергеевич, кандидат физико-математических наук, научный сотрудник кафедры алгебры и математической логики
Казанский (Приволжский) федеральный университет
ул. Кремлевская, д. 18, г. Казань, 420008, Россия
E-mail: mikhail.eryashkin@gmail.com
Фролов Андрей Николаевич, доктор физико-математических наук, старший научный сотрудник кафедры алгебры и математической логики
Казанский (Приволжский) федеральный университет
ул. Кремлевская, д. 18, г. Казань, 420008, Россия
E-mail: andrey.frolov@kpfu.ru, a.frolov.kpfu@gmail.com
Для цитирования: Бикмухаметов Р.И., Еряшкин М.С., Фролов А.Н. Спектр отношения блока 1-вычислимых линейных порядков // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2017. – Т. 159, кн. 3. – С. 296–305.
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)
Контент доступен под лицензией Creative Commons Attribution 4.0 License.