• S. Coskey, J. D. Hamkins, and R. Miller, “The hierarchy of equivalence relations on the natural numbers under computable reducibility,” , pp. 1-36. (submitted)  
  Citation arχiv

  @ARTICLE{CoskeyHamkinsRussell: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 = {},
  YEAR = {},
  volume = {},
  number = {},
  pages = {1--36},
  month = {},
  note = {submitted},
  url = {http://arxiv.org/abs/1109.3375},
  eprint = {1109.3375},
  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.

See Sam’s post on this article