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

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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1142/S0219061302000151
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 50,118
Through your library

References found in this work BETA

Dynamic Properties of Computably Enumerable Sets.Robert I. Soare - 1996 - In S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.), Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press. pp. 224--105.
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

Citations of this work BETA

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

Add more citations

Similar books and articles

Analytics

Added to PP index
2012-09-02

Total views
31 ( #309,937 of 2,324,566 )

Recent downloads (6 months)
6 ( #138,747 of 2,324,566 )

How can I increase my downloads?

Downloads

My notes