RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия высших учебных заведений. Математика // Архив

Изв. вузов. Матем., 2022, номер 11, страницы 124–131 (Mi ivm9832)

Краткие сообщения

Неравномерность плотности вниз в $n$-вычислимо перечислимых тьюринговых степенях

А. И. Талипова, М. М. Ямалеев

Казанский федеральный университет, ул. Кремлевская, д. 18, г. Казань, 420008, Россия

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

Ключевые слова: тьюринговая степень, равномерная конструкция, иерархия Ершова, плотность вниз.

УДК: 510.532

Поступила: 27.09.2022
Исправленный вариант: 27.09.2022
Принята к публикации: 28.09.2022

DOI: 10.26907/0021-3446-2022-11-124-131


 Англоязычная версия: Russian Mathematics (Izvestiya VUZ. Matematika), 2022, 66:11, 110–115


© МИАН, 2024