کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4661665 | 1633448 | 2015 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Degrees bounding principles and universal instances in reverse mathematics
ترجمه فارسی عنوان
اصول محدود کننده درجه و نمونه های جهانی در ریاضیات معکوس
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
منطق ریاضی
چکیده انگلیسی
A Turing degree d bounds a principle P of reverse mathematics if every computable instance of P has a d-computable solution. P admits a universal instance if there exists a computable instance such that every solution bounds P. We prove that the stable version of the ascending descending sequence principle (SADS) as well as the stable version of the thin set theorem for pairs (STS(2)) does not admit a bound of low2 degree. Therefore no principle between Ramsey's theorem for pairs (RT22) and SADS or STS(2) admits a universal instance. We construct a low2 degree bounding the ErdÅs-Moser theorem (EM), thereby showing that the previous argument does not hold for EM. Finally, we prove that the only Î20 degree bounding a stable version of the rainbow Ramsey theorem for pairs (SRRT22) is 0â². Hence no principle between the stable Ramsey theorem for pairs (SRT22) and SRRT22 admits a universal instance. In particular the stable version of the ErdÅs-Moser theorem does not admit one. It remains unknown whether EM admits a universal instance.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 166, Issue 11, November 2015, Pages 1165-1185
Journal: Annals of Pure and Applied Logic - Volume 166, Issue 11, November 2015, Pages 1165-1185
نویسندگان
Ludovic Patey,