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

Алгебра и логика, 1988, том 27, номер 3, страницы 343–358 (Mi al2020)

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

Индексные множества фактор-объектов нумерации Поста

В. Л. Селиванов


Аннотация: Изучаются факторизации нумерации Поста $\pi$ по некоторым отношениям эквивалентности на рекурсивно-перечислимых множествах. Оказалось, что при этом важную роль играют релятивизации понятий предполноты, полноты и $2$-полноты. Например, если $\sim$ — нетривиальное отношение конгруэнтности на решетке рекурсивно-перечислимых множеств, то факторизация $\widetilde\pi$ — универсальная $2$-полная нумерация относительно $\varnothing'$. Если $\sim$ — отношение $T$-эквивалентности, то $\widetilde\pi$ — универсальная полная нумерация относительно $\varnothing''$. Если $\sigma\sim\tau$ означает $\exists n \,\left(\sigma^{(n)}\equiv_T\tau^{(n)}\right)$, то $\widetilde\pi$ — универсальная предполная нумерация относительно $\varnothing^{(\omega)}$. Приводится также ряд следствий об индексных множествах таких факторизации.

УДК: 510.5

Поступило: 24.12.1986


 Англоязычная версия: DOI: 10.1007/BF01978567

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


© МИАН, 2024