Variations on a Theme by Weiermann
Arai, Toshiyasu
J. Symbolic Logic, Tome 63 (1998) no. 1, p. 897-925 / Harvested from Project Euclid
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 $\theta\alpha$n is described as follows. For each ordinal $\alpha$ and natural number n let T$^\alpha_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$^\alpha_n$ is well founded and hence finite by Konig's lemma. Define $\theta\alpha$n=the depth of the tree T$^\alpha_n$=the length of the longest branch in T$^\alpha_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.
Publié le : 1998-09-14
Classification: 
@article{1183745573,
     author = {Arai, Toshiyasu},
     title = {Variations on a Theme by Weiermann},
     journal = {J. Symbolic Logic},
     volume = {63},
     number = {1},
     year = {1998},
     pages = { 897-925},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745573}
}
Arai, Toshiyasu. Variations on a Theme by Weiermann. J. Symbolic Logic, Tome 63 (1998) no. 1, pp.  897-925. http://gdmltest.u-ga.fr/item/1183745573/