Thin Set Versions of Hindman’s Theorem

Notre Dame Journal of Formal Logic 63 (4):481-491 (2022)
  Copy   BIBTEX

Abstract

We examine the reverse mathematical strength of a variation of Hindman’s Theorem (HT) constructed by essentially combining HT with the Thin Set Theorem to obtain a principle that we call thin-HT. This principle states that every coloring c:N→N has an infinite set S⊆N whose finite sums are thin for c, meaning that there is an i with c(s)≠i for all nonempty 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, as shown by Blass, Hirst, and Simpson (1987). In analyzing this proof, we deduce that thin-HT implies ACA0 over RCA0+IΣ20. 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 Σ20 solution.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,642

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The Thin Set Theorem for Pairs Implies DNR.Brian Rice - 2015 - Notre Dame Journal of Formal Logic 56 (4):595-601.
A Simple Proof and Some Difficult Examples for Hindman's Theorem.Henry Towsner - 2012 - Notre Dame Journal of Formal Logic 53 (1):53-65.
Ramsey Algebras and Formal Orderly Terms.Wen Chean Teh - 2017 - Notre Dame Journal of Formal Logic 58 (1):115-125.
Regressive versions of Hindman’s theorem.Lorenzo Carlucci & Leonardo Mainardi - 2024 - Archive for Mathematical Logic 63 (3):447-472.
Ramsey algebras.Wen Chean Teh - 2016 - Journal of Mathematical Logic 16 (2):1650005.
Ramsey's Theorem and Cone Avoidance.Damir D. Dzhafarov & Carl G. Jockusch - 2009 - Journal of Symbolic Logic 74 (2):557-578.

Analytics

Added to PP
2023-01-05

Downloads
9 (#1,281,906)

6 months
5 (#710,311)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
Ramsey's theorem and recursion theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.
RT₂² does not imply WKL₀.Jiayi Liu - 2012 - Journal of Symbolic Logic 77 (2):609-620.
RT2 2 does not imply WKL0.Jiayi Liu - 2012 - Journal of Symbolic Logic 77 (2):609-620.

Add more references