Subrecursive degrees and fragments of Peano arithmetic
type: Item
instance of: scholarly article
title: Subrecursive degrees and fragments of Peano arithmetic
zbMATH Open document ID: 0982.03022
author: Lars Kristiansen
published in: Archive for Mathematical Logic
publication date: 2002-03-19T00:00:00Z
review text: Let \(T_{0} \leq T_{1}\) denote that each computable function which is provably total in the first order theory \(T_{0}\) is also provably total in the first oder theory \(T_{1}\). The relation \(\leq\) induces a degree structure on the sound finite \(\Pi_{2}\) extensions of EA (Elementary Arithmetic). The paper under review is devoted to the study of this structure. An isomorphic subrecursive degree structure \((\leq, {\mathcal S})\) is defined and studied by subrecursive and computability-theoretic means. Further some operators on the degrees of \((\leq, {\mathcal S})\) are introduced and investigated. It is shown that they correspond to some rules in formal arithmetic (e.g., to the \(\Sigma_{1}\) collection rule and to the \(\Sigma_{1}\) induction rule).
reviewed by: Roman Murawski
Mathematics Subject Classification ID: 03D20
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 1657163
zbMATH Keywords: subrecursive degree structure
zbMATH Keywords: provably total computable function
zbMATH Keywords: extensions of elementary arithmetic
zbMATH Keywords: first-order theories
MaRDI profile type: Publication
DOI: 10.1007/S001530000066
description: scientific article; zbMATH DE number 1657163