Completing pseudojump operators (Q2570139): Difference between revisions

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.