I will speak on the computable analogue of the theory of
equivalence relations on the reals under Borel reducibility. The Borel
theory has been enormously successful in clarifying the hierarchy of
classification problems arising throughout mathematics. The computable
analogue, meanwhile, appears to be particularly wellsuited for an analysis
of the c.e. instances of those problems, a rich context with many natural
examples, such as the isomorphism relation on c.e. graphs or on computably
presented groups. In particular, every equivalence relation on countable
structures has its natural restriction to the c.e. instances, which may be
viewed as an equivalence relation on the indices of those c.e. sets.
Specifically, one equivalence relation E on the natural numbers is
computably reducible to another F, if there is a computable function f such
that n E m if and only if f(n) F f(m). This reduction notion has been
introduced and studied independently by several different researchers and
research groups. In this talk, I will describe recent joint work with Sam
Coskey and Russell Miller that fills out parts of the hierarchy. An
abundance of questions remain open.
(See article at: http://jdh.hamkins.org/equivalencerelationsonnaturals/)
