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

Алгебра и логика, 1973, том 12, номер 4, страницы 433–444 (Mi al1392)

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

О $btt$-сводимости. II

Г. Н. Кобзев


Аннотация: Доказано, всякая нерекурсивная рекурсивно-перечислимая (р.п.) $T$-степень содержит бесконечное число $btt$-несравнимых простых не гиперпростых множеств минимальной $btt$-степени. Если $A$ — р.п. множество, то найдутся р.п. множества $B_{i},\,i\geqslant 0$, такие, что $A\leqslant_{q}B_{i}$, $A\equiv_{T}B_{i}$, $B_{i}\nleqslant_{btt}B_{j}$ для $i\neq j$. Найдено р.п. множество $A$ со свойством $(\forall B)(B\equiv_{btt}A\Rightarrow B<_{btt}B^{\omega}\ \&\ B<_{btt}{}^{\omega}B)$. Замечено, если $A$ — $r$-максимальное множество, то $(\forall B)(B\equiv_{btt}A\Rightarrow A\leqslant_{m}B\vee A\leqslant_{m}\overline{B})$. Если же $A$ и $B$ — максимальные множества, то из $A\equiv_{tt}B$ следует $A\equiv_{m}B$.

УДК: 517.11:518.5

Поступило: 18.06.1973



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


© МИАН, 2024