The study of Borel equivalence relations under Borel reducibility has developed into an important area of descriptive set theory. The dichotomies of Silver [20] and Harrington, Kechris and Louveau [6] show that with respect to Borel reducibility, any Borel equivalence relation strictly above equality on ω is above equality on , the power set of ω, and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on . In this article we examine the effective (...) content of these and related results by studying effectively Borel equivalence relations under effectively Borel reducibility. The resulting structure is complex, even for equivalence relations with finitely many equivalence classes. However use of Kleene’s O as a parameter is sufficient to restore the picture from the noneffective setting. A key lemma is that of the existence of two effectively Borel sets of reals, neither of which contains the range of the other under any effectively Borel function; the proof of this result applies Barwise compactness to a deep theorem of Harrington establishing for any recursive ordinal α the existence of singletons whose α-jumps are Turing incomparable. (shrink)

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 equation imagei.e., Σ11 but not equation image 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 and show that existence of infinitely many properly Σ11 equivalence classes that are complete as Σ11 sets is necessary but not sufficient for a relation to be complete in the context of Σ11 equivalence relations. (shrink)

Classification is an important goal in many branches of mathematics. The idea is to describe the members of some class of mathematical objects, up to isomorphism or other important equivalence, in terms of relatively simple invariants. Where this is impossible, it is useful to have concrete results saying so. In model theory and descriptive set theory, there is a large body of work showing that certain classes of mathematical structures admit classification while others do not. In the present paper, we (...) describe some recent work on classification in computable structure theory.Section 1 gives some background from model theory and descriptive set theory. From model theory, we give sample structure and non-structure theorems for classes that include structures of arbitrary cardinality. We also describe the notion of Scott rank, which is useful in the more restricted setting of countable structures. From descriptive set theory, we describe the basic Polish space of structures for a fixed countable language with fixed countable universe. We give sample structure and non-structure theorems based on the complexity of the isomorphism relation, and on Borel embeddings.Section 2 gives some background on computable structures. We describe three approaches to classification for these structures. The approaches are all equivalent. However, one approach, which involves calculating the complexity of the isomorphism relation, has turned out to be more productive than the others. Section 3 describes results on the isomorphism relation for a number of mathematically interesting classes—various kinds of groups and fields. In Section 4, we consider a setting similar to that in descriptive set theory. We describe an effective analogue of Borel embedding which allows us to make distinctions even among classes of finite structures. Section 5 gives results on computable structures of high Scott rank. Some of these results make use of computable embeddings. Finally, in Section 6, we mention some open problems and possible directions for future work. (shrink)