A bounded jump for the bounded Turing degrees
Bernard A. Anderson, Barbara F. Csima · 2010
We define the bounded jump of A by Ab={x∈ω∣∃i≤x[φi(x)↓∧ΦxA↾↾φi(x)(x)↓]} and let Anb denote the nth bounded jump. We demonstrate several properties of the bounded jump, including the fact that it is strictly increasing and order-preserving on the bounded Turing (bT) degrees (also known as the weak truth-table degrees). We show that the bounded jump is related to the Ershov hierarchy. Indeed, for n≥2 we have X≤bT∅nb⇔X is ωn-c.e. ⇔X≤1∅nb, extending the classical result that X≤bT∅'⇔X is ω-c.e. Finally, we prove that the analogue of Shoenfield inversion holds for the bounded jump on the bounded Turing degrees. That is, for every X such that ∅b≤bTX≤bT∅2b, there is a Y≤bT∅b such that Yb≡bTX.