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

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

Abstract

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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,088

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

Analytics

Added to PP
2012-09-02

Downloads
53 (#275,815)

6 months
12 (#137,533)

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