Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-21T18:20:51.707Z Has data issue: false hasContentIssue false
  • English
  • Français

Classifying the Provably Total Functions of PA

Published online by Cambridge University Press:  15 January 2014

Andreas Weiermann
Andreas Weiermann*
Affiliation:
Mathematical Institute, P.O. Box 80010, 3508 TA Utrecht, TheNetherlandsE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We give a self-contained and streamlined version of the classification of the provably computable functions of PA. The emphasis is put on illuminating as well as seems possible the intrinsic computational character of the standard cut elimination process. The article is intended to be suitable for teaching purposes and just requires basic familiarity with PA and the ordinals below ε0. (Familiarity with a cut elimination theorem for a Gentzen or Tait calculus is helpful but not presupposed).

Type
Articles
Information
Bulletin of Symbolic Logic , Volume 12 , Issue 2 , June 2006 , pp. 177 - 190
Copyright
Copyright © Association for Symbolic Logic 2007

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] Ackermann, W., Zur Widerspruchsfreiheit der reinen Zahlentheorie, Mathematische Annalen, vol. 117 (1940).Google Scholar
[2] Avigad, J. and Sommer, R., A model-theoretic approach to ordinal analysis, this Bulletin, vol. 3 (1997), no. 1, pp. 17–52.Google Scholar
[3] Blankertz, B. and Weiermann, A., How to characterize provably total functions by the Buchholz operator method, Lecture Notes in Logic, vol. 6, Springer, 1996, pp. 205–213.Google Scholar
[4] Buchholz, W., Notation systems for infinitary derivations, Archive for Mathematical Logic, vol. 30 (1991), no. 5/6, pp. 277–296.CrossRefGoogle Scholar
[5] Buchholz, W., A simplified version of local predicativity, Proof theory: a selection of papers from the Leeds proof theory meeting 1990 (Aczel, P., Simmons, H., and Wainer, S.S., editors), Cambridge University Press, 1992, pp. 115–148.Google Scholar
[6] Buchholz, W., Lectures Notes Logic I, II and Proof Theory, Online available under: http://www.mathematik.uni-muenchen.de/~buchholz/.Google Scholar
[7] Buchholz, W., Cichon, A., and Weiermann, A., A uniform approach to fundamental sequences and hierarchies, Mathematical Logic Quarterly, vol. 40 (1994), pp. 273–286.Google Scholar
[8] Buchholz, W. and Wainer, S. S., Provably computable functions and the fast growing hierarchy, Logic and combinatorics, Contemporary Mathematics, vol. 65, American Mathematical Society, 1987, pp. 179–198. 2This was the topic of a seminar by the author in Utrecht which followed his proof and recursion theory lecture. 190 andreas weiermannCrossRefGoogle Scholar
[9] Cichon, E. A., A short proof of two recently discovered independence results using recursion theoretic methods, Proceedings of the AMS, vol. 87, 1983, pp. 704–706.Google Scholar
[10] Fairtlough, M. and Wainer, S. S., Hierarchies of provably recursive functions, Handbook of proof theory, Studies in Logic and the Foundation of Mathematics, vol. 137, North-Holland, 1998, pp. 149–207.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.Google Scholar
[12] Gödel, K., Über eine bisher noch nicht benützte Erweiterung des finiten Standpunkts, Dialectica, vol. 12 (1958), pp. 280–287.CrossRefGoogle Scholar
[13] Hájek, P. and Pudlák, P., Metamathematics of first-order arithmetic, Springer, 1993.Google Scholar
[14] Kreisel, G., On the interpretation of non-finitist proofs II, The Journal of Symbolic Logic, vol. 17 (1952), pp. 43–58.CrossRefGoogle Scholar
[15] Pohlers, W., Proof theory. An introduction, Lecture Notes in Mathematics, vol. 1407, Springer, 1989.Google Scholar
[16] Pohlers, W., Subsystems of set theory and second order number theory, Handbook of proof theory, Studies in Logic and the Foundations of Mathematics, vol. 137, North-Holland, 1998, pp. 209–335.Google Scholar
[17] Rose, H. E., Subrecursion: Functions and hierarchies, Oxford University Press, 1984.Google Scholar
[18] Schütte, K., Proof theory, Springer, 1977.Google Scholar
[19] Schwichtenberg, H., Eine Klassifikation der ε0-rekursiven Funktionen, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, (1971), pp. 61–74.Google Scholar
[20] Schwichtenberg, H., Proof theory: Some applications of cut-elimination, Handbook of mathematical logic (Barwise, J., editor), North-Holland, 1977, pp. 867–895.Google Scholar
[21] Takeuti, G., Proof theory, 2nd ed., North-Holland, 1987.Google Scholar
[22] Wainer, S. S., A classification of the ordinal recursive functions, Archiv für Mathematische Logik, vol. 13 (1970), pp. 136–153.CrossRefGoogle Scholar
[23] Weiermann, A., How to characterize provably total functions by local predicativity, The Journal of Symbolic Logic, vol. 61 (1996), pp. 52–69.Google Scholar
[24] Weiermann, A., Analytic combinatorics, proof-theoretic ordinals, and phase transitions for independence results, Annals of Pure and Applied Logic, vol. 136 (2005), no. 1–2, pp. 189–218.Google Scholar