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.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 107,599

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

Initial Segments of the Degrees of Ceers.Uri Andrews & Andrea Sorbi - 2022 - Journal of Symbolic Logic 87 (3):1260-1282.
On Polynomial-Time Relation Reducibility.Su Gao & Caleb Ziegler - 2017 - Notre Dame Journal of Formal Logic 58 (2):271-285.
Investigating the Computable Friedman–Stanley Jump.Uri Andrews & Luca San Mauro - 2024 - Journal of Symbolic Logic 89 (2):918-944.

Analytics

Added to PP
2020-02-13

Downloads
26 (#999,611)

6 months
3 (#1,334,077)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Luca San Mauro
Università degli Studi di Roma La Sapienza