The hierarchy of equivalence relations on the natural numbers under computable reducibility, Chicheley Hall, June 2012


This will be a talk at The Incomputable, a workshop held June 12-15, 2012 at the Kavli Royal Society International Centre at Chicheley Hall as a part of the program Semantics and Syntax: A Legacy of Alan Turing organized by the Isaac Newton Institute of Mathematical Sciences in Cambridge, UK.

Abstract.  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 beenMathematical discussions with Philip Welch 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.

Article | Slides | Workshop abstract 

Leave a Reply