کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4661749 1633461 2014 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Local induction and provably total computable functions
ترجمه فارسی عنوان
القاء محلی و توابع قابل محاسبه کل قابل اعتماد
کلمات کلیدی
حساب مرتبه اول؛ نتایج حفاظت؛ القاء بدون پارامتر؛ توابع بازگشتی اولیه
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 165, Issue 9, September 2014, Pages 1429–1444
نویسندگان
, ,