On Σ11 equivalence relations over the natural numbers
Ekaterina Fokina, Sy‐David Friedman · Mathematical logic quarterly · 2011
Abstract We study the structure of Σ11 equivalence relations on hyperarithmetical subsets of ω under reducibilities given by hyperarithmetical or computable functions, called h‐reducibility and FF‐reducibility, respectively. We show that the structure is rich even when one fixes the number of properly \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^1_1\ \big ($\end{document} i.e., Σ11 but not \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Delta ^1_1\big )$\end{document} equivalence classes. We also show the existence of incomparable Σ11 equivalence relations that are complete as subsets of ω × ω with respect to the corresponding reducibility on sets. We study complete Σ11 equivalence relations (under both reducibilities) and show that existence of infinitely many properly Σ11 equivalence classes that are complete as Σ11 sets (under the corresponding reducibility on sets) is necessary but not sufficient for a relation to be complete in the context of Σ11 equivalence relations.