scientific article; zbMATH DE number 1048040
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].
- Structure and definability in general bounded arithmetic theories
- Bounded arithmetic and the polynomial hierarchy
- Separations of theories in weak bounded arithmetic
- Obituary: Franco Montagna (1948--2015)
- Iterated local reflection versus iterated consistency
- scientific article; zbMATH DE number 5778051 (Why is no real title available?)
- Division in the Theory S02+ of Bounded Arithmetic.
- A small reflection principle for bounded arithmetic
- Proof theoretic analysis by iterated reflection
- scientific article; zbMATH DE number 1431685 (Why is no real title available?)
- Construction of models of bounded arithmetic by restricted reduced powers
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)