On Dark Computably Enumerable Equivalence Relations

N. A. Bazhenov, B. S. Kalmurzaev

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

3 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)22-30
Число страниц9
ЖурналSiberian Mathematical Journal
Том59
Номер выпуска1
DOI
СостояниеОпубликовано - 1 янв 2018

Fingerprint Подробные сведения о темах исследования «On Dark Computably Enumerable Equivalence Relations». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать