Hostname: page-component-7b7567c8c-w7t8q Total loading time: 0 Render date: 2026-11-18T06:03:53.196Z Has data issue: false hasContentIssue false

Limits on jump inversion for strong reducibilities

Published online by Cambridge University Press:  12 March 2014

Barbara F. Csima
Affiliation:
Department of Pure Mathematics, University of Waterloo, Waterloo, ON, N2L 3G1, Canada, E-mail: csima@math.uwaterloo.ca, URL: www.math.uwaterloo.ca/~csima
Rod Downey
Affiliation:
School of Mathematics, Statistics and Computer Science, Victoria University of Wellington, PO BOX 600, Wellington, New Zealand, E-mail: rod.downey@vuw.ac.nz
Keng Meng Ng
Affiliation:
University of Wisconsin, 480 Lincoln Drive, Madison, Wisconsin 53706, USA, E-mail: selwynng@math.wisc.edu

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 δ20 set B >tt ∅′ such that there is no c.e. set A with A′ ≡wttB. We also show that there is a Σ20 set C >tt ∅′ such that there is no δ20 set D with D′ ≡wttC.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable