Some properties of graphs of functions in the Grzegorczyk hierarchy

S. V. Pakhomov

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part V, Tome 32 (1972), pp. 105-107

Résumé

Let $\Gamma^n$ be the set of all primitive recursive functions whose graphs belong to $\varepsilon^n$ [I]. It is proved that $\Gamma^n$ is the closure of $\varepsilon^n$ relative to identification and permutation of variables, to substitution of constants and to special operations I)–4) on p.p. 105–106. In particular $f_n\in\Gamma^0$ for every $n\geq 3$. Here $f_n$ is a modification of Ackermana's function described in [I] p. 30.