scientific article; zbMATH DE number 1048040

From MaRDI portal
Publication:4348126





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











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