Download PDF - Arithmetical transfinite induction and hierarchies of functionsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Arithmetical transfinite induction and hierarchies of functions

Authors 1

Affiliations

  1. Institute of Mathematics, Warsaw University, Banacha 2, 00-913 Warszawa 59, Poland

Abstract

We generalize to the case of arithmetical transfinite induction the following three theorems for PA: the Wainer Theorem, the Paris-Harrington Theorem, and a version of the Solovay-Ketonen Theorem. We give uniform proofs using combinatorial constructions.

Bibliography

  1. G. Gentzen, Beweisbarkeit und Unbeweisbarkeit von Anfangsfählen der transfiniten Induktion in der reinen Zahlentheorie, Math. Ann. 119 (1943), 140-161.
  2. P. Hájek and J. Paris, Combinatorial principles concerning approximations of functions, Arch. Math. Logik Grundlag. 26 (1987), 13-28.
  3. J. Ketonen and R. Solovay, Rapidly growing Ramsey functions, Ann. of Math. 113 (1981), 267-314.
  4. H. Kotlarski and Z. Ratajczyk, Inductive full satisfaction classes, Ann. Pure Appl. Logic 47 (1990), 199-223.
  5. K. McAloon, Paris-Harrington incompleteness and progressions of theories, in: Proc. Sympos. Pure Math. 42, Amer. Math. Soc., 1985, 447-460.
  6. J. Paris and L. Harrington, A mathematical incompleteness in Peano arithmetic, in: Handbook of Mathematical Logic, North-Holland, 1977, 1133-1142.
  7. Z. Ratajczyk, A combinatorial analysis of functions provably recursive in IΣn, Fund. Math. 130 (1988), 191-213.
  8. Z. Ratajczyk, Subsystems of the true arithmetic and hierarchies of functions, Ann. Pure Appl. Logic, to appear.
  9. U. Schmerl, A fine structure generated by reflection formulas over primitive recursive arithmetic, in: Logic Colloquium 78, M. Boffa, K. McAloon and D. van Dalen (eds.), North-Holland, Amsterdam 1979, 335-350.
  10. D. Schmidt, Built-up systems of fundamental sequences and hierarchies of number-theoretic functions, Arch. Math. Logik Grundlag. 18 (1976), 47-53.
  11. S. Wainer, Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy, J. Symbolic Logic 37 (1972), 281-292.

Additional information

http://matwbn.icm.edu.pl/ksiazki/fm/fm141/fm14111.pdf

Fundamenta Mathematicae
1992/141/1
Export to PBN, Opens in new tab
Pages:
1-20
Main language of publication
English
Received
1990-10-15
Accepted
1991-09-26
Published
1992
Exact and natural sciences