Arithmetical transfinite induction and hierarchies of functions

• Autorzy: Z. Ratajczyk
• Języki publikacji: EN

Abstrakty

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.

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Fundamenta Mathematicae
• Rocznik: 1992
• Tom: 141
• Numer: 1
• Strony: 1-20

Daty

wydano

1992

otrzymano

1990-10-15

poprawiono

1991-09-26

Twórcy

autor

Z. Ratajczyk

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

Bibliografia

• [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.