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

DOI10.1007/978-3-319-58741-7_21zbMATH Open1496.03242arXiv1701.06095OpenAlexW2963872185MaRDI QIDQ2011655FDOQ2011655

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

Publication date: 4 August 2017

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

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

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)