Баженов Н. А., Калмурзаев Б. С.
О темных вычислимо перечислимых отношениях эквивалентности

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

N. A. Bazhenov, B. S. Kalmurzaev
On Dark Computably Enumerable Equivalence Relations

We study computably enumerable (c.e.) relations on the set of naturals. A binary relation $R$ on $\omega$ is computably reducible to a relation $S$ (which is denoted by $R \le_{c} S$) if there exists a computable function $f(x)$ such that the conditions ($xRy$) and ($f(x)Sf(y)$) are equivalent for all $x$ and $y$. An equivalence relation $E$ is called dark if it is incomparable with respect to $\le_c$ with the identity equivalence relation. We prove that, for every dark c.e. equivalence relation $E$ there exists a weakly precomplete dark c.e. relation $F$ such that $E \le_{c} F$. As a consequence of this result, we construct an infinite increasing $\le_c$-chain of weakly precomplete dark c.e. equivalence relations. We also show the existence of a universal c.e. linear order with respect to $\le_c$.

DOI 10.17377/smzh.2018.59.103
Ключевые слова: отношение эквивалентности, вычислимо перечислимое отношение эквивалентности, вычислимая сводимость, слабо предполное отношение эквивалентности, вычислимо перечислимый линейный порядок, $lo$-сводимость.

Свободный доступ к полным текстам предоставляется после 1 июля года, следующего за годом публикации