No label defined (Q3140637)
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 440480
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 440480 |
Statements
5 December 1993
0 references
provably recursive functions
0 references
speed-up
0 references
strong fragments of PA
0 references
weak fragments of PA
0 references
0.813573956489563
0 references
0.8126533031463623
0 references
0.7573853731155396
0 references
0.7365444302558899
0 references
0.7336673140525818
0 references
The authors investigate speed-up achieved by adding the rule \(\text{Prov}(\varphi)/\varphi\) and other admissible rules of similar kind to strong fragments of PA (\(\Sigma_ n\)-induction) and weak fragments of PA (extensions of \(\Delta_ 0\)-induction by axioms expressing that exponent or iteration of the exponent is total). In most cases the speed- up is possible up to functions provably recursive in the system. The reason is roughly that (i) \(\forall z\text{ Con}(\bar z)\) is provable in the theory itself (where \(\text{Con}(\bar z)\) means consistency for proofs of \(\leq z\) symbols); (ii) existence of values of a diagonal function \(d(\bar n)\) for fixed arguments \(n\) is provable using \(\leq p(n)\) symbols, where \(p\) is a polynomial. For the entire collection see [Zbl 0777.00008].
0 references