Journal of Symbolic Logic 68 (1):17-34 (2003)
We study the fragment of Peano arithmetic formalizing the induction principle for the class of decidable predicates, $I\Delta_1$ . We show that $I\Delta_1$ is independent from the set of all true arithmetical $\Pi_2-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 $\Delta_1-induction$ . An open problem formulated by J. Paris is whether $I\Delta_1$ proves the corresponding least element principle for decidable predicates, $L\Delta_1$ (or, equivalently. the $\Sigma_1-collection$ principle $B\Sigma_1$ ). We reduce this question to a purely computation-theoretic one
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
References found in this work BETA
Induction Rules, Reflection Principles, and Provably Recursive Functions.Lev D. Beklemishev - 1997 - Annals of Pure and Applied Logic 85 (3):193-242.
A Proof-Theoretic Analysis of Collection.Lev D. Beklemishev - 1998 - Archive for Mathematical Logic 37 (5-6):275-296.
Citations of this work BETA
No citations found.
Similar books and articles
Degree Spectra of Prime Models.Barbara F. Csima - 2004 - Journal of Symbolic Logic 69 (2):430 - 442.
An Event-Based Fragment of First-Order Logic Over Intervals.Savas Konur - 2010 - Journal of Logic, Language and Information 20 (1):49-68.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Is There a Nonrecursive Decidable Equational Theory?Benjamin Wells - 2002 - Minds and Machines 12 (2):301-324.
Decidable Subspaces and Recursively Enumerable Subspaces.C. J. Ash & R. G. Downey - 1984 - Journal of Symbolic Logic 49 (4):1137-1145.
Added to index2009-01-28
Total downloads11 ( #389,156 of 2,143,567 )
Recent downloads (6 months)3 ( #227,097 of 2,143,567 )
How can I increase my downloads?
There are no threads in this forum
Nothing in this forum yet.