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.
@article{bwmeta1.element.bwnjournal-article-fmv141i1p1bwm,
author = {Z. Ratajczyk},
title = {Arithmetical transfinite induction and hierarchies of functions},
journal = {Fundamenta Mathematicae},
volume = {141},
year = {1992},
pages = {1-20},
zbl = {0809.03043},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-fmv141i1p1bwm}
}
Ratajczyk, Z. Arithmetical transfinite induction and hierarchies of functions. Fundamenta Mathematicae, Tome 141 (1992) pp. 1-20. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-fmv141i1p1bwm/
[00000] [1] G. Gentzen, Beweisbarkeit und Unbeweisbarkeit von Anfangsfählen der transfiniten Induktion in der reinen Zahlentheorie, Math. Ann. 119 (1943), 140-161. | Zbl 0028.10201
[00001] [2] P. Hájek and J. Paris, Combinatorial principles concerning approximations of functions, Arch. Math. Logik Grundlag. 26 (1987), 13-28. | Zbl 0645.03057
[00002] [3] J. Ketonen and R. Solovay, Rapidly growing Ramsey functions, Ann. of Math. 113 (1981), 267-314. | Zbl 0494.03027
[00003] [4] H. Kotlarski and Z. Ratajczyk, Inductive full satisfaction classes, Ann. Pure Appl. Logic 47 (1990), 199-223. | Zbl 0708.03014
[00004] [5] K. McAloon, Paris-Harrington incompleteness and progressions of theories, in: Proc. Sympos. Pure Math. 42, Amer. Math. Soc., 1985, 447-460. | Zbl 0589.03028
[00005] [6] J. Paris and L. Harrington, A mathematical incompleteness in Peano arithmetic, in: Handbook of Mathematical Logic, North-Holland, 1977, 1133-1142.
[00006] [7] Z. Ratajczyk, A combinatorial analysis of functions provably recursive in , Fund. Math. 130 (1988), 191-213.
[00007] [8] Z. Ratajczyk, Subsystems of the true arithmetic and hierarchies of functions, Ann. Pure Appl. Logic, to appear.
[00008] [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.
[00009] [10] D. Schmidt, Built-up systems of fundamental sequences and hierarchies of number-theoretic functions, Arch. Math. Logik Grundlag. 18 (1976), 47-53. | Zbl 0358.02061
[00010] [11] S. Wainer, Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy, J. Symbolic Logic 37 (1972), 281-292. | Zbl 0261.02031