A Caltech Library Service

How Many Turing Degrees are There?

Dougherty, Randall and Kechris, Alexander S. (2000) How Many Turing Degrees are There? In: Computability theory and its applications: current trends and open problems. Contemporary Mathematics. No.257. American Mathematical Society , Providence, RI, pp. 83-94. ISBN 9780821819227.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
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.
Funding AgencyGrant Number
Other Numbering System:
Other Numbering System NameOther Numbering System ID
MathSciNet ReviewMR1770736
Series Name:Contemporary Mathematics
Issue or Number:257
Classification Code:1991 Mathematics Subject Classification. Primary 03D30, 03E15; Secondary 04A15, 54H05
Record Number:CaltechAUTHORS:20130624-113819994
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:39054
Deposited On:24 Jun 2013 21:14
Last Modified:09 Nov 2021 23:42

Repository Staff Only: item control page