Ricerc@Sapienza

Hirst investigated a natural restriction of Hindman’s Finite Sums Theorem—called Hilbert’s Theorem—and proved it equivalent over RCA0 to the Infinite Pigeonhole Principle for all colors. This gave the first example of a natural restriction of Hindman’s Theorem provably much weaker than Hindman’s Theorem itself. We here introduce another natural restriction of Hindman’s Theorem—which we name the Adjacent Hindman’s Theorem with apartness—and prove it to be provable from Ramsey’s Theorem for pairs and strictly stronger than Hirst’s Hilbert’s Theorem.

We present a natural restriction of Hindman’s Finite Sums Theorem that admits a simple combinatorial proof (one that does not also prove the full Finite Sums Theorem) and low computability-theoretic and proof-theoretic upper bounds, yet implies the existence of the Turing Jump, thus realizing the only known lower bound for the full Finite Sums Theorem. This is the first example of this kind. In fact we isolate a rich family of similar restrictions of Hindman’s Theorem with analogous properties

The relations between (restrictions of) Hindman’s Finite Sums Theorem and (variants of) Ramsey’s Theorem give rise to long-standing open problems in combinatorics, computability theory and proof theory. We present some results motivated by these open problems. In particular we investigate the restriction of the Finite Sums Theorem to sums of at most two elements, which is the subject of a long-standing open question by Hindman, Leader and Strauss.