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

DOI10.3233/COM-2012-004zbMATH Open1325.03049arXiv1109.3375OpenAlexW1636748716MaRDI QIDQ4904456FDOQ4904456

Authors: Samuel Coskey, Joel David Hamkins, Russell Miller 

Publication date: 30 January 2013

Published in: Computability (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1109.3375

Recommendations

• Finitary reducibility on equivalence relations
• On the degree structure of equivalence relations under computable reducibility
• Equivalence relations that are \(\Sigma^0_3\) complete for computable reducibility (extended abstract)
• Minimal equivalence relations in hyperarithmetical and analytical hierarchies
• Weakly precomplete equivalence relations in the Ershov hierarchy

zbMATH Keywords

equivalence relationscomputable reducability

Mathematics Subject Classification ID

Descriptive set theory (03E15) Other degrees and reducibilities in computability and recursion theory (03D30)

Cited In (20)

• ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS
• The natural hierarchy and quasi-hierarchy of constructibility degrees
• Primitive recursive equivalence relations and their primitive recursive complexity
• Learning algebraic structures with the help of Borel equivalence relations
• Representations versus numberings: On the relationship of two computability notions
• Agreement reducibility
• Uniform Martin’s conjecture, locally
• On the reducibility of monadic equivalence relations
• Reducibilities among equivalence relations induced by recursively enumerable structures
• On learning for families of algebraic structures
• COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR
• A Survey on Universal Computably Enumerable Equivalence Relations
• Jumps of computably enumerable equivalence relations
• On Σ¹ ₁ equivalence relations over the natural numbers
• On \(\Delta_2^0\)-categoricity of equivalence relations
• Graphs realised by r.e. equivalence relations
• On the degree structure of equivalence relations under computable reducibility
• Classifying equivalence relations in the Ershov hierarchy
• On \(p\)-reducibility of computable numerations
• On Heckits, LATE, and Numerical Equivalence

This page was built for publication: The hierarchy of equivalence relations on the natural numbers under computable reducibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4904456)