A non-inversion theorem for the jump operator (Q1111549): Difference between revisions

The well-known Friedberg inversion theorem states that if \(\emptyset '\leq_ TB\), then there exists a set A such that \(A'\equiv_ TA\vee \emptyset '\equiv_ TB\), or in words, that every set above \(\emptyset '\) is in the range of the Turing jump operator. The Sacks inversion theorem states that every set, which is above \(\emptyset '\) and recursively enumerable in \(\emptyset '\), is the jump of a recursively enumerable set. The paper under review shows that the Friedberg inversion theorem can be extended to partial orders, while the Sacks inversion theorem cannot. The non-extendibility of the Sacks inversion theorem is a corollary of the main result: Theorem. There are degrees \(a_ 0\), \(a_ 1\) recursively enumerable in and above 0' such that the join \(a_ 0\vee a_ 1<0''\) and if \(u<0'\) then not both \(a_ 0\) and \(a_ 1\) are recursively enumerable in u. The proof introduces a novel \(0^{(3)}\) priority argument in which the tree of strategies is \(\omega +1\)-branching and so determining the true path requires a \(0^{(3)}\) oracle.