Thin Set Versions of Hindman's Theorem

by Denis R. Hirschfeldt and Sarah C. Reitzes



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