The reverse mathematics of Hindman’s Theorem for sums of exactly two elements

DOI10.3233/COM-180094zbMATH Open1448.03007arXiv1804.09809OpenAlexW2962887429MaRDI QIDQ5211065FDOQ5211065

Linda Brown Westrick, Damir D. Dzhafarov, Barbara Csima, Carl G. jun. Jockusch, Denis R. Hirschfeldt, Reed Solomon

Publication date: 17 January 2020

Published in: Computability (Search for Journal in Brave)

Abstract: Hindman's Theorem (HT) states that for every coloring of $mathbbN$ with finitely many colors, there is an infinite set $HsubseteqmathbbN$ 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$\underset{k}{\overset{leqslantn}{}}$ is the restriction of HT to sums of at most $n$ many elements, with at most $k$ colors allowed, and HT$\underset{k}{\overset{=n}{}}$ is the restriction of HT to sums of emph{exactly} $n$ many elements and $k$ colors. Even HT$\underset{2}{\overset{leqslant2}{}}$ appears to be a strong principle, and may even imply HT itself over RCA${}_0$. In contrast, HT$\underset{2}{\overset{=2}{}}$ is known to be strictly weaker than HT over RCA${}_0$, since HT$\underset{2}{\overset{=2}{}}$ follows immediately from Ramsey's Theorem for $2$-colorings of pairs. In fact, it was open for several years whether HT$\underset{2}{\overset{=2}{}}$ is computably true. We show that HT$\underset{2}{\overset{=2}{}}$ and similar results with addition replaced by subtraction and other operations are not provable in RCA${}_0$, or even WKL${}_0$. In fact, we show that there is a computable instance of HT$\underset{2}{\overset{=2}{}}$ such that all solutions can compute a function that is diagonally noncomputable relative to $emptyse{t}^{\prime }$. It follows that there is a computable instance of HT$\underset{2}{\overset{=2}{}}$ with no $Sigm{a}_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 $emptyse{t}^{\prime }$ shows that HT$\underset{2}{\overset{=2}{}}$ implies RRT$\underset{2}{\overset{=2}{}}$, the Rainbow Ramsey Theorem for $2$-colorings of pairs, over RCA${}_0$. The most interesting aspect of our construction of computable colorings as above is the use of an effective version of the Lov'asz Local Lemma due to Rumyantsev and Shen.

Full work available at URL: https://arxiv.org/abs/1804.09809

zbMATH Keywords

Hindman's theoremreverse mathematicsLovász local lemmaaddition-like functions

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Second- and higher-order arithmetic and fragments (03F35)

Cited In (5)

• Restrictions of Hindman's theorem: an overview
• A computable analysis of variable words theorems
• Hindman's theorem for sums along the full binary tree, \(\Sigma^0_2\)-induction and the pigeonhole principle for trees
• Thin set versions of Hindman's theorem
• Finiteness classes arising from Ramsey-theoretic statements in set theory without choice

This page was built for publication: The reverse mathematics of Hindman’s Theorem for sums of exactly two elements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211065)