Classifying equivalence relations in the Ershov hierarchy

2020

Full text Open access: Hybrid Metadata (CSL-JSON)
DOI 10.1007/s00153-020-00710-1
Data confidence 70 medium
How this score is calculated

It is built from checkable properties of the record itself: whether the article has a DOI, how many independent sources confirmed its data, whether the required fields are filled in, and how recent the latest confirmation is. Disagreement between sources and a missing identifier lower it. A value of 80 or above means the record was published without further checking; 60 to 79 means it is published at reduced confidence, with a manual check advisable. A record verified by an editor by hand is never pushed below 90 by a recalculation. This scores our data about the article, not the article itself.

Abstract

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 $$\leqslant _c$$ ⩽ c . This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the $$\Delta ^0_2$$ Δ 2 0 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 $$\leqslant _c$$ ⩽ c on the $$\Sigma ^{-1}_{a}\smallsetminus \Pi ^{-1}_a$$ Σ a - 1 \ Π a - 1 equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees.