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

DOI10.3233/COM-2012-004MaRDI QIDQ4904456zbMATH OpenOpenAlexFDO

Authors Samuel Coskey, Joel David Hamkins, Russell Miller

Publication date 30 January 2013

Published in Computability (Search for Journal in Brave)

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

zbMATH Keywords

equivalence relationscomputable reducability

Mathematics Subject Classification ID

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

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.

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

Cited in

(25)

• On Heckits, LATE, and Numerical Equivalence
• Finitary reducibility on equivalence relations
• The natural hierarchy and quasi-hierarchy of constructibility degrees
• ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS
• 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
• Weakly precomplete equivalence relations in the Ershov hierarchy
• Agreement reducibility
• On polynomial-time relation reducibility
• On the reducibility of monadic equivalence relations
• A survey on universal computably enumerable 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
• Uniform Martin's conjecture, locally
• Jumps of computably enumerable equivalence relations
• On \(\Delta_2^0\)-categoricity of equivalence relations
• Graphs realised by r.e. equivalence relations
• On Σ¹ ₁ equivalence relations over the natural numbers
• Equivalence relations that are \(\Sigma^0_3\) complete for computable reducibility (extended abstract)
• On the degree structure of equivalence relations under computable reducibility
• Classifying equivalence relations in the Ershov hierarchy
• Minimal equivalence relations in hyperarithmetical and analytical hierarchies
• On \(p\)-reducibility of computable numerations

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)