A bounded jump for the bounded Turing degrees

Abstract: We define the bounded jump of A by A^b = {x | Exists i <= x [phi_i (x) converges and Phi_x^[A|phi_i(x)](x) converges} and let A^[nb] denote the n-th bounded jump. We demonstrate several properties of the bounded jump, including 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 > 1 we have X <=_[bT] 0^[nb] iff X is omega^n-c.e. iff X <=_1 0^[nb], extending the classical result that X <=_[bT] 0' iff X is omega-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 0^b <=_[bT] X <=_[bT] 0^[2b], there is a Y <=_[bT] 0^b such that Y^b =_[bT] X.

Review text

The behaviour of jump operators, especially the Turing jump, on the several partially ordered structures of degrees is one of the interesting lines of research in computability theory. A known result in this area is Shoenfield's jump inversion theorem: given any \(\Sigma^0_2\) set \(B\) with \(\emptyset'\leq_T B\), then there exists a set \(A\leq_T\emptyset'\) such that the Turing jump of \(A\) is Turing-equivalent to \(B\). In [\textit{B. F. Csima} et al., J. Symb. Log. 76, No. 4, 1287--1296 (2011; Zbl 1248.03062)] it was proved that the analog of Shoenfield's jump inversion theorem is not true in the partial ordering \(({\mathcal D}_{\mathrm{bT}},\leq)\) of the bounded Turing degrees. In the paper under review, the authors introduce and study a new jump operator, the \textit{bounded jump operator}, in order to obtain an analog of Shoenfield's jump inversion in \(({\mathcal D}_{\mathrm{bT}},\leq)\). Given any set \(A\) of natural numbers, the bounded jump of \(A\) is the set \(A^{\mathrm{b}}=\{x\in\omega\mid\exists i\leq x[\varphi_i(x)\downarrow\wedge\Phi_x^{A\upharpoonright\varphi_i(x)}(x)\downarrow]\}\). For every positive natural number \(n\) and every set \(A\), \(A^{n\mathrm{b}}\) denotes the \(n\)th iterate of the bounded jump of \(A\). For this new jump operator, an analog of Shoenfield's jump inversion in \(({\mathcal D}_{\mathrm{bT}},\leq)\) is shown, namely: for every (\(\omega^2\) c.e.) set \(B\) with \(\emptyset^{\mathrm{b}}\leq_{\mathrm{bT}} B\leq_{\mathrm{bT}}\emptyset^{2\mathrm{b}}\), there is a (\(\omega\)-c.e.) set \(A\leq_{\mathrm{bT}}\emptyset^{\mathrm{b}}\) such that \(A^b\equiv_{\mathrm{bT}}B\). The first part of the paper contains a preliminary list of several properties of the bounded jump on \(({\mathcal D}_{\mathrm{bT}},\leq)\), among them the strictly increasing property and the order-preserving porperty. The authors critically analyze other possible definitions of bounded jump operators. In the second part, the nice property of completeness in the Ershov hierarchy of the iterates of the bounded jump operator is shown. Precisely, it is proved that: for any set \(X\) and \(n\geq 2\), it holds that \(X\leq_{\mathrm{bT}}\emptyset^{nb}\Leftrightarrow X{\text{ is }} \omega^n{\text{-c.e.}}\Leftrightarrow X\leq_1\emptyset^{n\mathrm{b}}\). The final part contains some results that connect the bounded jump operator to the truth-table jump operator introduced by \textit{G. Gerla} [Boll. Unione Mat. Ital., V. Ser., B 16, 765--778 (1979; Zbl 0417.03018)]. The paper ends with a section dedicated to some interesting suggestions for further studies.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: A bounded jump for the bounded Turing degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2452680)