TY - JOUR

T1 - The reverse mathematics of Hindman's Theorem for sums of exactly two elements

AU - Csima, Barbara F.

AU - Dzhafarov, Damir D.

AU - Hirschfeldt, Denis R.

AU - Jockusch, Carl G.

AU - Solomon, Reed

AU - Brown Westrick, Linda

N1 - Publisher Copyright:
© 2019 - IOS Press and the authors. All rights reserved.

PY - 2019

Y1 - 2019

N2 - Hindman's Theorem (HT) states that for every coloring of N with finitely many colors, there is an infinite set H ⊆ N such that all nonempty sums of distinct elements of H have the same color. The investigation of restricted versions of HT from the computability-theoretic and reverse-mathematical perspectives has been a productive line of research recently. In particular, HT k ≤ n is the restriction of HT to sums of at most n many elements, with at most k colors allowed, and HT k = n is the restriction of HT to sums of exactly n many elements and k colors. Even HT 2 ≤ 2 appears to be a strong principle, and may even imply HT itself over RCA0. In contrast, HT 2 = 2 is known to be strictly weaker than HT over RCA0, since HT 2 = 2 follows immediately from Ramsey's Theorem for 2-colorings of pairs. In fact, it was open for several years whether HT 2 = 2 is computably true. We show that HT 2 = 2 and similar results with addition replaced by subtraction and other operations are not provable in RCA0, or even WKL0. In fact, we show that there is a computable instance of HT 2 = 2 such that all solutions can compute a function that is diagonally noncomputable relative to θ′ . It follows that there is a computable instance of HT 2 = 2 with no Σ 2 0 solution, which is the best possible result with respect to the arithmetical hierarchy. Furthermore, a careful analysis of the proof of the result above about solutions DNC relative to θ′ shows that HT 2 = 2 implies RRT 2 2 , the Rainbow Ramsey Theorem for colorings of pairs for which there are most two pairs with each color, over RCA0. The most interesting aspect of our construction of computable colorings as above is the use of an effective version of the Lovász Local Lemma due to Rumyantsev and Shen.

AB - Hindman's Theorem (HT) states that for every coloring of N with finitely many colors, there is an infinite set H ⊆ N such that all nonempty sums of distinct elements of H have the same color. The investigation of restricted versions of HT from the computability-theoretic and reverse-mathematical perspectives has been a productive line of research recently. In particular, HT k ≤ n is the restriction of HT to sums of at most n many elements, with at most k colors allowed, and HT k = n is the restriction of HT to sums of exactly n many elements and k colors. Even HT 2 ≤ 2 appears to be a strong principle, and may even imply HT itself over RCA0. In contrast, HT 2 = 2 is known to be strictly weaker than HT over RCA0, since HT 2 = 2 follows immediately from Ramsey's Theorem for 2-colorings of pairs. In fact, it was open for several years whether HT 2 = 2 is computably true. We show that HT 2 = 2 and similar results with addition replaced by subtraction and other operations are not provable in RCA0, or even WKL0. In fact, we show that there is a computable instance of HT 2 = 2 such that all solutions can compute a function that is diagonally noncomputable relative to θ′ . It follows that there is a computable instance of HT 2 = 2 with no Σ 2 0 solution, which is the best possible result with respect to the arithmetical hierarchy. Furthermore, a careful analysis of the proof of the result above about solutions DNC relative to θ′ shows that HT 2 = 2 implies RRT 2 2 , the Rainbow Ramsey Theorem for colorings of pairs for which there are most two pairs with each color, over RCA0. The most interesting aspect of our construction of computable colorings as above is the use of an effective version of the Lovász Local Lemma due to Rumyantsev and Shen.

UR - http://www.scopus.com/inward/record.url?scp=85072586373&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85072586373&partnerID=8YFLogxK

U2 - 10.3233/COM-180094

DO - 10.3233/COM-180094

M3 - Article

AN - SCOPUS:85072586373

SN - 2211-3568

VL - 8

SP - 253

EP - 263

JO - Computability

JF - Computability

IS - 3-4

ER -