- S. Coskey, J. D. Hamkins, and R. Miller, “The hierarchy of equivalence relations on the natural numbers under computable reducibility,” Computability, vol. 1, iss. 1, p. 15–38, 2012.

[Bibtex]`@ARTICLE{CoskeyHamkinsMiller2012:HierarchyOfEquivalenceRelationsOnN, AUTHOR = {Samuel Coskey and Joel David Hamkins and Russell Miller}, TITLE = {The hierarchy of equivalence relations on the natural numbers under computable reducibility}, JOURNAL = {Computability}, YEAR = {2012}, volume = {1}, number = {1}, pages = {15--38}, month = {}, note = {}, url = {http://jdh.hamkins.org/equivalence-relations-on-naturals/}, eprint = {1109.3375}, archivePrefix = {arXiv}, primaryClass = {math.LO}, doi = {10.3233/COM-2012-004}, abstract = {}, keywords = {}, source = {}, }`

We define and elaborate upon the notion of computable reducibility between equivalence relations on the natural numbers, providing a natural computable analogue of Borel reducibility, and investigate the hierarchy to which it gives rise. The theory appears well suited for an analysis of equivalence relations on classes of c.e. structures, a rich context with many natural examples, such as the isomorphism relation on c.e. graphs or on computably presented groups. In this regard, our exposition extends earlier work in the literature concerning the classification of computable structures. An abundance of open questions remain.

Pingback: The hierarchy of equivalence relations on the natural numbers under computable reducibility, Florida, 2012 | Joel David Hamkins

Pingback: The hierarchy of equivalence relations on the natural numbers under computable reducibility, Cambridge, March 2012 | Joel David Hamkins

Pingback: The hierarchy of equivalence relations on $mathbb{N}$ under computable reducibility, New York March 2012 | Joel David Hamkins

Pingback: The hierarchy of equivalence relations on the natural numbers under computable reducibility, Chicheley Hall, June 2012 | Joel David Hamkins