Induction, minimization and collection for _n+1(T)-formulas
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.
- A proof-theoretic analysis of collection
- On axiom schemes for \(T\)-provably \(\Delta_1\) formulas
- Local induction and provably total computable functions
- A note on parameter free \(\Pi _{1}\)-induction and restricted exponentiation
- scientific article; zbMATH DE number 4035826 (Why is no real title available?)
- On the induction schema for decidable predicates
- Fragments of Arithmetic and true sentences
- Σ_{𝑛}-bounding and Δ_{𝑛}-induction
- A note on Δ1induction and Σ1collection
This page was built for publication: Induction, minimization and collection for \(\Delta_{n+1}(T)\)-formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q701746)
