|
Алгебра и логика, 1972, том 11, номер 3, страницы 257–269
(Mi al1339)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 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}$.
Поступило: 25.12.1971
Образец цитирования:
А. Н. Дёгтев, “Наследственные множества и табличная сводимость”, Алгебра и логика, 11:3 (1972), 257–269
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al1339 https://www.mathnet.ru/rus/al/v11/i3/p257
|
Статистика просмотров: |
Страница аннотации: | 95 | PDF полного текста: | 31 |
|