Upper bounds for the arithmetical degrees

DOI10.1016/0168-0072(85)90001-6MaRDI QIDQ1086229zbMATH OpenOpenAlexFDO

Authors Manuel Lerman

Publication date 1985

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(85)90001-6

zbMATH Keywords

arithmetical functionsarithmetical setsgeneralized high/low hierarchyjumps of upper bounds

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Review text

We show that there is an upper bound \(\underset \tilde{} d\) for the arithmetical degrees such that \(\underset \tilde{} d'\geq \underset \tilde{} 0^{(\omega)}\) but \(\underset \tilde{} d\) is not the degree of a subuniform upper bound for the arithmetical sets. It then follows that this degree is not the degree of a model of the elementary theory of the semiring of natural numbers. We next turn to comparisons of the upper bounds for the arithmetical degrees below \(\underset \tilde{} 0^{(\omega)}\) and the degrees below \(\underset \tilde{} 0^{(2)}\). We show that all uniform upper bounds for the arithmetical functions bound minimal upper bounds for the arithmetical degrees. We then introduce a counterpart of the generalized high/low hierarchy which is useful for studying upper bounds for the arithmetical degrees. We first locate minimal upper bounds for the arithmetical degrees within this hierarchy. We then give a direct proof of a result hidden in a paper of \textit{J. Knight}, \textit{A. H. Lachlan}, and \textit{R. I. Soare} [J. Symb. Logic 49, 425-436 (1984; Zbl 0576.03044)] which relates jumps of upper bounds for the arithmetical degrees to uniform upper bounds for the arithmetical functions. Finally, we determine which classes of this hierarchy are non-empty. The conclusion discusses open questions.

Recommendations

• Minimal upper bounds for arithmetical degrees
• Models of arithmetic and subuniform bounds for the arithmetic sets
• Minimal complementation below uniform upper bounds for the arithmetical degrees
• Models of arithmetic and upper bounds for arithmetic sets
• Degrees which do not bound minimal degrees

Cites work

• A degree-theoretic definition of the ramified analytical hierarchy
• A minimal degree not realizing least possible jump
• A note on the hyperarithmetical hierarchy
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• Degrees in Which the Recursive Sets are Uniformly Recursive
• Degrees joining to 0′
• Degrees of Recursively Saturated Models
• Double jumps of minimal degrees
• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 3825809 (Why is no real title available?)
• scientific article; zbMATH DE number 3732037 (Why is no real title available?)
• scientific article; zbMATH DE number 3358471 (Why is no real title available?)
• Jumping to a Uniform Upper Bound
• Minimal degrees and the jump operator
• On degrees of recursive unsolvability
• Simple Proofs of Some Theorems on High Degrees of Unsolvability
• Two theorems on degrees of models of true arithmetic
• Uniform upper bounds on ideals of turing degrees

Cited in

(9)

• Towards a theory of arithmetic degrees
• Minimal complementation below uniform upper bounds for the arithmetical degrees
• Completions of PA: Models and enumerations of representable sets
• Minimal upper bounds for arithmetical degrees
• Models of arithmetic and upper bounds for arithmetic sets
• Models of arithmetic and subuniform bounds for the arithmetic sets
• 1998–99 Annual Meeting of the Association for Symbolic Logic
• Bounds for the degrees in the division problem
• On some filters and ideals of the Medvedev lattice

This page was built for publication: Upper bounds for the arithmetical degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1086229)