Аннотация:
В 1993 г. Р. Доуни и М. Стоб показали, что плотность вниз вычислимо перечислимых (в.п.) тьюринговых степеней в частичном порядке 2-в.п. тьюринговых степеней не может быть доказана при помощи равномерной конструкции. В текущей работе этот результат обобщается на случай произвольного натурального n>2 и показывается, что не существует равномерной конструкции для плотности вниз (n−1)-в.п. степеней в структуре n-в.п. степеней. Более того, показывается, что не существует равномерной конструкции для плотности вниз в структуре n-в.п. степеней.
Ключевые слова:
тьюринговая степень, равномерная конструкция, иерархия Ершова, плотность вниз.
Работа поддержана грантом Российского научного фонда и Кабинета Министров Республики Татарстан (проект № 22-21-20024, https://rscf.ru/project/22-21-20024/) и выполнена в рамках реализации программы развития Научно-образовательного математического центра Приволжского федерального округа (соглашение № 075-02-2022-882).
Поступила: 27.09.2022 Исправленный вариант: 27.09.2022 Принята к публикации: 28.09.2022