Exact pairs for the ideal of the k-trivial sequences in the Turing degrees

Journal of Symbolic Logic 79 (3):676-692 (2014)
  Copy   BIBTEX


TheK-trivial sets form an ideal in the Turing degrees, which is generated by its computably enumerable members and has an exact pair below the degree of the halting problem. The question of whether it has an exact pair in the c.e. degrees was first raised in [22, Question 4.2] and later in [25, Problem 5.5.8].We give a negative answer to this question. In fact, we show the following stronger statement in the c.e. degrees. There exists aK-trivial degreedsuch that for all degreesa, bwhich are notK-trivial anda > d, b > dthere exists a degreevwhich is notK-trivial anda > v, b > v. This work sheds light to the question of the definability of theK-trivial degrees in the c.e. degrees.



    Upload a copy of this work     Papers currently archived: 86,377

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles


Added to PP

4 (#1,371,792)

6 months
1 (#866,649)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Algorithmic randomness and measures of complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.
Computing from projections of random points.Noam Greenberg, Joseph S. Miller & André Nies - 2019 - Journal of Mathematical Logic 20 (1):1950014.

Add more citations

References found in this work

No references found.

Add more references