Streamlined subrecursive degree theory
type: Item
instance of: scholarly article
title: Streamlined subrecursive degree theory
zbMATH Open document ID: 1245.03063
author: Lars Kristiansen
author: Jan-Christoph Schlage-Puchta
author: Andreas Weiermann
published in: Annals of Pure and Applied Logic
publication date: 2012-03-29T00:00:00Z
review text: The paper under review consists of two parts. Part I is devoted to the investigation of the structure of honest elementary degrees, i.e., the degree structure induced on the honest functions by the reducibility relation ``being (Kalmar) elementary in''. In Part II the degree theory found in Part I is generalized. The reducibility relation ``being \(\alpha\)-elementary in'', where \(\alpha\) is an ordinal \(\leq \varepsilon_{0}\), is introduced and the structure of honest \(\alpha\)-elementary degrees is investigated. Relations between the degree theory developed in the paper and provability in Peano arithmetic is also discussed.
reviewed by: Roman Murawski
Mathematics Subject Classification ID: 03D20
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 6019358
zbMATH Keywords: subrecursive degrees
zbMATH Keywords: honest functions
zbMATH Keywords: provability in PA
MaRDI profile type: Publication
full work available at URL: j.apal.2011.11.004
OpenAlex ID: W2015272527
cites work: Q4893145
cites work: A Uniform Approach to Fundamental Sequences and Hierarchies
cites work: Q4893148
cites work: A jump operator on honest subrecursive degrees
cites work: Subrecursive degrees and fragments of Peano arithmetic
cites work: Q4503966
cites work: Q4354788
cites work: Augmented loop languages and classes of computable functions
cites work: The honest subrecursive classes are a lattice
cites work: On the density of honest subrecursive classes
cites work: A Classification of the Recursive Functions
cites work: Classical recursion theory. Vol. II
cites work: Q3241197
cites work: Q5573961
cites work: Q3325707
DOI: 10.1016/J.APAL.2011.11.004
description: scientific article; zbMATH DE number 6019358