×

Completing pseudojump operators. (English) Zbl 1085.03031

For a set of natural numbers \(X\) and an index \(e\), the \(e\)th pseudojump operator \(J_e\) is defined as \(X\oplus W_e^X\). For a pseudojump operator \(V\), if \(X<_T V^X\) for all \(X\in {\mathcal C}\), \(V\) is called uniformly nontrivial with respect to \(\mathcal C\). If \(\mathcal C\) is the set of all reals, then \(V\) is strongly nontrivial. In this paper, the authors firstly consider the existence of incomparable c.e. sets completing pseudojump operators, and the question of the existence of sets not of c.e. degree completing pseudojump operators. They prove that for any uniformly nontrivial pseudojump operator \(V\) with respect to all c.e. sets, there exist Turing-incomparable computably enumerable sets \(A\) and \(B\) such that \(V^A\equiv_T V^B \equiv_T K\). They also prove that for any nontrivial pseudojump operator \(U\) with respect to all d.c.e. sets, there exists a d.c.e. set \(A\) such that \(U^A\equiv_T K\) and the degree of \(A\) is not c.e. They also illustrate how independent nontriviality with respect to one class of sets can be from nontriviality with respect to another even closely related class. They prove that for every \(n>0\) there exists a pseudojump operator \(U\) and a co-\(n\)-c.e. set \(A\) such that \(A\equiv_T U^A\), but \(X<U^X\) for all \(n\)-c.e. sets \(X\). The most surprising result they prove in the paper is the impossibility of requiring cone-avoidance in a pseudojump completion theorem, given what seems to be a natural nontriviality hypothesis. Thus the usual restraint functions for avoiding cones are not compatible with the pseudojump completion theorem. The theorem states that there exists a non-computable c.e. set \(C\) and a pseudojump operator \(U\) such that (1) for every \(e\in\omega\), \(W_e<_T U^{W_e}\), and (2) for every \(e\in\omega\), if \(U^{W_e}\equiv_T K\), then \(C\leq_T W_e\). Finally, they raise seven open questions with regard to pseudojump operators.

MSC:

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

References:

[1] Downey, R.; Lempp, S., Contiguity and distributivity in the computably enumerable Turing degrees, J. Symbolic Logic, 62, 1215-1240 (1997) · Zbl 0897.03047
[2] Jockusch, C.; Shore, R., Pseudojump operators I: the r.e. case, Trans. Amer. Math. Soc., 275, 2, 599-609 (1983) · Zbl 0514.03028
[3] Jockusch, C.; Shore, R., Pseudojump operators II: transfinite iterations, hierarchies, and minimal covers, J. Symbolic Logic, 49, 1205-1236 (1984) · Zbl 0574.03026
[4] Shore, R., A non-inversion theorem for the jump operator, Ann. Pure Appl. Logic, 40, 277-303 (1988) · Zbl 0658.03024
[5] Soare, R., Recursively Enumerable Sets and Degrees (1987), Springer: Springer Berlin · Zbl 0623.03042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.