Joel David Hamkins
(City University of New York)
The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility

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 well-suited 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: