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

Cite this