Arithmetical transfinite induction and hierarchies of functions

Z. Ratajczyk

Fundamenta Mathematicae (1992)

  • Volume: 141, Issue: 1, page 1-20
  • ISSN: 0016-2736

Abstract

top
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.

How to cite

top

Ratajczyk, Z.. "Arithmetical transfinite induction and hierarchies of functions." Fundamenta Mathematicae 141.1 (1992): 1-20. <http://eudml.org/doc/211948>.

@article{Ratajczyk1992,
author = {Ratajczyk, Z.},
journal = {Fundamenta Mathematicae},
keywords = {arithmetical transfinite induction; Wainer Theorem; Paris-Harrington Theorem; Solovay-Ketonen Theorem},
language = {eng},
number = {1},
pages = {1-20},
title = {Arithmetical transfinite induction and hierarchies of functions},
url = {http://eudml.org/doc/211948},
volume = {141},
year = {1992},
}

TY - JOUR
AU - Ratajczyk, Z.
TI - Arithmetical transfinite induction and hierarchies of functions
JO - Fundamenta Mathematicae
PY - 1992
VL - 141
IS - 1
SP - 1
EP - 20
LA - eng
KW - arithmetical transfinite induction; Wainer Theorem; Paris-Harrington Theorem; Solovay-Ketonen Theorem
UR - http://eudml.org/doc/211948
ER -

References

top
  1. [1] G. Gentzen, Beweisbarkeit und Unbeweisbarkeit von Anfangsfählen der transfiniten Induktion in der reinen Zahlentheorie, Math. Ann. 119 (1943), 140-161. Zbl0028.10201
  2. [2] P. Hájek and J. Paris, Combinatorial principles concerning approximations of functions, Arch. Math. Logik Grundlag. 26 (1987), 13-28. Zbl0645.03057
  3. [3] J. Ketonen and R. Solovay, Rapidly growing Ramsey functions, Ann. of Math. 113 (1981), 267-314. Zbl0494.03027
  4. [4] H. Kotlarski and Z. Ratajczyk, Inductive full satisfaction classes, Ann. Pure Appl. Logic 47 (1990), 199-223. Zbl0708.03014
  5. [5] K. McAloon, Paris-Harrington incompleteness and progressions of theories, in: Proc. Sympos. Pure Math. 42, Amer. Math. Soc., 1985, 447-460. Zbl0589.03028
  6. [6] J. Paris and L. Harrington, A mathematical incompleteness in Peano arithmetic, in: Handbook of Mathematical Logic, North-Holland, 1977, 1133-1142. 
  7. [7] Z. Ratajczyk, A combinatorial analysis of functions provably recursive in I Σ n , Fund. Math. 130 (1988), 191-213. 
  8. [8] Z. Ratajczyk, Subsystems of the true arithmetic and hierarchies of functions, Ann. Pure Appl. Logic, to appear. 
  9. [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. [10] D. Schmidt, Built-up systems of fundamental sequences and hierarchies of number-theoretic functions, Arch. Math. Logik Grundlag. 18 (1976), 47-53. Zbl0358.02061
  11. [11] S. Wainer, Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy, J. Symbolic Logic 37 (1972), 281-292. Zbl0261.02031

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.