×

Functions provably total in \(I^ -S_ n\). (English) Zbl 0703.03018

Summary: The main theorem of the paper can be formulated as follows. Let \(n\geq 2\). If, in the proof of the totality of a recursive function f: \(N\to N\) we use only m different axioms of \(\Sigma\) \({}_ n\)-induction without parameters and additionally only axioms of \(PA^-\), then f can be bounded (almost everywhere) by a function \(H_{\beta}\) in Hardy’s hierarchy, where \(\beta =\omega_{n-1}^{\omega^ m\cdot k}\) for some \(k\in \omega\).

MSC:

03D20 Recursive functions and relations, subrecursive hierarchies
PDFBibTeX XMLCite
Full Text: DOI EuDML