zbMATH — the first resource for mathematics

Progressions of theories of bounded arithmetic. (English) Zbl 0881.03029
Sorbi, Andrea (ed.), Complexity, logic, and recursion theory. New York, NY: Marcel Dekker. Lect. Notes Pure Appl. Math. 187, 123-156 (1997).
The reflection principle, relative to a theory \(T\), for a class of arithmetical formulas \(\Gamma\), is the scheme \[ \{\forall x_1,\dots,\forall x_n[Pr_T(\ulcorner\varphi (I(x_1),\dots,\varphi I(x_n))\urcorner\rightarrow \varphi(x_1,\dots,x_n)]:\varphi\in \Gamma\} \] Where \(Pr_{T}\) is the provability predicate for \(T\). Arithmetization of the language is done over Buss’ system \(S^{1}_{2}\), in particular, \(I(x)\) is Buss’ efficient numeral of \(x\). It is shown that, for \(n>1\), \(S^{1}_{2}+\Sigma_{n+1}RP(S^{1}_{2})\) coincides with \(I\Sigma_n\), and that \(S^{1}_{2}+\Sigma_1RP(S^{1}_{2})\) coincides with \(I\Delta_0+ \text{Superexp}\). The rest of the paper is devoted to a detailed study of weak reflection principles and their progressions. The authors characterize the infinite unions of theories based on finite iterations of some weak reflection principles, i.e. principles for classes of formulas containing bounded formulas only. The final section of the paper is devoted to the development of a system of notations \({\mathcal O}^{P}\), for polynomial time ordinals, which is then used to obtain some results on polynomial time ordinal progressions based on weak reflection principles.
For the entire collection see [Zbl 0865.00036].

03F30 First-order arithmetic and fragments
03F15 Recursive ordinals and ordinal notations
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)