An extremely sharp phase transition threshold for the slow growing hierarchy

摘要

We investigate natural systems of fundamental sequences for ordinals below the Howard-Bachmann ordinal and study growth rates of the resulting slow growing hierarchies. We consider a specific assignment of fundamental sequences that depends on a non-negative real number epsilon. We show that the resulting slow growing hierarchy is eventually dominated by a fixed elementary recursive function if epsilon is equal to zero. We show further that the resulting slow growing hierarchy exhausts the provably recursive functions of ID1 if epsilon is strictly greater than zero. Finally, we show that the resulting fast growing hierarchies exhaust the provably recursive functions of ID1 for all non-negative values of epsilon Our result is somewhat surprising since usually the slow growing hierarchy along the Howard-Bachmann ordinal exhausts precisely the provably recursive functions of PA. Note that the elementary functions are a very small subclass of the provably recursive functions of PA, and the provably recursive functions of PA are a very small subclass of the provably recursive functions of ID1. Thus the jump from epsilon equal to zero to epsilon greater than zero is one of the biggest jumps in growth rates for subrecursive hierarchies one might think of.