Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
On Dark Computably Enumerable Equivalence Relations. / Bazhenov, N. A.; Kalmurzaev, B. S.
в: Siberian Mathematical Journal, Том 59, № 1, 01.01.2018, стр. 22-30.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
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 -
ID: 10453842