Definability in the Recursively Enumerable Degrees (Q3128481)

Let \(\mathcal R\) be the r.e. degrees with the usual partial order of Turing reducibility. This paper's main theorem is that in \(\mathcal R\) there is a definable copy \({\mathcal N}_0\) of the structure \(({\mathcal N},+,\times)\) and a definable map \(f:{\mathcal R}\to{\mathcal N}_0\) such that \(f({\mathbf a})\) is the code for the least index of some r.e. set whose double jump belongs to the double jump of \({\mathbf a}\). This comes ``within two jumps'' of a conjecture of Harrington, Slaman, and Woodin, which was the natural variant of this theorem that lacks the double jumps. Cooper showed in 1996 that their conjecture fails, so that the present theorem is the best possible. A relation is invariant in \(\mathcal R\) if automorphisms preserve it, invariant under the double jump if preserved when its arguments are replaced by degrees with the same double jumps. Among corollaries of the theorem: a relation is invariant in \(\mathcal R\) if it is invariant under double jump; any arithmetically definable relation that is invariant under double jump is definable in \(\mathcal R\); for \(k\geq 3\), the relation of having the same \(k\)th jump is definable in \(\mathcal R\); the class of \(\text{high}_n\) degrees is definable in \(\mathcal R\) for \(n\geq 1\), and so is the class of \(\text{low}_n\) degrees for \(n\geq 2\). (By Cooper's result, the class of \(\text{low}=\text{low}_1\) degrees is not definable in \(\mathcal R\).) These corollaries (but not others) may all be relativized to \({\mathcal R}^{\mathbf z}\), the structure of degrees r.e. in and above \({\mathbf z}\). The paper offers open questions and conjectures regarding the number and definability of automorphisms of \(\mathcal R\) and the definability in \(\mathcal R\) of individual degrees.