The hierarchy of equivalence relations on the natural numbers under computable reducibility

Abstract

The notion of computable reducibility between equivalence relations on the natural numbers provides a natural computable analogue of Borel reducibility. We investigate the computable reducibility hierarchy, comparing and contrasting it with the Borel reducibility hierarchy from descriptive set theory. Meanwhile, the notion of computable reducibility appears well suited for an analysis of equivalence relations on the c.e.\ sets, and more specifically, on various classes of c.e.\ structures. This is a rich context with many natural examples, such as the isomorphism relation on c.e.\ graphs or on computably presented groups. Here, our exposition extends earlier work in the literature concerning the classification of computable structures. An abundance of open questions remains.

To appear in Computability

References in corpus (1)

• Computably Enumerable Equivalence Relations

Cited by in corpus (9)

• On the structure of computable reducibility on equivalence relations of natural numbers
• Classifying equivalence relations in the Ershov hierarchy
• Learning algebraic structures with the help of Borel equivalence relations
• Punctual equivalence relations and their (punctual) complexity
• Measuring the complexity of reductions between equivalence relations
• Computable Component-wise Reducibility
• Computable reducibility of equivalence relations and an effective jump operator
• Complexity of equivalence relations and preorders from computability theory
• Comparing the isomorphism types of equivalence structures and preorders