Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones |
| |
| Authors: | Andreas Weiermann |
| |
| Institution: | 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 ofACA
0 + (
1
l
–TR).] In particular let 
a
denote the enumeration function of the infinite cardinals and leta  0
a denote the partial collapsing operation on T() which maps ordinals of T() into the countable segment T
0 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_{ln]} (n),} \\ \end{array} } & {\begin{array}{*{20}c} {F_{a + 1} (n): = \underbrace {F_a (...F_a }_{n + 1 - times}(n)...),} \\ {F_l (n): = F_{ln]} (n),} \\ \end{array} } \\ \end{array}$$](/content/L47J01782530W1X6/153_2005_Article_BF01387511_TeX2GIFE1.gif)