Induction, minimization and collection for \(\Delta_{n+1}(T)\)-formulas (Q701746): Difference between revisions

Let \(T\) be a consistent theory in the language of arithmetic. \(\text{I}\Delta_{n+1}(T)\) and \(\text{L}\Delta_{n+1}(T)\) are, respectively, the induction schema and the least number principle for the formulas which are \(\Delta_{n+1}\) provably in \(T\). \(\text{B}^*\Delta_{n+1}(T)\) is \(\text{I}\Delta_0\) plus the collection principle for those formulas \(\varphi\in \Pi_n\) for which \(\exists y\varphi\) is provably \(\Delta_{n+1}\) in \(T\). The main motivation for the results in this paper is the open problem whether \(\text{I}\Delta_1\) and \(\text{L}\Delta_1\) are equivalent. This is a substantial paper. In the first part, the authors establish a Kirby-Paris-style diagram for the hierarchy theories \(\text{I}\Delta_{n+1}(T)\), \(\text{L}\Delta_{n+1}(T)\), and \(\text{B}^*\Delta_{n+1}(T)\), where \(T=\text{I}\Sigma_n\). The rest of the paper is devoted to a characterization of the \(\Pi_{n+2}\) consequences of \(T\) in terms of \(\text{I}\Sigma_n\) and a set of nondecreasing \(\Pi_n\)-functions. The authors also discuss connections between their work and Beklemishev's study of induction and collection schemes as inference rules.