Classifying equivalence relations in the Ershov hierarchy

Nikolay Bazhenov, Manat Mustafa, Luca San Mauro, Andrea Sorbi, Mars Yamaleev

Research output: Contribution to journalArticle

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 Δ02 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 Σ−1a∖Π−1a equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees.
Original languageEnglish
Article number1
Pages (from-to)1-30
Number of pages30
JournalArchive for Mathematical Logic
DOIs
Publication statusPublished - Feb 13 2020

Fingerprint

Ershov Hierarchy
Equivalence relation
Reducibility
Supremum
Notation
Nonexistence
Classify
Equivalence

Cite this

Classifying equivalence relations in the Ershov hierarchy. / Bazhenov, Nikolay; Mustafa, Manat; San Mauro, Luca; Sorbi, Andrea; Yamaleev, Mars.

In: Archive for Mathematical Logic, 13.02.2020, p. 1-30.

Research output: Contribution to journalArticle

Bazhenov, Nikolay ; Mustafa, Manat ; San Mauro, Luca ; Sorbi, Andrea ; Yamaleev, Mars. / Classifying equivalence relations in the Ershov hierarchy. In: Archive for Mathematical Logic. 2020 ; pp. 1-30.
@article{6b7f22e727694b6ca8a275bdb7ff4941,
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 Δ02 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 Σ−1a∖Π−1a equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees.",
author = "Nikolay Bazhenov and Manat Mustafa and {San Mauro}, Luca and Andrea Sorbi and Mars Yamaleev",
year = "2020",
month = "2",
day = "13",
doi = "https://doi.org/10.1007/s00153-020-00710-1",
language = "English",
pages = "1--30",
journal = "Archive for Mathematical Logic",
issn = "0933-5846",
publisher = "Springer New York",

}

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/2/13

Y1 - 2020/2/13

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 Δ02 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 Σ−1a∖Π−1a 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 Δ02 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 Σ−1a∖Π−1a equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees.

UR - https://link.springer.com/article/10.1007/s00153-020-00710-1

U2 - https://doi.org/10.1007/s00153-020-00710-1

DO - https://doi.org/10.1007/s00153-020-00710-1

M3 - Article

SP - 1

EP - 30

JO - Archive for Mathematical Logic

JF - Archive for Mathematical Logic

SN - 0933-5846

M1 - 1

ER -