No label defined (Q3140634)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 440477
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 440477 |
Statements
2 December 1993
0 references
fragments of bounded arithmetic
0 references
definable functions
0 references
provably total functions
0 references
witnessing theorems
0 references
conservation results
0 references
0.8156941533088684
0 references
0.8156941533088684
0 references
0.8149295449256897
0 references
0.7900931239128113
0 references
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].
0 references