Thin Set Versions of Hindman's Theorem
Status: to appear in the Notre Dame
Journal of Formal Logic
Availability:
preprint
Abstract. In this paper we examine the reverse mathematical
strength of a variation of Hindman's Theorem HT constructed by essentially
combining HT with the Thin Set Theorem TS to obtain a principle that we
call thin-HT. This principle states that every coloring c :
ℕ → ℕ has an infinite set
S⊆ℕ whose finite sums are thin for c, meaning
that there is an i with
c(s)≠i for all sums s of finitely
many distinct elements of S. We show
that there is a computable instance of
thin-HT such that every solution computes ∅′, as is the case with HT
(see
Blass, Hirst, and Simpson 1987). In analyzing this proof, we deduce that
thin-HT implies ACA0 over RCA0+IΣ02. On
the
other hand, using Rumyantsev
and Shen's computable version of the Lovász Local Lemma, we show
that
there is a computable instance of the restriction of thin-HT to sums of
exactly 2 elements such that any solution has diagonally noncomputable
degree relative to ∅′. Hence there is a computable instance of this
restriction of thin-HT with no Σ02 solution.
drh@math.uchicago.edu