On Dark Computably Enumerable Equivalence Relations
- Autores: Bazhenov N.1, Kalmurzaev B.2
-
Afiliações:
- Sobolev Institute of Mathematics
- Al-Farabi Kazakh National University
- Edição: Volume 59, Nº 1 (2018)
- Páginas: 22-30
- Seção: Article
- URL: https://journals.rcsi.science/0037-4466/article/view/171638
- DOI: https://doi.org/10.1134/S0037446618010032
- ID: 171638
Citar
Resumo
We study computably enumerable (c.e.) relations on the set of naturals. A binary relation R on ω is computably reducible to a relation S (which is denoted by R ≤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 ≤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 ≤cF. As a consequence of this result, we construct an infinite increasing ≤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 ≤c.
Sobre autores
N. Bazhenov
Sobolev Institute of Mathematics
Autor responsável pela correspondência
Email: bazhenov@math.nsc.ru
Rússia, Novosibirsk
B. Kalmurzaev
Al-Farabi Kazakh National University
Email: bazhenov@math.nsc.ru
Cazaquistão, Almaty