matatecsМатематика и теоретические компьютерные наукиMathematics and Theoretical Computer Science2949-3919Казанский (Приволжский) федеральный университет10.26907/2949-3919.2024.3.76-91matatecs-55Research ArticleСТАТЬИПлотность вниз в n-вычислимо перечислимых тьюринговых степенях и равномерные конструкцииDownwards density in the n-computably enumerable Turing degrees and the uniform constructionsЯмалеевМ. М.YamaleevM. M.Марс Мансурович Ямалеев

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

Mars Mansurovich Yamaleev

18 Kremlyovskaya str., Kazan 420008

Казанский (Приволжский) федеральный университет, Институт математики и механики им. Н.И. Лобачевского, Научно-образовательный математический центр ПФОРоссияKazan Federal University, N.I. Lobachevsky Institute of Mathematics and Mechanics, Volga Region Mathematical CenterRussian Federation202420102024237691Copyright © Ямалеев М.М., 20242024Ямалеев М.М.Yamaleev M.M.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://matatecs.elpub.ru/jour/article/view/55

В 1993 Р. Доуни и М. Стоб показали, что плотность вниз вычислимо перечислимых (далее, в. п.) тьюринговых степеней в частичном порядке 2-в. п. тьюринговых степеней не может быть доказана при помощи равномерной конструкции. Мы обобщаем этот результат на случай произвольного натурального n > 2 и доказываем, что не существует равномерной конструкции для плотности вниз (n − 1)-в. п. степеней в структуре n-в. п. степеней. Более того, нами показано, что не существует равномерной конструкции для плотности вниз в структуре n-в. п. степеней.

In 1993, R. Downey and M. Stob showed that the downwards density of computably enumerable (c.e.) Turing degrees in the partial 2-c.e. Turing degrees cannot be obtained from a uniform construction. We generalize this result for any n > 2 and show that there is no a uniform construction for the downwards density of (n − 1)-c.e. degrees in the structure of n-c.e. degrees. Moreover, we show that there is no a uniform construction for the downwards density in the n-c.e. degrees.

тьюринговая степеньравномерная конструкцияиерархия Ершоваплотность внизTuring degreeuniform constructionErshov’s heirarchydownwards densityReferencesА.И. Талипова, М.М. Ямалеев, Неравномерность плотности вниз в n-вычислимо перечислимых тьюринговых степенях, Изв. вузов. Матем. (11), 124–131 (2022). DOI: https://doi.org/10.26907/0021-3446-2022-11-124-131A.I. Talipova, M.M. Yamaleev, Nonuniformity of downwards density in the n-computably enumerable Turing degrees, Russian Math. (Iz. VUZ) 66 (11), 110–115 (2022). DOI: https://doi.org/10.3103/S1066369X22110081Р.И. Соар, Вычислимо перечислимые множества и степени, Казан. матем. о-во, Казань, 2000.R.I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in mathematical logic. Springer-Verlag, Berlin, Heidelberg, New York, etc., 1987. URL: https://link.springer.com/book/9783540666813R. Downey, M. Stob, Splitting theorems in recursion theory, Ann. Pure Appl. Log. 65 (1), 1–106 (1993). DOI: https://doi.org/10.1016/0168-0072(93)90234-5R. Downey, M. Stob, Splitting theorems in recursion theory, Ann. Pure Appl. Log. 65 (1), 1–106 (1993). DOI: https://doi.org/10.1016/0168-0072(93)90234-5S.B. Cooper, A.S. Li, Non-uniformity and generalised Sacks splitting, Acta Math. Sinica 18 (2), 327–334 (2002). DOI: https://doi.org/10.1007/s101140100150S.B. Cooper, A.S. Li, Non-uniformity and generalised Sacks splitting, Acta Math. Sinica 18 (2), 327–334 (2002). DOI: https://doi.org/10.1007/s101140100150M.M. Arslanov, I.Sh. Kalimullin, S. Lempp, On Downey’s conjecture, J. Symb. Log. 75 (2), 401–441 (2010). DOI: https://doi.org/10.2178/jsl/1268917488M.M. Arslanov, I.Sh. Kalimullin, S. Lempp, On Downey’s conjecture, J. Symb. Log. 75 (2), 401–441 (2010). DOI: https://doi.org/10.2178/jsl/1268917488

The authors declare that there are no conflicts of interest present.