Classifying equivalence relations in the Ershov hierarchy

Archive for Mathematical Logic 59 (7-8):835-864 (2020)
  Copy   BIBTEX

Abstract

Computably enumerable equivalence relations received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility \. This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the \ 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 \ on the \ equivalence relations. A special focus of our work is on the existence of infima and suprema of c-degrees.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,168

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

On Polynomial-Time Relation Reducibility.Su Gao & Caleb Ziegler - 2017 - Notre Dame Journal of Formal Logic 58 (2):271-285.
Σ 1 0 and Π 1 0 equivalence structures.Douglas Cenzer, Valentina Harizanov & Jeffrey B. Remmel - 2011 - Annals of Pure and Applied Logic 162 (7):490-503.
? 0 N -equivalence relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351-358.
Classifying positive equivalence relations.Claudio Bernardi & Andrea Sorbi - 1983 - Journal of Symbolic Logic 48 (3):529-538.
The Hausdorff-Ershov Hierarchy in Euclidean Spaces.Armin Hemmerling - 2006 - Archive for Mathematical Logic 45 (3):323-350.
$\sum_{0}^{n}$ -Equivalence Relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351 - 358.

Analytics

Added to PP
2020-02-13

Downloads
17 (#871,839)

6 months
7 (#437,422)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Luca San Mauro
Università degli Studi di Roma La Sapienza