Об индексных множествах для классов позитивных предпорядков

Изучается сложность индексных множеств относительно универсальной вычислимой нумерации семейства всех позитивных предпорядков. Пусть $\leq_c$ — вычислимая сводимость на позитивных предпорядках. Для произвольного позитивного предпорядка $R$, такого что $R$-индуцированная эквивалентность $\sim_R$ имеет бесконечно много классов, устанавливаются следующие результаты. Индексное множество предпорядков $P$, таких что $R\leq_c P$, является $\Sigma^0_3$-полным. Предпорядок $R$ называют самополным, если область значений любой вычислимой функции, осуществляющей сводимость $R \leq_c R$, пересекает все $\sim_R$-классы. Если $L$ — позитивный линейный предпорядок, не являющийся самополным, то индексное множество предпорядков $P$, таких что $P\equiv_c L$, является $\Sigma^0_3$-полным. Доказывается, что индексное множество самополных линейных предпорядков является $\Pi^0_3$-полным.