СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ

АННОТАЦИИ

Исследуются вычислимо перечислимые (в.п.)
отношения эквивалентности на множестве
натуральных чисел. Бинарное отношение $R$
на $\omega$ вычислимо сводится к отношению $S$ (обозначается через $R\leq_c S$),
если существует вычислимая функция $f(x)$ такая, что для любых $x$ и $y$ условия
$(xRy)$ и $(f(x)Sf(y))$ эквивалентны. Отношение эквивалентности $E$ называют
{\it темным}, если оно не сравнимо
относительно $\leq_c$ с тождественным отношением
эквивалентности. Доказано, что для любого темного в.п. отношения
эквивалентности $E$ существует слабо предполное темное в.п. отношение
эквивалентности $F$ такое, что $E\leq_{c} F$. В~качестве следствия этого
результата построена бесконечная возрастающая $\leq_c$-цепь слабо предполных
темных в.п. отношений эквивалентности. Также показано существование
универсального относительно сводимости $\leq_c$ в.п. линейного порядка.