کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4661749 | 1633461 | 2014 | 16 صفحه PDF | دانلود رایگان |
Let IΠ2− denote the fragment of Peano Arithmetic obtained by restricting the induction scheme to parameter free Π2Π2 formulas. Answering a question of R. Kaye, L. Beklemishev showed that the provably total computable functions of IΠ2− are, precisely, the primitive recursive ones. In this work we give a new proof of this fact through an analysis of certain local variants of induction principles closely related to IΠ2−. In this way, we obtain a more direct answer to Kaye's question, avoiding the metamathematical machinery (reflection principles, provability logic,...) needed for Beklemishev's original proof.Our methods are model-theoretic and allow for a general study of IΠn+1− for all n≥0n≥0. In particular, we derive a new conservation result for these theories, namely that IΠn+1− is Πn+2Πn+2-conservative over IΣnIΣn for each n≥1n≥1.
Journal: Annals of Pure and Applied Logic - Volume 165, Issue 9, September 2014, Pages 1429–1444