A jump operator on honest subrecursive degrees
type: Item
instance of: scholarly article
title: A jump operator on honest subrecursive degrees
zbMATH Open document ID: 0899.03031
author: Lars Kristiansen
published in: Archive for Mathematical Logic
publication date: 1998-08-10T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 1187516
zbMATH Keywords: jump operator
zbMATH Keywords: honest elementary degrees
zbMATH Keywords: high degrees
zbMATH Keywords: low degrees
zbMATH Keywords: lattice
MaRDI profile type: Publication
full work available at URL: s001530050086
OpenAlex ID: W2035245701
DOI: 10.1007/S001530050086
description: scientific article; zbMATH DE number 1187516