On the definability of the double jump in the computably enumerable sets

Journal of Mathematical Logic 2 (02):261-296 (2002)
  Copy   BIBTEX


We show that the double jump is definable in the computably enumerable sets. Our main result is as follows: let [Formula: see text] is the Turing degree of a [Formula: see text] set J ≥T0″}. Let [Formula: see text] such that [Formula: see text] is upward closed in [Formula: see text]. Then there is an ℒ property [Formula: see text] such that [Formula: see text] if and only if there is an A where A ≡T F and [Formula: see text]. A corollary of this is that, for all n ≥ 2, the high n computably enumerable degrees are invariant in the computably enumerable sets. Our work resolves Martin's Invariance Conjecture.



    Upload a copy of this work     Papers currently archived: 94,420

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

55 (#286,536)

6 months
13 (#281,206)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

A Hierarchy of Computably Enumerable Degrees.Rod Downey & Noam Greenberg - 2018 - Bulletin of Symbolic Logic 24 (1):53-89.
Degree invariance in the Π10classes.Rebecca Weber - 2011 - Journal of Symbolic Logic 76 (4):1184-1210.

Add more citations

References found in this work

Recursion, metarecursion, and inclusion.James C. Owings - 1967 - Journal of Symbolic Logic 32 (2):173-179.
Degrees of classes of RE sets.J. R. Shoenfield - 1976 - Journal of Symbolic Logic 41 (3):695-696.

View all 6 references / Add more references