Goodness in the enumeration and singleton degrees

Archive for Mathematical Logic 49 (6):673-691 (2010)
  Copy   BIBTEX

Abstract

We investigate and extend the notion of a good approximation with respect to the enumeration ${({\mathcal D}_{\rm e})}$ and singleton ${({\mathcal D}_{\rm s})}$ degrees. We refine two results by Griffith, on the inversion of the jump of sets with a good approximation, and we consider the relation between the double jump and index sets, in the context of enumeration reducibility. We study partial order embeddings ${\iota_s}$ and ${\hat{\iota}_s}$ of, respectively, ${{\mathcal D}_{\rm e}}$ and ${{\mathcal D}_{\rm T}}$ (the Turing degrees) into ${{\mathcal D}_{\rm s}}$ , and we show that the image of ${{\mathcal D}_{\rm T}}$ under ${\hat{\iota}_s}$ is precisely the class of retraceable singleton degrees. We define the notion of a good enumeration, or singleton, degree to be the property of containing the set of good stages of some good approximation, and we show that ${\iota_s}$ preserves the latter, as also other naturally arising properties such as that of totality or of being ${\Gamma^0_n}$ , for ${\Gamma \in \{\Sigma,\Pi,\Delta\}}$ and n > 0. We prove that the good enumeration and singleton degrees are immune and that the good ${\Sigma^0_2}$ singleton degrees are hyperimmune. Finally we show that, for singleton degrees a s < b s such that b s is good, any countable partial order can be embedded in the interval (a s, b s)

Links

PhilArchive



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

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

Limit lemmas and jump inversion in the enumeration degrees.Evan J. Griffiths - 2003 - Archive for Mathematical Logic 42 (6):553-562.
On the Symmetric Enumeration Degrees.Charles M. Harris - 2007 - Notre Dame Journal of Formal Logic 48 (2):175-204.
Bounded enumeration reducibility and its degree structure.Daniele Marsibilio & Andrea Sorbi - 2012 - Archive for Mathematical Logic 51 (1-2):163-186.
On the jump classes of noncuppable enumeration degrees.Charles M. Harris - 2011 - Journal of Symbolic Logic 76 (1):177 - 197.
The structure of the s -degrees contained within a single e -degree.Thomas F. Kent - 2009 - Annals of Pure and Applied Logic 160 (1):13-21.
The jump operator on the ω-enumeration degrees.Hristo Ganchev & Ivan N. Soskov - 2009 - Annals of Pure and Applied Logic 160 (3):289-301.
On Transfinite Levels of the Ershov Hierarchy.Cheng Peng - 2021 - Bulletin of Symbolic Logic 27 (2):220-221.

Analytics

Added to PP
2013-11-23

Downloads
68 (#237,442)

6 months
7 (#621,576)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Density of the cototal enumeration degrees.Joseph S. Miller & Mariya I. Soskova - 2018 - Annals of Pure and Applied Logic 169 (5):450-462.
Avoiding uniformity in the Δ 2 0 enumeration degrees.Liliana Badillo & Charles M. Harris - 2014 - Annals of Pure and Applied Logic 165 (9):1355-1379.
Bounded enumeration reducibility and its degree structure.Daniele Marsibilio & Andrea Sorbi - 2012 - Archive for Mathematical Logic 51 (1-2):163-186.
On the jump classes of noncuppable enumeration degrees.Charles M. Harris - 2011 - Journal of Symbolic Logic 76 (1):177 - 197.
Badness and jump inversion in the enumeration degrees.Charles M. Harris - 2012 - Archive for Mathematical Logic 51 (3-4):373-406.

View all 6 citations / Add more citations

References found in this work

Classical recursion theory: the theory of functions and sets of natural numbers.Piergiorgio Odifreddi - 1989 - New York, N.Y., USA: Sole distributors for the USA and Canada, Elsevier Science Pub. Co..
Computability Theory.S. Barry Cooper - 2003 - Chapman & Hall.
Then-rea enumeration degrees are dense.Alistair H. Lachlan & Richard A. Shore - 1992 - Archive for Mathematical Logic 31 (4):277-285.
Enumeration reducibility and partial degrees.John Case - 1971 - Annals of Mathematical Logic 2 (4):419-439.
On minimal pairs of enumeration degrees.Kevin McEvoy & S. Barry Cooper - 1985 - Journal of Symbolic Logic 50 (4):983-1001.

View all 10 references / Add more references