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

Алгебра и логика, 1988, том 27, номер 4, страницы 464–478 (Mi al2027)

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

Иерархия Ершова и $\mathrm{T}$-скачок

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


Аннотация: Пусть $(O; <_O)$ — клиниевская система ординальных обозначений, $\Sigma_a^{-1}$ и $\Delta_a^{-1}$ — классы иерархии Ершова, $'$ — операция $T$-скачка. Доказано, что 1) для любого рекурсивно-перечислимого (р.п.) множества $A$ и любого не наименьшего $a\in O$ существует $R\in \Sigma_a^{-1}$ такое, что $R$ не $T$-эквивалентно никакому множеству из $\Delta_a^{-1}$ и $R'\equiv_TA'$, 2) для любого р.п. множества $A$ и любого предельного $a\in O$ существует $R\in\Delta_a^{-1}$ такое, что $R$ не $T$-эквивалентно никакому множеству из $\bigcup\limits_{b<_O\,a}\Sigma_b^{-1}$ и $R'\equiv_TA'$. Доказано также, что 1) для любого не наименьшего $a\in O$ существуют $R$, $\tilde R\in\Sigma_a^{-1}$ такие, что $\tilde R<_T R$, $\tilde{R}'\equiv_T\Phi'$, $R'\equiv_T\Phi''$ и не существует $x\in\Delta_a^{-1}$, $\tilde{R}\leqslant_T x\leqslant_T R$; 2) для любого предельного $a\in O$ существуют $R$, $\tilde R\in\Delta_a^{-1}$ такие, что $\tilde R<_T R$, $\tilde{R}'\equiv_T\Phi'$, $R'\equiv_T\Phi''$ и не существует $X\in\bigcup\limits_{b<_O\,a}\Sigma_b^{-1}$, $\tilde{R}\leqslant_T x\leqslant_T R$.

УДК: 510.5

Поступило: 24.12.1986


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

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


© МИАН, 2024