On the induction schema for decidable predicates
Journal of Symbolic Logic 68 (1):17-34 (2003)
| Abstract | 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 | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,679 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesBarbara F. Csima (2004). Degree Spectra of Prime Models. Journal of Symbolic Logic 69 (2):430 - 442.
Savas Konur (forthcoming). An Event-Based Fragment of First-Order Logic Over Intervals. Journal of Logic, Language and Information.
Douglas Cenzer & Jeffrey B. Remmel (2006). Complexity, Decidability and Completeness. Journal of Symbolic Logic 71 (2):399 - 424.
Benjamin Wells (2002). Is There a Nonrecursive Decidable Equational Theory? Minds and Machines 12 (2):301-324.
C. J. Ash & R. G. Downey (1984). Decidable Subspaces and Recursively Enumerable Subspaces. Journal of Symbolic Logic 49 (4):1137-1145.
Peter Gärdenfors (1990). Induction, Conceptual Spaces and AI. Philosophy of Science 57 (1):78-95.
Wolfgang Burr (2000). Fragments of Heyting Arithmetic. Journal of Symbolic Logic 65 (3):1223-1240.
Douglas Cenzer & Andre Nies (2001). Initial Segments of the Lattice of Π01 Classes. Journal of Symbolic Logic 66 (4):1749 - 1765.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads2 ( #232,501 of 549,084 )Recent downloads (6 months)1 ( #63,317 of 549,084 )How can I increase my downloads? |
My notes
Discussion
