BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The hierarchy of equivalence relations on the natural numbers unde
 r computable reducibility - Hamkins\, JD (City University of New York)
DTSTART:20120327T090000Z
DTEND:20120327T093000Z
UID:TALK37185@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:Many of the naturally arising equivalence relations in mathema
 tics\, such as isomorphism relations on various types of countable structu
 res\, turn out to be equivalence relations on a standard Borel space\, and
  these relations form an intensely studied hierarchy under Borel reducibil
 ity.  The topic of this talk is to introduce and explore the computable an
 alogue 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 Turi
 ng degrees on such relations\, since it is connected with the difficulty o
 f the corresponding classification problems\, rather than with the difficu
 lty of computing the relations themselves.  The theory is well suited for 
 an analysis of equivalence relations on classes of c.e.  structures\, a ri
 ch context with many natural examples\, such as the isomorphism relation o
 n c.e. graphs or on computably presented groups.  An abundance of open que
 stions remain\, and the subject is an attractive mix of methods from mathe
 matical logic\, computability\, set theory\, particularly descriptive set 
 theory\, and the rest of mathematics\, subjects in which many of the equiv
 alence relations arise.  This is joint work with Sam Coskey and Russell Mi
 ller.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR