Limits on jump inversion for strong reducibilities

Journal of Symbolic Logic 76 (4):1287-1296 (2011)
  Copy   BIBTEX

Abstract

We show that Sacks' and Shoenfield's analogs of jump inversion fail for both tt- and wtt-reducibilities in a strong way. In particular we show that there is a ${\mathrm{\Delta }}_{2}^{0}$ set B > tt ∅′ such that there is no c.e. set A with A′ ≡ wtt B. We also show that there is a ${\mathrm{\Sigma }}_{2}^{0}$ set C > tt ∅′ such that there is no ${\mathrm{\Delta }}_{2}^{0}$ set D with D′ ≡ wtt C

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,611

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2011-10-12

Downloads
57 (#283,468)

6 months
9 (#320,673)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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.
Effective Domination and the Bounded Jump.Keng Meng Ng & Hongyuan Yu - 2020 - Notre Dame Journal of Formal Logic 61 (2):203-225.
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

Computability Theory.Barry Cooper - 2010 - Journal of the Indian Council of Philosophical Research 27 (1).
A criterion for completeness of degrees of unsolvability.Richard Friedberg - 1957 - Journal of Symbolic Logic 22 (2):159-160.
Classifications of degree classes associated with r.e. subspaces.R. G. Downey & J. B. Remmel - 1989 - Annals of Pure and Applied Logic 42 (2):105-124.

Add more references