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

Алгебра и логика, 1974, том 13, номер 1, страницы 22–25 (Mi al1411)

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

О полной $btt$-степени

Г. Н. Кобзев


Аннотация: По определению, $A\leqslant_{bd}B$, если найдутся общерекурсивная функция $f(x)$ и число $k$ такие, что $(\forall x)(|D_{f(x)}|\leqslant k\ \&\ (x\in A\Leftrightarrow B\cap D_{f(x)}\neq\varnothing))$ (здесь $D_{x}$ — стандартная нумерация конечных множеств). Если $A\leqslant_{bd}B$ и $B\leqslant_{bd}A$, то $A\equiv_{bd}B$. Доказывается, что если $K$ — креативное множество, $A$ — рекурсивно-перечислимое множество, то условия $K\equiv_{btt}A$ и $K\equiv_{bd}A$ эквивалентны. Из $K\equiv_{bd}A$ следует, что ${}^{k+1}A\leqslant_{m}{}^{k}A$ для некоторого $k$. Однако существует такое $A$, что $K\equiv_{bd}A$ и $(\forall k)(A^{k}<_mA^{k+1})$.

УДК: 518.5

Поступило: 11.12.1973



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


© МИАН, 2024