Sometimes slow growing is fast growing

Annals of Pure and Applied Logic 90 (1-3):91-99 (1997)
  Copy   BIBTEX

Abstract

The slow growing hierarchy is commonly defined as follows: G0 = 0, Gx−1 := Gx + 1 and Gλ := Gλ[x] where λ<0 is a limit and ·[·]:0∩ Lim × ω → 0 is a given assignment of fundamental sequences for the limits below 0. The first obvious question which is encountered when one looks at this definition is: How does this hierarchy depend on the choice of the underlying system of fundamental sequences? Of course, it is well known and easy to prove that for the standard assignment of fundamental sequence the hierarchy x<0 is slow growing, i.e. each Gx is majorized by a Kalmar elementary recursive function.It is shown in this paper that the slow growing hierarchy x<0 — when it is defined with respect to the norm-based assignment of fundamental sequences which is defined in the article by Cichon — is actually fast growing, i.e. each PA-provably recursive function is eventually dominated by Gx for some α<0. The exact classification of this hierarchy, i.e. the problem whether it is slow or fast growing, has been unsolved since 1992. The somewhat unexpected result of this paper shows that the slow growing hierarchy is extremely sensitive with respect to the choice of the underlying system of fundamental sequences.The paper is essentially self-contained. Only little knowledge about ordinals less than 0 — like the existence of Cantor normal forms, etc. and the beginnings of subrecursive hierarchy theory as presented, for example, in the 1984 textbook of Rose — is assumed

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Slow versus fast growing.Andreas Weiermann - 2002 - Synthese 133 (1-2):13 - 29.
Slow growing versus fast growing.S. S. Wainer - 1989 - Journal of Symbolic Logic 54 (2):608-614.
Γ0 May Be Minimal Subrecursively Inaccessible.Andreas Weiermann - 2001 - Mathematical Logic Quarterly 47 (3):397-408.
Variations on a theme by Weiermann.Toshiyasu Arai - 1998 - Journal of Symbolic Logic 63 (3):897-925.
The" Slow-Growing" U\ Approach to Hierarchies.S. S. Wainer - 1985 - In Anil Nerode & Richard A. Shore (eds.), Recursion Theory. American Mathematical Society. pp. 42--487.
The slow-growing and the grzecorczyk hierarchies.E. A. Cichon & S. S. Wainer - 1983 - Journal of Symbolic Logic 48 (2):399-408.
A slow growing analogue to buchholz' proof.Toshiyasu Arai - 1991 - Annals of Pure and Applied Logic 54 (2):101-120.

Analytics

Added to PP
2014-01-16

Downloads
22 (#606,933)

6 months
4 (#319,344)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Slow consistency.Sy-David Friedman, Michael Rathjen & Andreas Weiermann - 2013 - Annals of Pure and Applied Logic 164 (3):382-393.
Slow versus fast growing.Andreas Weiermann - 2002 - Synthese 133 (1-2):13 - 29.

Add more citations

References found in this work

Add more references