The hierarchy of equivalence relations on the natural numbers under computable reducibility

29 mins 37 secs, 410.94 MB, MPEG-4 Video 640x360, 29.97 fps, 44100 Hz, 1.85 Mbits/sec

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/1231825/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Hamkins, JD (City University of New York) Tuesday 27 March 2012, 10:00-10:30


Created:	2012-03-30 14:20
Collection:	Semantics and Syntax: A Legacy of Alan Turing
Publisher:	Isaac Newton Institute
Copyright:	Hamkins, JD
Language:	eng (English)


Abstract:	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.

Abstract:

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.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video *	640x360	1.85 Mbits/sec	410.94 MB	View	Download
WebM	640x360	1.15 Mbits/sec	255.76 MB	View	Download
Flash Video	484x272	568.92 kbits/sec	123.41 MB	View	Download
iPod Video	480x270	505.97 kbits/sec	109.82 MB	View	Download
MP3	44100 Hz	125.02 kbits/sec	27.00 MB	Listen	Download
Auto	(Allows browser to choose a format it supports)