کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4662081 1633512 2010 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The strength of sharply bounded induction requires MSP
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
The strength of sharply bounded induction requires MSP
چکیده انگلیسی

We show that the arithmetical theory -IND∣x∣5, formalized in the language of Buss, i.e. with ⌊x/2⌋ but without the MSP function ⌊x/2y⌋, does not prove that every nontrivial divisor of a power of 2 is even. It follows that this theory proves neither NP=coNP nor .

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 161, Issue 4, January 2010, Pages 504-510