On ?11 equivalence relations over the natural numbers
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 i.e., ?11 but not 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.
equivalence relations h-reducibility ff-reducibility hyperarithmetical set msc (2010) 03d30