Classifying equivalence relations in the Ershov hierarchy

Standard

Classifying equivalence relations in the Ershov hierarchy. / Bazhenov, Nikolay; Mustafa, Manat; San Mauro, Luca et al.

In: Archive for Mathematical Logic, Vol. 59, No. 7-8, 01.11.2020, p. 835-864.

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

Harvard

Bazhenov, N, Mustafa, M, San Mauro, L, Sorbi, A & Yamaleev, M 2020, 'Classifying equivalence relations in the Ershov hierarchy', Archive for Mathematical Logic, vol. 59, no. 7-8, pp. 835-864. https://doi.org/10.1007/s00153-020-00710-1

APA

Bazhenov, N., Mustafa, M., San Mauro, L., Sorbi, A., & Yamaleev, M. (2020). Classifying equivalence relations in the Ershov hierarchy. Archive for Mathematical Logic, 59(7-8), 835-864. https://doi.org/10.1007/s00153-020-00710-1

Vancouver

Bazhenov N, Mustafa M, San Mauro L, Sorbi A, Yamaleev M. Classifying equivalence relations in the Ershov hierarchy. Archive for Mathematical Logic. 2020 Nov 1;59(7-8):835-864. doi: 10.1007/s00153-020-00710-1

Author

Bazhenov, Nikolay ; Mustafa, Manat ; San Mauro, Luca et al. / Classifying equivalence relations in the Ershov hierarchy. In: Archive for Mathematical Logic. 2020 ; Vol. 59, No. 7-8. pp. 835-864.

BibTeX

@article{7e9dbf32021e4c508c3b01ea87c5beec,

title = "Classifying equivalence relations in the Ershov hierarchy",

abstract = "Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility ⩽ c. This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the Δ20 case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by ⩽ c on the Σa-1\Πa-1 equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees.",

keywords = "Computability theory, Computably enumerable equivalence relations, Ershov hierarchy, Δ equivalence relations, Delta(0)(2) equivalence relations, COMPLEXITY",

author = "Nikolay Bazhenov and Manat Mustafa and {San Mauro}, Luca and Andrea Sorbi and Mars Yamaleev",

year = "2020",

month = nov,

day = "1",

doi = "10.1007/s00153-020-00710-1",

language = "English",

volume = "59",

pages = "835--864",

journal = "Archive for Mathematical Logic",

issn = "0933-5846",

publisher = "Springer Nature",

number = "7-8",

}

RIS

TY - JOUR

T1 - Classifying equivalence relations in the Ershov hierarchy

AU - Bazhenov, Nikolay

AU - Mustafa, Manat

AU - San Mauro, Luca

AU - Sorbi, Andrea

AU - Yamaleev, Mars

PY - 2020/11/1

Y1 - 2020/11/1

N2 - Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility ⩽ c. This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the Δ20 case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by ⩽ c on the Σa-1\Πa-1 equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees.

AB - Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility ⩽ c. This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the Δ20 case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by ⩽ c on the Σa-1\Πa-1 equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees.

KW - Computability theory

KW - Computably enumerable equivalence relations

KW - Ershov hierarchy

KW - Δ equivalence relations

KW - Delta(0)(2) equivalence relations

KW - COMPLEXITY

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

U2 - 10.1007/s00153-020-00710-1

DO - 10.1007/s00153-020-00710-1

M3 - Article

C2 - 33122878

AN - SCOPUS:85079714401

VL - 59

SP - 835

EP - 864

JO - Archive for Mathematical Logic

JF - Archive for Mathematical Logic

SN - 0933-5846

IS - 7-8

ER -

ID: 23593542