scientific article; zbMATH DE number 440480

From MaRDI portal
Publication:3140637





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].











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 Q3140637)