Minimal Equivalence Relations in Hyperarithmetical and Analytical Hierarchies

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 }_{\alpha }^0$, ${\Pi }_{\alpha }^0$, ${\Sigma }_n^1$, or ${\Pi }_n^1$, where $\alpha \ge 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$.

8 pages