Research article:

    Samuel R. Buss and Jan Krajicek and Gaisi Takeuti.
    "Provably total functions in the bounded arithmetic theories Ri3, Ui2, and Vi2."
    In Proof Theory, Arithmetic, and Complexity, P. Clote and J. Krajicek (eds), Oxford University Press, 1993, pp. 116-161.

Download conference article: postscript or PDF

    Abstract: This paper investigates the provably total functions of fragments of first- and second-order Bounded Arithmetic. The (strongly) $\Sigma^b_i$-definable functions of $S^{i-1}_3$ and $R^i_3$ are precisely the (strong) $\FPthreewp {i-1}$ functions. The $\Sigma^{1,b}_i$-definable functions of $V^{i-1}_2$ and $U^i_2$ are the $\EXwp {i-1}$ functions and the $\Sigma^{1,b}_i$-definable functions of $V^i_2$ are the $\EX i$-functions. We give witnessing theorems for these theories and prove conservation results for $R^i_3$ over $S^{i-1}_3$ and for $U^i_2$ over $V^{i-1}_2$.

Back to Sam Buss's publications page.