RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2018 Volume 59, Number 1, Pages 29–40 (Mi smj2951)

This article is cited in 10 papers

On dark computably enumerable equivalence relations

N. A. Bazhenovab, B. S. Kalmurzaevc

a Sobolev Institute of Mathematics, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
c Al-Farabi Kazakh National University, Almaty, Kazakhstan

Abstract: 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\leq_cS$) 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 $\leq_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\leq_cF$. As a consequence of this result, we construct an infinite increasing $\leq_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 $\leq_c$.

Keywords: equivalence relation, computably enumerable equivalence relation, computable reducibility, weakly precomplete equivalence relation, computably enumerable order, $lo$-reducibility.

UDC: 510.57

MSC: 35R30

Received: 07.06.2017

DOI: 10.17377/smzh.2018.59.103


 English version:
Siberian Mathematical Journal, 2018, 59:1, 22–30

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024