A jump operator on honest subrecursive degrees (Q1128175)

It is well known that the structure of honest elementary degrees is a lattice with rather strong density properties. Let \({\mathbf a}\cup{\mathbf b}\) and \({\mathbf a}\cap{\mathbf b}\) denote, respectively, the join and the meet of the degrees \({\mathbf a}\) and \({\mathbf b}\). This paper introduces a jump operator \((\cdot')\) on the honest elementary degrees and defines canonical degrees \(\text{\textbf{0}},\text{\textbf{0}}',\text{\textbf{0}}'',\dots\) and low and high degrees analogous to the corresponding concepts for the Turing degrees. Among others, the following results about the structure of the honest elementary degrees are shown: There exist low degrees, and there exist degrees which are neither low nor high. Every degree above \(\text{\textbf{0}}'\) is the jump of some degree, moreover, for every degree \({\mathbf c}\) above \(\text{\textbf{0}}'\) there exist degrees \({\mathbf a}\), \({\mathbf b}\) such that \({\mathbf c}= {\mathbf a}\cup{\mathbf b}= {\mathbf a}'={\mathbf b}'\). We have \({\mathbf a}'\cup{\mathbf b}'\leq ({\mathbf a}\cup{\mathbf b})'\) and \({\mathbf a}'\cap{\mathbf b}'\geq ({\mathbf a}\cap {\mathbf b})'\). The jump operator is of course monotonic, i.e. \({\mathbf a}\leq{\mathbf b}\Rightarrow{\mathbf a}'\leq{\mathbf b}'\). We prove that every situation compatible with \({\mathbf a}\leq{\mathbf b}\Rightarrow{\mathbf a}'\leq{\mathbf b}'\) is realized in the structure, e.g. we have incomparable degrees \({\mathbf a}\), \({\mathbf b}\) such that \({\mathbf a}'<{\mathbf b}'\) and incomparable degrees \({\mathbf a}\), \({\mathbf b}\) such that \({\mathbf a}'={\mathbf b}'\) etc. We are able to prove all these results without the traditional recursion-theoretic constructions. Our proof method relies on the fact that the growth of the functions in a degree is bounded. This technique also yields a very simple proof of an old result, namely that the structure is a lattice.