Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-28T17:10:15.021Z Has data issue: false hasContentIssue false
  • English
  • Français

Variations on a theme by Weiermann

Published online by Cambridge University Press:  12 March 2014

Toshiyasu Arai
Toshiyasu Arai*
Affiliation:
Faculty of Integrated Arts and Sciences, Hiroshima University, Higashi-Hiroshima, 739-8521, Japan E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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 θαη is described as follows. For each ordinal a and natural number n let 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 is well founded and hence finite by König's lemma. Define θαηn =the depth of the tree =the length of the longest branch in .

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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 63 , Issue 3 , September 1998 , pp. 897 - 925
Copyright
Copyright © Association for Symbolic Logic 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Arai, T., Some results on cut-elimination, provable well-orderings, induction and reflection, to appear in Annals of Pure and Applied Logic.Google Scholar
[2]Arai, T., On Takeuti's fundamental conjecture (Japanese), Sûgaku, vol. 40 (1988), pp. 322–337, MR 90f:03091 and Zbl. Math. 689 03f:03026.Google Scholar
[3]Arai, T., Proof theory for theories of ordinals I.Π2-reflecting ordinals, manuscript, 02 1989.Google Scholar
[4]Arai, T., A slow growing analogue to Buchholz' proof, Annals of Pure and Applied Logic, vol. 54 (1991), pp. 101–120.CrossRefGoogle Scholar
[5]Arai, T., Systems of ordinal diagrams, manuscript, 08 1996.Google Scholar
[6]Arai, T., Consistency proof via pointwise induction, Archives for Mathematical Logic, vol. 37 (1998), pp. 149–165.CrossRefGoogle Scholar
[7]Buchholz, W., An independence result for ( – CA) + BI, Annals of Pure and Applied Logic, vol. 33 (1987), pp. 131–155.CrossRefGoogle Scholar
[8]Buchholz, W., Proof-theoretic analysis of termination proofs, Annals of Pure and Applied Logic, vol. 75 (1995), pp. 57–65.CrossRefGoogle Scholar
[9]Buchholz, W., Cichon, E. A., and Weiermann, A., A uniform approach to fundamental sequences and hierarchies, Mathematical Logic Quarterly, vol. 40 (1994), pp. 273–286.CrossRefGoogle Scholar
[10]Cichon, E. A., Termination orderings and complexity characterizations, Proof theory (Aczel, P.et al., editors), Cambridge University Press, Cambridge, 1992, pp. 171–193.Google Scholar
[11]Friedman, H. and Sheard, M., Elementary descent recursion and proof theory, Annals of Pure and Applied Logic, vol. 71 (1995), pp. 1–45.CrossRefGoogle Scholar
[12]Hájek, P. and Pudlák, P., Metamathematics of first order arithmetic, Springer-Verlag, 1993.CrossRefGoogle Scholar
[13]Pohlers, W., A short course in ordinal analysis, Proof theory (Aczel, P.et al., editors), Cambridge University Press, Cambridge, 1992, pp. 27–78.Google Scholar
[14]Schmerl, U. R., Afine structure generated by reflection formulas over primitive recursive arithmetic, Logic Colloquium 78 (Boffa, M., editor), North-Holland, Amsterdam, 1979, pp. 335–350.Google Scholar
[15]Sommer, R., Transfinite induction within Peano arithmetic, Annals of Pure and Applied Logic, vol. 76 (1995), pp. 231–289.CrossRefGoogle Scholar
[16]Takeuti, G., Proof theory, second ed., North-Holland, 1987.Google Scholar
[17]Weiermann, A., Bounding derivation lengths with functions from the slow growing hierarchy, submitted.Google Scholar
[18]Weiermann, A., How to characterize provably total functions by local predicativity, this Journal, vol. 61 (1996), pp. 52–69.Google Scholar
[19]Weiermann, A., On the slow growing hierarchy via Cichon's fundamental sequences, manuscript, 02 1996.Google Scholar
[20]Weiermann, A., Outer iteration together with lengths bounded transfinite recursion does not yield slow growingness, draft, 04 1996.Google Scholar
[21]Weiermann, A., Sometimes slow growing is fast growing, draft, 04 1996.Google Scholar