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

      0 references
      0 references
      0 references
      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
      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

      Identifiers