On Dark Computably Enumerable Equivalence Relations

Standard

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

In: Siberian Mathematical Journal, Vol. 59, No. 1, 01.01.2018, p. 22-30.

Research output: Contribution to journal › Article › peer-review

Harvard

Bazhenov, NA & Kalmurzaev, BS 2018, 'On Dark Computably Enumerable Equivalence Relations', Siberian Mathematical Journal, vol. 59, no. 1, pp. 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 Jan 1;59(1):22-30. doi: 10.1134/S0037446618010032

Author

Bazhenov, N. A. ; Kalmurzaev, B. S. / On Dark Computably Enumerable Equivalence Relations. In: Siberian Mathematical Journal. 2018 ; Vol. 59, No. 1. pp. 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.

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