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. 8394. ISBN 9780821819227 . http://resolver.caltech.edu/CaltechAUTHORS:20130624113819994

PDF
 Published Version
See Usage Policy. 463Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20130624113819994
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.
Item Type:  Book Section  

Related URLs: 
 
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.  
Funders: 
 
Other Numbering System: 
 
Classification Code:  1991 Mathematics Subject Classification. Primary 03D30, 03E15; Secondary 04A15, 54H05  
Record Number:  CaltechAUTHORS:20130624113819994  
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:20130624113819994  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  39054  
Collection:  CaltechAUTHORS  
Deposited By:  John Wade  
Deposited On:  24 Jun 2013 21:14  
Last Modified:  11 Jul 2017 22:40 
Repository Staff Only: item control page