COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > The hierarchy of equivalence relations on the natural numbers under computable reducibility

## The hierarchy of equivalence relations on the natural numbers under computable reducibilityAdd to your list(s) Download to your calendar using vCal - Hamkins, JD (City University of New York)
- Tuesday 27 March 2012, 10:00-10:30
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Semantics and Syntax: A Legacy of Alan Turing Many of the naturally arising equivalence relations in mathematics, such as isomorphism relations on various types of countable structures, turn out to be equivalence relations on a standard Borel space, and these relations form an intensely studied hierarchy under Borel reducibility. The topic of this talk is to introduce and explore the computable analogue of this robust theory, by studying the corresponding hierarchy of equivalence relations on the natural numbers under computable reducibility. Specifically, one relation E is computably reducible to another, F , if there is a unary computable function f such that x E y if and only if f(x) F f(y) . This gives rise to a very different hierarchy than the Turing degrees on such relations, since it is connected with the difficulty of the corresponding classification problems, rather than with the difficulty of computing the relations themselves. The theory is 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. An abundance of open questions remain, and the subject is an attractive mix of methods from mathematical logic, computability, set theory, particularly descriptive set theory, and the rest of mathematics, subjects in which many of the equivalence relations arise. This is joint work with Sam Coskey and Russell Miller. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsGurdon Institute Seminar Series 6th Annual Cambridge Technology Ventures Conference - June 11th History and the Law## Other talksMarket Socialism and Community Rating in Health Insurance The Most Influential Living Philosopher? Annual General Meeting Is Demand Side Response a womanâ€™s work? Gender dynamics in a field trial of smart meters and Time of Use tariffs in east London. Developing an optimisation algorithm to supervise active learning in drug discovery Access to Medicines Networks, resilience and complexity Autumn Cactus & Succulent Show Direct measurements of dynamic granular compaction at the mesoscale using synchrotron X-ray radiography Public Lecture: Development of social behaviour in children from infancy: neurobiological, relational and situational interactions |