On the induction schema for decidable predicates
Beklemishev, Lev D.
J. Symbolic Logic, Tome 68 (2003) no. 1, p. 17-34 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We study the fragment of Peano arithmetic formalizing the induction principle for the class of decidable predicates, $I\Delta1$. We show that $I\Delta1$ is independent from the set of all true arithmetical $\Pi2$-sentences. Moreover, we establish the connections between this theory and some classes of oracle computable functions with restrictions on the allowed number of queries. We also obtain some conservation and independence results for parameter free and inference rule forms of $\Delta1$-induction. ¶ An open problem formulated by J. Paris (see \cite{CloKra,HP}) is whether $I\Delta1$ proves the corresponding least element principle for decidable predicates, $L\Delta1$ (or, equivalently, the $\Sigma1$-collection principle $B\Sigma1$). We reduce this question to a purely computation-theoretic one.
Publié le : 2003-03-14
Classification:  
@article{1045861504,
     author = {Beklemishev, Lev D.},
     title = {On the induction schema for decidable predicates},
     journal = {J. Symbolic Logic},
     volume = {68},
     number = {1},
     year = {2003},
     pages = { 17-34},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1045861504}
}

Beklemishev, Lev D. On the induction schema for decidable predicates. J. Symbolic Logic, Tome 68 (2003) no. 1, pp.  17-34. http://gdmltest.u-ga.fr/item/1045861504/