RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирский математический журнал // Архив

Сиб. матем. журн., 1976, том 17, номер 5, страницы 1014–1022 (Mi smj4047)

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

О минимальных $1$-степенях и табличной сводимости

А. Н. Дёгтев


Аннотация: Строится псевдокреативное множество $U$ со свойством
$$ (\forall B_{\text{р.п.}})[U\subset B\&B\setminus U\text{ не р.п. }) \Rightarrow(\exists R\text{ рекурс. })(U\subset R\subset B)]. $$
Оно имеет минимальную 1-степень, но не является $\eta$-замкнутым относительно любой позитивной максимальной эквивалентности $\eta$. Затем доказывается, что каждая р.п. некурсивная тьюрингова степень содержит минимальную р.п. $m$-степень, состоящую из единственной 1-степени. Показывается, что если $A$ и $B$ – р.п. множества такие, что $B$ некреативно, $B{\not\leq}_{tt}A$, то найдется р.п. $C$ такое, что $C$ $tt$-несравнимо с $B$ и $A<_{tt}C$.

УДК: 517.11+518.5

Статья поступила: 01.03.1975


 Англоязычная версия: Siberian Mathematical Journal, 1976, 17:5, 751–757

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


© МИАН, 2024