RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 1972, том 11, номер 3, страницы 257–269 (Mi al1339)

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

Наследственные множества и табличная сводимость

А. Н. Дёгтев


Аннотация: Доказано, что каждая тьюрингова степень, содержащая гипериммунное (соответственно, р.п. нерекурсивное) множество, содержит счётное число попарно $tt$-несравнимых (р.п.) множеств. Замечено, что простое негиперпростое множество $tt$-несводимо к р.п. множеству с ретрассируемым дополнением, а точная нижняя грань $tt$-степеней двух р.п. множеств с ретрассируемыми дополнениями различных тьюринговых степеней есть рекурсивная $tt$-степень.
Выяснены также некоторые свойства наследственных множеств. В частности, если $A$ - наследственное множество и $\overline{A}$ - дополнение $A$, то
1) $A$ простое $\Longrightarrow$ $\overline{A}$ интерсводимое;
2) $\overline{A}$ негипергипериммунное;
3) $\overline{A}$ регрессивное $\Longrightarrow$ $A\in\Pi^{0}_{1}\cup \Sigma^{0}_{1}$.

УДК: 517.11:518.5

Поступило: 25.12.1971



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


© МИАН, 2024