Standard

On Dark Computably Enumerable Equivalence Relations. / Bazhenov, N. A.; Kalmurzaev, B. S.

в: Siberian Mathematical Journal, Том 59, № 1, 01.01.2018, стр. 22-30.

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

Harvard

Bazhenov, NA & Kalmurzaev, BS 2018, 'On Dark Computably Enumerable Equivalence Relations', Siberian Mathematical Journal, Том. 59, № 1, стр. 22-30. https://doi.org/10.1134/S0037446618010032

APA

Bazhenov, N. A., & Kalmurzaev, B. S. (2018). On Dark Computably Enumerable Equivalence Relations. Siberian Mathematical Journal, 59(1), 22-30. https://doi.org/10.1134/S0037446618010032

Vancouver

Bazhenov NA, Kalmurzaev BS. On Dark Computably Enumerable Equivalence Relations. Siberian Mathematical Journal. 2018 янв. 1;59(1):22-30. doi: 10.1134/S0037446618010032

Author

Bazhenov, N. A. ; Kalmurzaev, B. S. / On Dark Computably Enumerable Equivalence Relations. в: Siberian Mathematical Journal. 2018 ; Том 59, № 1. стр. 22-30.

BibTeX

@article{2985afad68314919a71e5cbe65234b74,
title = "On Dark Computably Enumerable Equivalence Relations",
abstract = "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.",
keywords = "computable reducibility, computably enumerable equivalence relation, computably enumerable order, equivalence relation, lo-reducibility, weakly precomplete equivalence relation",
author = "Bazhenov, {N. A.} and Kalmurzaev, {B. S.}",
note = "Publisher Copyright: {\textcopyright} 2018, Pleiades Publishing, Ltd.",
year = "2018",
month = jan,
day = "1",
doi = "10.1134/S0037446618010032",
language = "English",
volume = "59",
pages = "22--30",
journal = "Siberian Mathematical Journal",
issn = "0037-4466",
publisher = "MAIK NAUKA/INTERPERIODICA/SPRINGER",
number = "1",

}

RIS

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