Minimal Equivalence Relations in Hyperarithmetical and Analytical Hierarchies

2020

Full text Open access: Green Metadata (CSL-JSON)
DOI 10.1134/s199508022002002x
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

A standard tool for classifying the complexity of equivalence relations on $$\omega$$ is provided by computable reducibility. This reducibility gives rise to a rich degree structure. The paper studies equivalence relations, which induce minimal degrees with respect to computable reducibility. Let $$\Gamma$$ be one of the following classes: $$\Sigma^{0}_{\alpha}$$ , $$\Pi^{0}_{\alpha}$$ , $$\Sigma^{1}_{n}$$ , or $$\Pi^{1}_{n}$$ , where $$\alpha\geq 2$$ is a computable ordinal and $$n$$ is a non-zero natural number. We prove that there are infinitely many pairwise incomparable minimal equivalence relations that are properly in $$\Gamma$$ .