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. https://resolver.caltech.edu/CaltechAUTHORS:20130624-113819994
|
PDF
- Published Version
See Usage Policy. 475kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20130624-113819994
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: |
| ||||||||||||
Series Name: | Contemporary Mathematics | ||||||||||||
Issue or Number: | 257 | ||||||||||||
Classification Code: | 1991 Mathematics Subject Classification. Primary 03D30, 03E15; Secondary 04A15, 54H05 | ||||||||||||
DOI: | 10.1090/conm/257 | ||||||||||||
Record Number: | CaltechAUTHORS:20130624-113819994 | ||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20130624-113819994 | ||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
ID Code: | 39054 | ||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||
Deposited By: | INVALID USER | ||||||||||||
Deposited On: | 24 Jun 2013 21:14 | ||||||||||||
Last Modified: | 09 Nov 2021 23:42 |
Repository Staff Only: item control page