Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2000 | 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 Download all
md5:2bcb263f3b55545291e8e7f3595182af
475.1 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
March 5, 2024