Специальная разложимость в 2-в. п. тьюринговых степенях
Аннотация
Рассматривается специальная разложимость 2-в. п. тьюринговых степеней. Под специальным понимается разложение, при котором одна из частей разложения является в. п. степенью. Исследуется вопрос о существовании такого разложения для произвольной 2-в. п. степени, в том числе с избеганием верхнего конуса заданной в. п. степени. Доказывается, что существует 2-в. п. степень, не имеющая специального разложения с избеганием конуса некоторой в. п. степени.
Ключевые слова
тьюринговая степень,
2-в. п. множество,
разложимость,
избегание верхнего конуса,
лахлановское множество
При поддержке: Работа выполнена в рамках реализации программы развития Научно-образовательного математического центра Приволжского федерального округа (соглашение № 075-02-2023-944).
Об авторе
Р. Р. Багавиев
Казанский (Приволжский) федеральный университет, Научно-образовательный математический центр ПФО
Россия
Россия
Рамиль Радифович Багавиев
ул. Кремлевская, д. 18, г. Казань, 420008
Список литературы
1. E.M. Gold, Limiting recursion, J. Symb. Logic 30 (1), 28–48 (1965). DOI: https://doi.org/10.2307/2270580
2. H. Putnam, Trial and error predicates and the solution to a problem of Mostowski, J. Symb. Logic 30 (1), 49–57 (1965). DOI: https://doi.org/10.2307/2270581
3. Ю.Л. Ершов, Об одной иерархии множеств. I, Алгебра и логика 7 (1), 47–74 (1968). URL: http://mi.mathnet.ru/al1139
4. Ю.Л. Ершов, Об одной иерархии множеств. II, Алгебра и логика 7 (4), 15–47 (1968). URL: http://mi.mathnet.ru/al1166
5. Ю.Л. Ершов, Об одной иерархии множеств. III, Алгебра и логика 9 (1), 34–51 (1970). URL: http://mi.mathnet.ru/al1231
6. S.B. Cooper, Degrees of Unsolvability: Ph. D. Thesis, Leicester University, Leicester, England, 1971.
7. М.М. Арсланов, О структуре степеней ниже 0′, Изв. вузов. Матем. (7), 27–33 (1988). URL: http://mi.mathnet.ru/ivm7989
8. S. Cooper, L. Harrington, A. Lachlan, S. Lempp, R. Soare, The d.r.e. degrees are not dense, Ann. Pure Appl. Logic 55 (2), 125–151 (1991). DOI: https://doi.org/10.1016/0168-0072(91)90005-7
9. R.G. Downey, D.r.e. degrees and the nondiamond theorem, Bull. London Math. Soc. 21 (1), 43–50 (1989). DOI: https://doi.org/10.1112/BLMS/21.1.43
10. M.M. Arslanov, I.Sh. Kalimullin, S. Lempp, On Downey’s conjecture, J. Symb. Logic 75 (2), 401–441 (2010). DOI: https://doi.org/10.2178/jsl/1268917488
11. М.М. Арсланов, М.М. Ямалеев, Тьюрингова вычислимость: структурная теория, Итоги науки и техн. Сер. Соврем. матем. и ее прил. Темат. обз. 157, 8–41 (2018). URL: http://mi.mathnet.ru/into405
12. G.E. Sacks, On the degrees less than 0′, Ann. Math. (2) 78 (2), 211–231 (1963). DOI: https://doi.org/10.2307/1970214
13. S.B. Cooper, A splitting theorem for the n-r.e. degrees, Proc. Amer. Math. Soc. 115 (2), 461–471 (1992). DOI: https://doi.org/10.1090/S0002-9939-1992-1105037-0
14. S.B. Cooper, A. Li, Turing Definability in the Ershov Hierarchy, J. London Math. Soc. (2) 66 (3), 461–471 (2002). DOI: https://doi.org/10.1112/S0024610702003691
15. S.B. Cooper, A. Li, Splitting and cone avoidance in the d.c.e. degrees, Sci. in China (Ser. A) 45 (9), 1135–1146 (2002). DOI: http://doi.org/10.1360/02ys9124
16. М.М. Ямалеев, Разложимость 2-вычислимо перечислимых степеней с избеганием конусов, Изв. вузов. Матем. (6), 76–80 (2009). URL: http://mi.mathnet.ru/ivm1475
17. S.B. Cooper, X. Yi, Isolated d.r.e. degrees, Preprint series (Univ. Leeds, Dept. Pure Math.) 17 (1995).
18. Р.И. Соар, Вычислимо перечислимые множества и степени, Изд-во Казан. матем. о-ва, Казань, 2000.
19. S. Ishmukhametov, On the r.e. predecessors of d.r.e. degrees, Arch. Math. Logic 38 (6), 373–386 (1999). DOI: http://doi.org/10.1007/s001530050132
20. J. Liu, G. Wu, M. Yamaleev, Downward density of exact degrees, Lobachevskii J. Math. 36 (4), 389–398 (2015). DOI: http://doi.org/10.1134/S1995080215040095
Рецензия
Для цитирования:
Багавиев Р.Р. Специальная разложимость в 2-в. п. тьюринговых степенях. Математика и теоретические компьютерные науки. 2023;1(3):77-91.
For citation:
Bagaviev R.R. Special splitting in the 2-c.e. Turing degrees. Mathematics and Theoretical Computer Science. 2023;1(3):77-91. (In Russ.)
Просмотров:
117
Послать статью по эл. почте 