Reductions of well-ordering principles to combinatorial theorems

التفاصيل البيبلوغرافية
العنوان: Reductions of well-ordering principles to combinatorial theorems
المؤلفون: Carlucci, Lorenzo, Mainardi, Leonardo, Zdanowski, Konrad
سنة النشر: 2024
المجموعة: Mathematics
مصطلحات موضوعية: Mathematics - Logic, Mathematics - Combinatorics
الوصف: A well-ordering principle is a principle of the form: If $X$ is well-ordered then $F(X)$ is well-ordered, where $F$ is some natural operator transforming linear orders into linear orders. Many important subsystems of Second-order Arithmetic of interest in Reverse Mathematics are known to be equivalent to well-ordering principles. We give a unified treatment for proving lower bounds on the logical strength of various Ramsey-theoretic principles relations using characterizations of the corresponding formal systems in terms of well-ordering principles. Our implications (over $RCA_0$) from combinatorial theorems to $ACA_0$ and $ACA_0^+$ also establish uniform computable reductions of the corresponding well-ordering principles to the corresponding Ramsey-type theorems.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/2401.04451
رقم الأكسشن: edsarx.2401.04451
قاعدة البيانات: arXiv