TY - JOUR

T1 - On Dark Computably Enumerable Equivalence Relations

AU - Bazhenov, N. A.

AU - Kalmurzaev, B. S.

N1 - Publisher Copyright: © 2018, Pleiades Publishing, Ltd.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - computable reducibility

KW - computably enumerable equivalence relation

KW - computably enumerable order

KW - equivalence relation

KW - lo-reducibility

KW - weakly precomplete equivalence relation

UR - http://www.scopus.com/inward/record.url?scp=85043509774&partnerID=8YFLogxK

U2 - 10.1134/S0037446618010032

DO - 10.1134/S0037446618010032

M3 - Article

AN - SCOPUS:85043509774

VL - 59

SP - 22

EP - 30

JO - Siberian Mathematical Journal

JF - Siberian Mathematical Journal

SN - 0037-4466

IS - 1

ER -