New bounds on the strength of some restrictions of Hindman's theorem

DOI10.1007/978-3-319-58741-7_21MaRDI QIDQ2011655zbMATH OpenOpenAlexFDO

Authors Lorenzo Carlucci, Leszek Aleksander Kołodziejczyk, Francesco Lepore, Konrad Zdanowski

Publication date 4 August 2017

Full work available at URL https://arxiv.org/abs/1701.06095

Mathematics Subject Classification ID

Ramsey theory (05D10) Second- and higher-order arithmetic and fragments (03F35)

Abstract: We prove upper and lower bounds on the effective content and logical strength for a variety of natural restrictions of Hindman's Finite Sums Theorem. For example, we show that Hindman's Theorem for sums of length at most 2 and 4 colors implies $mathsf{ACA}_0$. An emerging {em leitmotiv} is that the known lower bounds for Hindman's Theorem and for its restriction to sums of at most 2 elements are already valid for a number of restricted versions which have simple proofs and better computability- and proof-theoretic upper bounds than the known upper bound for the full version of the theorem. We highlight the role of a sparsity-like condition on the solution set, which we call apartness.

Recommendations

• New bounds on the strength of some restrictions of Hindman’s Theorem
• ``Weak yet strong restrictions of Hindman's finite sums theorem
• Effectiveness of Hindman’s Theorem for Bounded Sums
• A weak variant of Hindman's theorem stronger than Hilbert's theorem
• The reverse mathematics of Hindman's theorem for sums of exactly two elements

Cites work

• scientific article; zbMATH DE number 5003594 (Why is no real title available?)
• A weak variant of Hindman's theorem stronger than Hilbert's theorem
• Cohesive avoidance and strong reductions
• Effectiveness of Hindman’s Theorem for Bounded Sums
• Finite sums from sequences within cells of a partition of N
• Hilbert versus Hindman
• On the role of the collection principle for \(\Sigma ^0_2\)-formulas in second-order reverse mathematics
• On the strength of Ramsey's theorem for pairs
• Open Problems in Partition Regularity
• Open questions in reverse mathematics
• Slicing the truth. On the computable and reverse mathematics of combinatorial principles
• Subsystems of second order arithmetic
• The Existence of Certain Ultrafilters on N and a Conjecture of Graham and Rothschild
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• The polarized Ramsey's theorem
• The strength of Ramsey's theorem for coloring relatively large sets

Cited in

(8)

• ``Weak yet strong restrictions of Hindman's finite sums theorem
• New bounds on the strength of some restrictions of Hindman’s Theorem
• New bounds in Balog-Szemerédi-Gowers theorem
• scientific article; zbMATH DE number 5003594 (Why is no real title available?)
• Hindman's theorem for sums along the full binary tree, \(\Sigma^0_2\)-induction and the pigeonhole principle for trees
• Note on finitary Hindman numbers
• Effectiveness of Hindman’s Theorem for Bounded Sums
• A weak variant of Hindman's theorem stronger than Hilbert's theorem

This page was built for publication: New bounds on the strength of some restrictions of Hindman's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011655)