Journal of Symbolic Logic 63 (3):897-925 (1998)
Weiermann  introduces a new method to generate fast growing functions in order to get an elegant and perspicuous proof of a bounding theorem for provably total recursive functions in a formal theory, e.g., in PA. His fast growing function θαn is described as follows. For each ordinal α and natural number n let T α n denote a finitely branching, primitive recursive tree of ordinals, i.e., an ordinal as a label is attached to each node in the tree so that the labelling is compatible with the tree ordering. Then the tree T α n is well founded and hence finite by Konig's lemma. Define θαn=the depth of the tree T α n =the length of the longest branch in T α n . We introduce new fast and slow growing functions in this mode of definitions and show that each of these majorizes provably total recursive functions in PA
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
References found in this work BETA
A Uniform Approach to Fundamental Sequences and Hierarchies.Wilfried Buchholz, Adam Cichon & Andreas Weiermann - 1994 - Mathematical Logic Quarterly 40 (2):273-286.
Elementary Descent Recursion and Proof Theory.Harvey Friedman & Michael Sheard - 1995 - Annals of Pure and Applied Logic 71 (1):1-45.
Proof-Theoretic Analysis of Termination Proofs.Wilfried Buchholz - 1995 - Annals of Pure and Applied Logic 75 (1-2):57-65.
Transfinite Induction Within Peano Arithmetic.Richard Sommer - 1995 - Annals of Pure and Applied Logic 76 (3):231-289.
A Slow Growing Analogue to Buchholz' Proof.Toshiyasu Arai - 1991 - Annals of Pure and Applied Logic 54 (2):101-120.
Citations of this work BETA
2004 Summer Meeting of the Association for Symbolic Logic.Wolfram Pohlers - 2005 - Bulletin of Symbolic Logic 11 (2):249-312.
Similar books and articles
An Application of Graphical Enumeration to PA.Andreas Weiermann - 2003 - Journal of Symbolic Logic 68 (1):5-16.
A Uniform Approach for Characterizing the Provably Total Number-Theoretic Functions of KPM and its Subsystems.Benjamin Blankertz & Andreas Weiermann - 1999 - Studia Logica 62 (3):399-427.
How to Characterize Provably Total Functions by Local Predicativity.Andreas Weiermann - 1996 - Journal of Symbolic Logic 61 (1):52-69.
Classifying the Provably Total Functions of Pa.Andreas Weiermann - 2006 - Bulletin of Symbolic Logic 12 (2):177-190.
Minimal Realizability of Intuitionistic Arithmetic and Elementary Analysis.Zlatan Damnjanovic - 1995 - Journal of Symbolic Logic 60 (4):1208-1241.
A Buchholz Derivation System for the Ordinal Analysis of KP + Π₃-Reflection.Markus Michelbrink - 2006 - Journal of Symbolic Logic 71 (4):1237 - 1283.
Some Interesting Connections Between the Slow Growing Hierarchy and the Ackermann Function.Andreas Weiermann - 2001 - Journal of Symbolic Logic 66 (2):609-628.
Added to index2009-01-28
Total downloads10 ( #424,116 of 2,153,834 )
Recent downloads (6 months)1 ( #398,274 of 2,153,834 )
How can I increase my downloads?