Variations on a theme by weiermann

摘要

Weiermann [18] 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 nod 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.