Plain bases for classes of primitive recursive functions (Q2776813)

The author investigates finite bases (the closure operation is substitution, and the bases are assumed to contain also projection functions) for L. Kalmár's class \(\mathbf{E}\) of elementary functions [\textit{L. Kalmár}, Mat. Fiz. Lapok 50, 1--23 (1943; Zbl 0063.03115)] as well as for A. Grzegorczyk's hierarchy \(\mathcal{E}^n\) [\textit{A. Grzegorczyk}, Some classes of recursive functions. Rozprawy Mat. 4 (1953; Zbl 0052.24902)] for \(n\geq 3\). A finite basis for \(\mathbf{E}\) was first found by \textit{D. Rödding} [Z. Math. Logik Grundlagen Math. 10, 315--330 (1964; Zbl 0199.02502)] and then by \textit{S. S. Marchenkov} [Mat. Zametki 27, 321--332 (1980); translation in Math. Notes 27, 161--166 (1980; Zbl 0483.03025)]. NEWLINENEWLINEThe author proves that there exist three new bases for \(\mathbf{E}\) containing very natural and simple functions. Particularly, one of the bases consists of addition, square, the remainder, and the base two exponential functions. Particularly, for every \(n>3\), \(\mathcal{E}^n\) is shown to be the closure of each of these bases augmented with an additional Ackermann-like function \(f_n\) due to \textit{R. W. Ritchie} [Pac. J. Math. 15, 1027--1044 (1965; Zbl 0133.24903)]. NEWLINENEWLINEThe obtained results enable the author to simplify the proof of \textit{H. Müller}'s theorem [Klassifizierungen der primitiv rekursiven Funktionen. Dissertation, Münster (1974)] stating that for every \(n\geq 2\), \(\mathcal{E}^{n+1}=\mathbf{K}_n\), where \(\mathbf{K}_n\) is P. Axt's hierarchy [\textit{P. Axt}, Z. Math. Logik Grundlagen Math. 11, 253--255 (1965; Zbl 0144.00201)].