Index sets in $O\,'$

L. Hay

Algebra i logika, Tome 12 (1973) no. 6, pp. 713-729

Résumé

Пусть $\{W_{x}\mid x\in N\}$ — стандартное перечисление всех рекурсивно перечислимых множеств. Индексным множеством класса $C$ рекурсивно перечислимых множеств называется множество $\{x\mid W_{x}\in C\}$. Для всякой тьюринговой степени $a$ пусть $\sigma_{a}$ обозначает частичное упорядочение $1$-степеней индексных множеств тюринговой степени $a$ относительно $1$-$1$-сводимости. Основные результаты: 1) если $a$ содержит нетривиальное индексное множество, то всякое счётное частичное упорядочение может быть вложено в $\sigma_{a}$; 2) каждый элемент из $\sigma_{a}$ имеет непосредственно следующий за ним. Кроме того, даются некоторые условия для того, чтобы индексные множества были $p$-цилиндрами.