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

Алгебра и логика, 1984, том 23, номер 4, страницы 395–406 (Mi al1869)

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

О $e$- и $s$-степенях

С. Д. Захаров


Аннотация: Изучается сводимость по перечислимости ($e$-сводимость) в сравнении с другими ($s$-, $p$-, $pc$-, $c$-, $d$-, $pm$-, $m$-) сводимостями. Доказывается, что в каждой $e$-степени содержится по крайней мере две $s$-степени. Устанавливается существование счетной цепи $m$-степеней, упорядоченной по типу натуральных чисел в каждой $e$-степени. Выясняется различие элементарной теории верхней полурешетки всех $s$-степеней с аналогичными теориями $r$-степеней для $r\in\{e, p, pc, c\}$. Из последнего результата выводятся следствия: 1) Элементарная теория рекурсивно-перечислимых $Q$-степеней отлична от аналогичных теорий $r$-степеней для $r\in\{T, wtt\}$. 2) Для каждой $e$-степени $a$ существуют несравнимые квазиминимальные степени $b$ и $c$ такие, что $a\leqslant_lb\oplus c$.

УДК: 510.54

Поступило: 10.04.1984



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


© МИАН, 2024