Pseudo-jump inversion, upper cone avoidance, and strong jump-traceability (Q1946791)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Pseudo-jump inversion, upper cone avoidance, and strong jump-traceability |
scientific article |
Statements
Pseudo-jump inversion, upper cone avoidance, and strong jump-traceability (English)
0 references
16 April 2013
0 references
Pseudo-jump operators are important in the study of the properties of the partially ordered structure \({\mathcal D}\) of the Turing degrees. They were introduced in [\textit{C. G. Jockusch jun.} and \textit{R. A. Shore}, Trans. Am. Math. Soc. 275, No. 2, 599--609 (1983; Zbl 0514.03028)] in order to approach the question of the definability of \({\mathbf 0}'\) in \({\mathcal D}\). This idea was right, because later, \textit{R. A. Shore} and \textit{T. A. Slaman} [Math. Res. Lett. 6, No. 5--6, 711--722 (1999; Zbl 0958.03029)] solved the question using pseudo-jump operators. For every \(e\in N\), the \(e\)-th pseudo-jump operator is the map \(J_e:2^{\omega}\rightarrow 2^{\omega}\) such that \(J_e(A):=A\oplus W_e^A\). Such operators are also known in the literature as 1-REA operators [\textit{C. G. Jockusch jun.} and \textit{R. A. Shore}, J. Symb. Log. 49, No. 4, 1205--1236 (1984; Zbl 0574.03026)]. In the paper under review, the authors prove the following main result: (1) There is a pseudo-jump operator, increasing on all sets, which cannot be inverted while avoiding any prescribed upper cone. It has been an open problem whether or not (1) was true for pseudo-jump operators increasing on all sets. Previously, (1) was proved in [\textit{R. Coles} et al., Ann. Pure Appl. Logic 136, No. 3, 297--333 (2005; Zbl 1085.03031)] for pseudo-jump operators increasing on c.e. sets. The strategy employed in this paper is to prove first the following result: (2) There is a noncomputable c.e. set which is computable from every strongly jump-traceable hard c.e. set. Then, they apply (2) to \textit{ultrahigh sets}, which were introduced in [\textit{K. M. Ng}, J. Symb. Log. 73, No. 1, 309--342 (2008; Zbl 1168.03031)]. A set \(B\) is strongly jump-traceable hard if \(\emptyset '\leq_{\mathrm{SJT}}B\), where the reducibility \(\leq_{\mathrm{SJT}}\) is defined in terms of strong jump-traceability, the latter having been introduced by \textit{S. Figueira} et al. [Ann. Pure Appl. Logic 152, No. 1--3, 51--66 (2008; Zbl 1137.03025)]. The proof of (2) is a refinement of the proof of the following result contained in the paper: (3) There is no minimal pair of c.e. strongly jump-traceable hard degrees. In turn, (3) implies the existence of a pseudo-jump operator, increasing on all sets, which cannot be inverted back to a pair of c.e. sets whose degrees form a minimal pair. Technically, the proofs of (2) and (3) are quite complex and they make use, \textit{inter alia}, of the so-called box promotion technique, introduced in [\textit{P. Cholak} et al., Adv. Math. 217, No. 5, 2045--2074, (2008; Zbl 1134.03026)].
0 references
pseudo-jump operators
0 references
computably enumerable degrees
0 references
strong jump-traceability
0 references