Classifying equivalence relations in the Ershov hierarchy

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

doi:10.1007/s00153-020-00710-1

Classifying equivalence relations in the Ershov hierarchy

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

Department of Mathematics

Vienna University of Technology
RAS - Sobolev Institute of Mathematics, Siberian Branch
Novosibirsk State University
University of Siena
Kazan Volga Region Federal University

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

8 Citations (Scopus)

6 Downloads (Pure)

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.

Original language	English
Article number	1
Pages (from-to)	835-864
Number of pages	30
Journal	Archive for Mathematical Logic
Volume	59
Issue number	7-8
DOIs	https://doi.org/10.1007/s00153-020-00710-1
Publication status	Published - Nov 1 2020

Funding

Open access funding provided by Austrian Science Fund (FWF). Part of the research contained in this paper was carried out while Bazhenov, San Mauro, and Yamaleev were visiting the Department of Mathematics of Nazarbayev University, Astana. These authors wish to thank Nazarbayev University for its hospitality.

Funders
Austrian Science Fund

Keywords

Computability theory
Computably enumerable equivalence relations
Ershov hierarchy
Δ equivalence relations

ASJC Scopus subject areas

Philosophy
Logic

Access to Document

10.1007/s00153-020-00710-1

Classifying equivalence relations in the Ershov hierarchy 77b7544cFinal published version, 444 KB

Cite this

@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 Δ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\textbackslash{}Π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",

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

note = "Publisher Copyright: {\textcopyright} 2020, The Author(s).",

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 New York",

number = "7-8",

}

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

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

UR - https://www.scopus.com/pages/publications/85079714401

UR - https://www.scopus.com/pages/publications/85079714401#tab=citedBy

U2 - 10.1007/s00153-020-00710-1

DO - 10.1007/s00153-020-00710-1

M3 - Article

SN - 0933-5846

VL - 59

SP - 835

EP - 864

JO - Archive for Mathematical Logic

JF - Archive for Mathematical Logic

IS - 7-8

M1 - 1

ER -

Classifying equivalence relations in the Ershov hierarchy

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this