Supplement to Proof Theory
F. Provably Computable Functions
One aim of proof theory is to find uniform scales against which one can measure the computational complexity of functions verifiably computable in “known” theories. Given a theory T, one is often interested in its provably computable functions, also know as its provably recursive functions.
Definition F.1 Let T be a theory whose language comprises that of PA. A function \(f:\bbN^k\to \bbN\) is \(\Sigma^0_i\)-definable in T if there is a \(\Sigma^0_i\)-formula \(A(x_1,\ldots,x_k,y)\) such that
-
\(T\vdash \forall x_1\ldots\forall x_k\,\exists! y\,A(x_1,\ldots,x_k,y)\), and
-
\(A(n_1,\ldots,n_k,m)\) holds if and only if \(f(n_1,\ldots,n_k)=m\) for all \(n_1,\ldots,n_k,m\in \bbN\).
The function f is provably computable in T if f is \(\Sigma_1^0\)-definable in T.
One of the oldest results of this sort is due to many people (at least Mints, Parsons, Takeuti).
Theorem F.2 The provably computable functions of \(\mathbf{I}\Sigma^0_1\) are the primitive recursive functions, where \(\mathbf{I}\Sigma^0_1\) is the fragment of PA with induction restricted to \(\Sigma^0_1\)-formulae.
A not too difficult proof is obtained via partial cut elimination followed by “reading-off” primitive recursive bounds for existential quantifiers in such proofs.[59]
For full PA there is Kreisel’s classification of the provably computable functions as the \(<\varepsilon_0\) recursive functions in Kreisel 1952. Here an ordinal representation system provides the uniform scale. Such a characterization can actually be extracted from the ordinal analysis of any theory. Indeed, it is a general fact that an ordinal analysis of a theory T yields, as a by-product, a characterization of the provably computable functions of T. An ordinal analysis of T via an ordinal representation system \(\langle A,\lhd,\ldots\rangle\) provides a reduction (also ensuring at least \(\Pi^0_2\)-conservativity) of T to
\[\tag{f1}\label{allgemein} \PA+\bigcup_{\alpha\in A} \rTI (\lhd_{\bar{\alpha}}) \]where \(\bigcup_{\alpha\in A} \rTI (\lhd_{\bar{\alpha}})\) denotes the schema of transfinite induction for all initial segments \(\lhd_{\bar{\alpha}}\) of the well-ordering \(\lhd\) (indexed externally). On the strength of the latter, it suffices to characterize the provably computable functions of theories of type \((\ref{allgemein})\).
Definition F.3 Let \(\alpha\in A\) such that \(0\lhd\alpha\). A number-theoretic function f is called \(\alpha\)-recursive if it can be generated by the usual schemes for generating primitive recursive functions plus the following scheme:
\[ f(m,\vec{n}) =\left\{\begin{array}{@{}ll} h(m,\vec{n},f(\theta(m,\vec{n}),\vec{n})) & \textrm{if } 0\lhd m\lhd\alpha\\ g(m,\vec{n}) & \textrm{otherwise,}\end{array}\right. \]where \(g,h,\theta\) are \(\alpha\)-recursive and \(\theta\) satisfies \(\theta(\beta,\vec{x})\lhd\beta\) whenever \(0\lhd\beta\lhd\alpha\).
Theorem F.4 The provably computable functions of \(\PA+\bigcup_{\alpha\in A} \rTI(A_{\bar{\alpha}},\lhd_{\bar{\alpha}})\) are exactly the functions which are \(\alpha\)-recursive for some \(\alpha\in A\).
The proof of Theorem F.4 poses, however, fascinating technical problems since the cut elimination usually takes place in infinitary calculi. A cut-free proof of a \(\Sigma^0_1\) statement can still be infinite and one needs a further “collapse” into the finite to be able to impose a numerical bound on the existential quantifier. One technical tool for achieving this characterization is to embed \(\PA+\bigcup_{\alpha\in A}\rTI(\lhd_{\bar{\alpha}})\) into a system of Peano arithmetic with the \(\omega\)-rule and a repetition rule, Rep, which simply repeats the premise as the conclusion. The addition of the Rep rule enables one to carry out a continuous cut elimination, due to Mints (1978), which is a continuous operation in the usual tree topology on proof trees. A further pivotal step consists in making the \(\omega\)-rule more constructive by assigning codes to proofs, where codes for applications of finitary rules contain codes for the proofs of the premises, and codes for applications of the \(\omega\)-rule contain Gödel numbers for partial functions enumerating codes of the premises. The aforementioned enumerating functions can be required to be partial recursive, making the proof trees recursive, or even primitive recursive in the presence of the rule Rep which enables one to stretch recursive trees into primitive recursive ones. A variant of the characterization of Theorem F.4[60] is given in Friedman & Sheard 1995, where the provably computable functions of \(\PA+\bigcup_{\alpha\in A}\rTI(\lhd_{\bar{\alpha}})\) are classified as the descent recursive functions over A. However, there is a more recent approach which has the great advantage over the previous one that one need not bother with codes for infinite derivations. In this approach one adds an extra feature to infinite derivations by which one can exert a greater control on derivations so as to be able to directly read off numerical bounds from cut free proofs of \(\Sigma_1^0\) statements. This has been carried out in Buchholz & Wainer 1987 for the special case of PA. In much greater generality and flexibility this approach has been developed by Weiermann (1996).
Ordinal analysis can also be used to extract information about other types of provable functions and higher type functionals, for example, hyperarithmetic functions, set recursive functions and ordinal recursive functions; cf. Rathjen 2006.