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

Изв. вузов. Матем., 2014, номер 2, страницы 77–81 (Mi ivm8875)

Эта публикация цитируется в 1 статье

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

Определимые отношения в структурах тьюринговых степеней

М. М. Арсланов

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

Аннотация: В работе исследована определимость классов $n$-вычислимо перечислимых (в.п.) множеств и степеней в разностной иерархии Ершова. Установлена определимость в.п. множеств на языке $\subseteq$ на всех конечных уровнях иерархии, а также определимость классов $m$-в.п. степеней во всех более высоких уровнях иерархии. Кроме того, для каждого уровня иерархии найден определимый в нем нетривиальный класс $m$-в.п. степеней.

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

УДК: 510.54

Поступила: 14.08.2013


 Англоязычная версия: Russian Mathematics (Izvestiya VUZ. Matematika), 2014, 58:2, 64–67

Реферативные базы данных:


© МИАН, 2024