The Reverse Mathematics of Hindman's Theorem for Sums of
Exactly Two Elements
Status: published in Computability 8
(2019) 253 - 263
Availability: journal
version and preprint
Abstract. Hindman's Theorem (HT) states that for every coloring
of
ℕ
with finitely many colors, there is an infinite set H ⊆
ℕ 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≤nk is the restriction of HT to
sums of at most n
many elements, with at most k colors allowed, and HT=nk is the
restriction of HT to sums of exactly n many elements and k
colors. Even HT=22 appears to be a strong principle,
and may even imply HT itself over RCA0. In
contrast, HT=22 is known to be strictly weaker than HT over
RCA0, since HT=22 follows immediately from Ramsey's Theorem
for 2-colorings of pairs. In fact, it was open for several years
whether HT=22 is computably true.
We show that HT=22 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=22 such that all solutions can compute a function that is
diagonally noncomputable relative to ∅'. It follows that
there is a computable instance of HT=22 with no Σ02
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=22 implies RRT22,
the Rainbow Ramsey Theorem for colorings of pairs for which there are 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.
drh@math.uchicago.edu