On [summation of 1 raised to the power 1] equivalence relations over the natural numbers
Ekaterina Fokina, Sy D. Friedman · Dipòsit Digital de Documents de la UAB (Universitat Autònoma de Barcelona) · 2011
We study the structure of Σ 1 1 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 Σ 1 1 (i.e.Σ 1 1 but not ∆ 1 1 ) equivalence classes.We also show the existence of incomparable Σ 1 1 equivalence relations that are complete as subsets of ω × ω with respect to the corresponding reducibility on sets.We study complete Σ 1 1 equivalence relations (under both reducibilities) and show that existence of infinitely many properly Σ 1 1 equivalence classes that are complete as Σ 1 1 sets (under the corresponding reducibility on sets) is necessary but not sufficient for a relation to be complete in the context of Σ 1 1 equivalence relations.