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$.
تحميل البحث