Logical Studies

Provability of Hindman-Schur and Hindman-Brauer in Peano Arithmetic

Document Type : Research

Author

amir khamseh

Assistant Professor, Faculty of Mathematical Sciences, Kharazmi University

https://doi.org/10.30465/lsj.2025.47895.1457
Abstract
Hindman’s Theorem states that for every coloring of natural numbers N with finitely many colors, there is an infinite set H such that the set of numbers which can be written as a sum of distinct elements of H is monochromatic. On the other hand, Brauer’s Theorem states that for all r,l,s≥1, there exists t=t(r,l,s) such that if the interval [1,t] is r-colored then there exists a,b>0 such that the set \{a,b,a+b,a+2b,…,a+(l-1)b\}⊆[1,t] is monochromatic. If A and B are sets, FS^A (B) is the set of all sums of j-many distinct elements of B, for all j∈A. Hindman-Brauer Theorem is the following statement: for every r-coloring of the set of natural numbers N, there is an infinite set H⊆N and a,b>0 such that FS^(\{a,b,a+b,a+2b,…,a+(l-1)b\}) is monochromatic. In this paper, we study the finite version of Hindman-Brauer Theorem and also Hindman-Schur Theorem and show that these results are provable in first order Peano Arithmetic. Also, we will see that these results are provable if we consider the apartness condition.

Keywords

Provability
Peano Arithmetic
Hindman Theorem
Brauer Theorem
Schur Theorem
Ramsey Theorem
Subjects
 
Cholak, Peter A &Jockusch, Carl G & Slaman, Theodore A (2001), “On the strength of Ramsey’s theorem for pairs”, The Journal of Symbolic Logic, vol. 66, No. 1, pp 1-55.
 
Carlucci, Lorenzo (2018), “Weak yet strong, restrictions of Hindman’s finite sum theorem”, Proceeding of the American Mathematical Society, vol 146, No. 2 pp 819-829.
 
Petr Hjek, Pavel Pudlk (1998), ‘’Metamathematics of first-order Arithmetic’’, Perspectives in Mathematical Logic, Springer-Verlag Berlin Heidelberg.
 
Kaye, Richard (1991). “Models of Peano Arithmetic”, Clarendon Press, Oxford, Oxford Logic Guides 15.
 
Simpson, Stephen (2009). ‘’Subsystems of second order Arithmetic’’, Cambridge University Press, New York, NY, Association for Symbolic Logic.
Logical Studies
Volume 15, Issue 2
March 2025
Pages 27-47

Home

Guide for Authors

Submit Manuscript

Reviewers

Contact Us