Effective Domination and the Bounded Jump

Notre Dame Journal of Formal Logic 61 (2):203-225 (2020)
  Copy   BIBTEX

Abstract

We study the relationship between effective domination properties and the bounded jump. We answer two open questions about the bounded jump: We prove that the analogue of Sacks jump inversion fails for the bounded jump and the wtt-reducibility. We prove that no c.e. bounded high set can be low by showing that they all have to be Turing complete. We characterize the class of c.e. bounded high sets as being those sets computing the Halting problem via a reduction with use bounded by an ω-c.e. function. We define several notions of a c.e. set being effectively dominant, and show that together with the bounded high sets they form a proper hierarchy.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,590

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

Bounded-low sets and the high/low hierarchy.Huishan Wu - 2020 - Archive for Mathematical Logic 59 (7-8):925-938.
A Bounded Jump for the Bounded Turing Degrees.Bernard Anderson & Barbara Csima - 2014 - Notre Dame Journal of Formal Logic 55 (2):245-264.
Bounded low and high sets.Bernard A. Anderson, Barbara F. Csima & Karen M. Lange - 2017 - Archive for Mathematical Logic 56 (5-6):507-521.
Nonisolated degrees and the jump operator.Guohua Wu - 2002 - Annals of Pure and Applied Logic 117 (1-3):209-221.
Hypersimplicity and semicomputability in the weak truth table degrees.George Barmpalias - 2005 - Archive for Mathematical Logic 44 (8):1045-1065.
Completely mitotic c.e. degrees and non-jump inversion.Evan J. Griffiths - 2005 - Annals of Pure and Applied Logic 132 (2-3):181-207.
Benign cost functions and lowness properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.

Analytics

Added to PP
2020-04-09

Downloads
14 (#264,824)

6 months
6 (#1,472,471)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Bounded-low sets and the high/low hierarchy.Huishan Wu - 2020 - Archive for Mathematical Logic 59 (7-8):925-938.

Add more citations

References found in this work

A Hierarchy of Computably Enumerable Degrees.Rod Downey & Noam Greenberg - 2018 - Bulletin of Symbolic Logic 24 (1):53-89.
A Bounded Jump for the Bounded Turing Degrees.Bernard Anderson & Barbara Csima - 2014 - Notre Dame Journal of Formal Logic 55 (2):245-264.
Abelian p-groups and the Halting problem.Rodney Downey, Alexander G. Melnikov & Keng Meng Ng - 2016 - Annals of Pure and Applied Logic 167 (11):1123-1138.

View all 6 references / Add more references