scientific article; zbMATH DE number 440477

From MaRDI portal
Publication:3140634





This paper investigates the provably total functions of fragments of first- and second-order bounded arithmetic. The (strongly) \(\Sigma_ i^ b\)-definable functions of \(S_ 3^{i-1}\) and \(R_ 3^ i\) are precisely the (strong) \(FP_ 3^{\Sigma^ p_{i-1}} [\text{wit},\log^{O(1)}]\) functions. The \(\Sigma_ i^{1,b}\)- definable functions of \(V_ 2^{i-1}\) and \(U_ 2^ I\) are the \(\text{EXPTIME}^{\Sigma^{1,p}_{i-1}} [\text{wit,poly}]\) functions, and the \(\Sigma_ i^{1,b}\)-definable functions of \(V_ 2^ i\) are the \(\text{EXPTIME}^{\Sigma_ i^{1,p}}\)-functions. The authors give witnessing theorems for these theories and prove conservation results for \(R_ 3^ i\) over \(S_ 3^{i-1}\) and for \(U_ 2^ i\) over \(V_ 2^{i-1}\). For the entire collection see [Zbl 0777.00008].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3140634)