Open AccessΣ_{𝑛}-bounding and Δ_{𝑛}-induction
Author(s) -
Theodore A. Slaman
Publication year - 2004
Publication title -
proceedings of the american mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.968
H-Index - 84
eISSN - 1088-6826
pISSN - 0002-9939
DOI - 10.1090/s0002-9939-04-07294-6
Subject(s) - algorithm , artificial intelligence , computer science
Working in the base theory of P A − + I Σ 0 + exp \mathrm {PA}^- + \mathrm {I}\Sigma _0 +\exp , we show that for all n ∈ ω n\in \omega , the bounding principle for Σ n \Sigma _n -formulas ( B Σ n \mathrm {B}\Sigma _n ) is equivalent to the induction principle for Δ n \Delta _n -formulas ( I Δ n \mathrm {I}\Delta _n ). This partially answers a question of J. Paris.