|
Алгебра и логика, 1973, том 12, номер 2, страницы 190–204
(Mi al1376)
|
|
|
|
О $btt$-сводимости
Г. Н. Кобзев
Аннотация:
Доказывается, что если множества $A$ и $B$ нерекурсивны, $\overline{A}$ или
$\overline{B}$ иммунно, $\overline{B}$ рекурсивно-перечислимое (р.п.)
множество и $A\mathop{\leqslant}\limits_{btt}B$, то для подходящего нерекурсивного
р.п. множества $C$ выполняется $C\mathop{\leqslant}\limits_{btt(1)}A$ и
$C\mathop{\leqslant}\limits_{q}B$. Отсюда, используя существование полурекурсивного
р.п. множества минимальной $m$-степени, доказываем существование множества
минимальной $btt$-степени. Доказано также, что $r$-максимальные множества
$A$ и $B$ $btt$-несравнимы, если множества $\overline{A}\cap\overline{B}$ и
$(A\setminus B)\cup(B\setminus A)$ бесконечны. Замечено, что существует
р.п. множество, $btt$-несравнимое с простыми множествами, а рекурсивно
неотделимые р.п. множества не могут $btt$-сводиться к простым множествам.
Поступило: 19.12.1972
Образец цитирования:
Г. Н. Кобзев, “О $btt$-сводимости”, Алгебра и логика, 12:2 (1973), 190–204
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al1376 https://www.mathnet.ru/rus/al/v12/i2/p190
|
Статистика просмотров: |
Страница аннотации: | 72 | PDF полного текста: | 25 | Список литературы: | 1 |
|