|
This article is cited in 10 scientific papers (total 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.
Received: 07.06.2017
Citation:
N. A. Bazhenov, B. S. Kalmurzaev, “On dark computably enumerable equivalence relations”, Sibirsk. Mat. Zh., 59:1 (2018), 29–40; Siberian Math. J., 59:1 (2018), 22–30
Linking options:
https://www.mathnet.ru/eng/smj2951 https://www.mathnet.ru/eng/smj/v59/i1/p29
|
Statistics & downloads: |
Abstract page: | 307 | Full-text PDF : | 94 | References: | 44 | First page: | 2 |
|