Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones |
| |
| Authors: | Andreas Weiermann |
| |
| Affiliation: | 1. Institut für mathematische Logik und Grundlagenforschung der Westf?lischen Wilhelms-Universit?t Münster, Einsteinstrasse 62, D-48149, Münster, Germany
|
| |
| Abstract: | Let T( ) be the ordinal notation system from Buchholz-Schütte (1988). [The order type of the countable segmentT()0 is — by Rathjen (1988) — the proof-theoretic ordinal the proof-theoretic ordinal ofACA0 + ( 1l–TR).] In particular let  a denote the enumeration function of the infinite cardinals and leta  0a denote the partial collapsing operation on T() which maps ordinals of T() into the countable segment T0 of T(). Assume that the (fast growing) extended Grzegorczyk hierarchy and the slow growing hierarchy are defined with respect to the natural system of distinguished fundamental sequences of Buchholz and Schütte (1988) in the following way:
|
|
![$$begin{array}{*{20}c} {G_0 (n): = 0,} & {F_0 (n): = (n + 1)^2 ,} {begin{array}{*{20}c} {G_{a + 1} (n): = G_a (n) + 1,} {G_l (n): = G_{l[n]} (n),} end{array} } & {begin{array}{*{20}c} {F_{a + 1} (n): = underbrace {F_a (...F_a }_{n + 1 - times}(n)...),} {F_l (n): = F_{l[n]} (n),} end{array} } end{array}$$](/content/L47J01782530W1X6/153_2005_Article_BF01387511_TeX2GIFE1.gif)