CaltechAUTHORS
  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 . http://resolver.caltech.edu/CaltechAUTHORS:20130624-113819994

[img]
Preview
PDF - Published Version
See Usage Policy.

463Kb

Use this Persistent URL to link to this item: http://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:
URLURL TypeDescription
http://www.ams.org/books/conm/257/PublisherArticle
http://dx.doi.org/10.1090/conm/257DOIArticle
https://arxiv.org/abs/math/0001173arXivDiscussion 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.
Funders:
Funding AgencyGrant Number
NSFDMS-9158092
NSFDMS-9619880
Other Numbering System:
Other Numbering System NameOther Numbering System ID
MathSciNet ReviewMR1770736
Classification Code:1991 Mathematics Subject Classification. Primary 03D30, 03E15; Secondary 04A15, 54H05
Record Number:CaltechAUTHORS:20130624-113819994
Persistent URL:http://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: John Wade
Deposited On:24 Jun 2013 21:14
Last Modified:11 Jul 2017 22:40

Repository Staff Only: item control page