×

Pseudo-jump inversion, upper cone avoidance, and strong jump-traceability. (English) Zbl 1267.03047

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 [C. G. Jockusch jun. and 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, R. A. Shore and 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 [C. G. Jockusch jun. and 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 [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 ultrahigh sets, which were introduced in [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 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, inter alia, of the so-called box promotion technique, introduced in [P. Cholak et al., Adv. Math. 217, No. 5, 2045–2074, (2008; Zbl 1134.03026)].

MSC:

03D25 Recursively (computably) enumerable sets and degrees
PDFBibTeX XMLCite
Full Text: DOI