Slow versus fast growing (Q1868156)

This is a survey article on majorization hierarchies. The starting example is the Grzegorczyk hierarchy \((F_l)\). It characterizes the primitive recursive functions in the following way: 1. Every function of the hierarchy is primitive recursive. 2. For any primitive recursive \(g:\mathbb N^k \rightarrow \mathbb N\) there exists \(l\in \mathbb N\) such that \(\forall\overrightarrow x \in \mathbb N^k g(\overrightarrow x) < F_l(\max (\overrightarrow x))\). This is expressed by: The primitive recursive functions are majorized by the Grzegorczyk hierarchy. Another example: The \((l+2)\)-ary Ackermann functions majorize the multiple recursive functions. Extending this hierarchy into the transfinite, the Schwichtenberg-Wainer-hierarchy is gained (in case of extension up to \(\varepsilon_0\)). By this hierarchy several classes of functions are majorized, for instance Kreisel's ordinal recursive functions and the provably recursive functions of first-order Peano arithmetic. Moreover this hierarchy is used to classify the complexity of Gödel's system \(T\). These examples suggest general investigations of majorizing hierarchies. Behind these studies may be the hope of classifying the class of all recursive functions. For such hierarchies of ordinal recursive functions, fundamental sequences of ordinals are needed. They have to satisfy certain natural properties which are fulfilled by the fundamental sequences of the examples above. But the larger the intended hierarchies are the more complicated their fundamental sequences have to be. To overcome this difficulty it is helpful to count the symbols occurring in the ordinals used in the fundamental sequences. The hierarchies mentioned so far are called fast growing because even for small arguments the values of the used functions become large. Their counterparts are the slow growing hierarchies. The difference can be illustrated by the following examples: \[ \begin{alignedat}{2} H_0(x) & = x &G_0(x) & = 0\\ H_{\alpha +1}(x) & = H_\alpha(x+1)\quad &G_{\alpha +1}(x) & = G_\alpha(x)+1\\ H_\lambda(x)& = H_{\lambda[x]}(x) &G_\lambda(x) & = G_{\lambda[x]}(x) \end{alignedat} \] Cichon and Wainer call the slow growing hierarchies the most natural ones. Historically the slow growing hierarchy was developed as a hierarchy over the predicative ordinals (i.e. over \(\Gamma_0\)) which catches up with the fast growing hierarchy over \(\Gamma_0\) by a suitable generation process. Both kinds of hierarchies are compared by several authors. In the paper under review some of the results are commented upon and listed up together with the related formal systems. The problem of matching up between the slow growing and the fast growing hierarchies is more complicated for hierarchies resulting from the Buchholz ordinal notations and the associated fundamental sequences. Some new results on this topic are sketched, among them the answer of the author to a question of T. Arai. In the last section some surprising properties of the slow growing hierarchy are presented. They result from the fact stated by Cichon, Arai, and the author that the slow growing hierarchies are extremely sensitive to the choice of the underlying fundamental sequences. This can be summarized as follows: The slow growing hierarchy is either slow or fast growing. Thus it cannot be expected to describe the conditions under which fundamental sequences are most natural. The author illustrates the situation by examples and also by some new result. As a résumé the author proposes to introduce different kinds of slow growing hierarchies using Girard's term of pointwise hierarchy.