In computability theory, computational complexity theory and proof theory, the slow-growing hierarchy is an ordinal-indexed family of slowly increasing functions g<sub>ñ</sub>: N â N (where N is the set of natural numbers, {0, 1, ...}). It contrasts with the fast-growing hierarchy.
Let ü be a large countable ordinal such that a fundamental sequence is assigned to every limit ordinal less than ü. The slow-growing hierarchy of functions g<sub>ñ</sub>: N â N, for ñ < ü, is then defined as follows:
Here ñ[n] denotes the n<sup>th</sup> element of the fundamental sequence assigned to the limit ordinal ñ.
The article on the fast-growing hierarchy describes a standardized choice for fundamental sequence for all ñ < õ<sub>0</sub>.
The slow-growing hierarchy grows much more slowly than the fast-growing hierarchy. Even g<sub>õ<sub>0</sub></sub> is only equivalent to f<sub>3</sub> and g<sub>ñ</sub> only attains the growth of f<sub>õ<sub>0</sub></sub> (the first function that Peano arithmetic cannot prove total in the hierarchy) when ñ is the BachmannâÂÂHoward ordinal.
However, Girard proved that the slow-growing hierarchy eventually catches up with the fast-growing one. Specifically, that there exists an ordinal ñ such that for all integers n
where f<sub>ñ</sub> are the functions in the fast-growing hierarchy. He further showed that the first ñ this holds for is the ordinal of the theory ID<sub><ÃÂ</sub> of arbitrary finite iterations of an inductive definition. However, for the assignment of fundamental sequences found in the first match up occurs at the level õ<sub>0</sub>. For Buchholz style tree ordinals it could be shown that the first match up even occurs at .
Extensions of the result proved to considerably larger ordinals show that there are very few ordinals below the ordinal of transfinitely iterated -comprehension where the slow- and fast-growing hierarchy match up.
The slow-growing hierarchy depends extremely sensitively on the choice of the underlying fundamental sequences.