Published 2000 | Version Published
Book Section - Chapter Open

How Many Turing Degrees are There?

Abstract

A Borel equivalence relation on a Polish space is countable if all of its equivalence classes are countable. Standard examples of countable Borel equivalence relations (on the space of subsets of the integers) that occur in recursion theory are: recursive isomorphism, Turing equivalence, arithmetic equivalence, etc. There is a canonical hierarchy of complexity of countable Borel equivalence relations imposed by the notion of Borel reducibility. We will survey results and conjectures concerning the problem of identifying the place in this hierarchy of these equivalence relations from recursion theory and also discuss some of their implications.

Additional Information

© 2000 American Mathematical Society. The first author was partially supported by NSF Grant DMS 9158092. The second author was partially supported by NSF Grant DMS 9619880.

Attached Files

Published - Kechris_2000p83.pdf

Files

Kechris_2000p83.pdf

Files (475.1 kB)

Name Size
md5:2bcb263f3b55545291e8e7f3595182af
475.1 kB Preview Download

Additional details

Identifiers

Eprint ID
39054
Resolver ID
CaltechAUTHORS:20130624-113819994

Related works

Funding

NSF
DMS-9158092
NSF
DMS-9619880

Dates

Created
2013-06-24
Created from EPrint's datestamp field
Updated
2021-11-09
Created from EPrint's last_modified field

Caltech Custom Metadata

Caltech groups
Mathematics Department
Series Name
Contemporary Mathematics
Series Volume or Issue Number
257
Other Numbering System Name
MathSciNet Review
Other Numbering System Identifier
MR1770736