Special splitting in the 2-c.e. Turing degrees
Abstract
We study a special splitting of 2-c.e. Turing degrees. The special splitting means a splitting which has a c.e. splitting part. We investigate an existence of a special splitting, including a special splitting with upper cone avoidance. We prove that there exists a 2-c.e. degree without special splitting and that there is a 2-c.e. degree which has no special splitting avoiding upper cone of some incomputable c.e. degree.
Supporting agencies: The work is performed under the development program of Volga Region Mathematical Center (agreement no. 075-02-2023-944).
About the Author
R. R. Bagaviev
Kazan Federal University, Volga Region Mathematical Center
Russian Federation
Russian Federation
Ramil Radifovich Bagaviev
18 Kremlyovskaya str., Kazan 420008
References
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. Yu.L. Ershov, A certain hierarchy of sets. I, Algebra Logika 7 (1), 47–74 (1968) [in Russian]. URL: http://mi.mathnet.ru/al1139
4. Yu.L. Ershov, A certain hierarchy of sets. II, Algebra Logika 7 (4), 15–47 (1968) [in Russian]. URL: http://mi.mathnet.ru/al1166
5. Yu.L. Ershov, A certain hierarchy of sets. III, Algebra Logika 9 (1), 34–51 (1970) [in Russian]. URL: http://mi.mathnet.ru/al1231
6. S.B. Cooper, Degrees of Unsolvability: Ph. D. Thesis, Leicester University, Leicester, England, 1971.
7. М.М. Arslanov, The lattice of the degrees below 0′, Soviet Math. (Iz. VUZ) 32 (7), 43–53 (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. М.М. Arslanov, М.М. Yamaleev, Turing Computability: Structural Theory, J. Math. Sciences 256 (6), 1–33 (2021). DOI: http://doi.org/10.1007/s10958-021-05418-y
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. М.М. Yamaleev, Splitting in 2-computably enumerable degrees with avoiding cones, Russ. Math. 53 (6), 63–66 (2009). DOI: https://doi.org/10.3103/S1066369X09060127
17. S.B. Cooper, X. Yi, Isolated d.r.e. degrees, Preprint series (Univ. Leeds, Dept. Pure Math.) 17 (1995).
18. R. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN: 3-540-15299-7
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).
Review
For citations:
Bagaviev R.R. Special splitting in the 2-c.e. Turing degrees. Mathematics and Theoretical Computer Science. 2023;1(3):77-91. (In Russ.)
Views:
120
Email this article 