What Makes A (Pointwise) Subrecursive Hierarchy Slow Growing?

Summary

Abstract

A subrecursive hierarchy (P_α)_α<ε0 of unary number-theoretic functions is called the slow growing if each _Pα is dominated by a Kalmar elementary recursive function. A subrecursive hierarchy (P_α)_α<ε0 is called pointwise if the value of P_α(x) can be computed recursively in terms of P_β(x) with β < α but with the same argument x. The point-wise hierarchy (G_α)_α<ε0 is defined recursively as follows: G₀(x) := 0; G_α+1(x) := 1 + G_α(x); G_λ(x) := G_λ[x](x) where λ is a limit and (λ[x])_x<ω is a distinguished fundamental sequence for λ. If (G_α)_α<ε0 is defined with respect to the standard system of fundamental sequences then (G_α)_α<ε0 is slow growing.

In the first part of the article we try to classify as well as seems possible those (natural) assignments of fundamental sequences for which the induced pointwise hierarchy remains slow growing or becomes fast growing in the sense that the resulting hierarchy matches up with the Schwichtenberg-Wainer hierarchy (F_α)_α<ε0. To exclude pathological cases we only consider elementary recursive assignments which are natural at least in the sense that their associated fast growing hierarchies classify exactly the provably recursive functions of PA. It turns out that the growth rate of the pointwise hierarchy is intrinsically connected with strong continuity properties of the assignment of fundamental sequences with respect to ordinal addition.