Minimal Equivalence Relations in Hyperarithmetical and Analytical Hierarchies
Nikolay A. Bazhenov, Manat Mustafa, Luca San Mauro, Mars M. Yamaleev · Lobachevskii Journal of Mathematics · 2020
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$$ .