``Weak yet strong restrictions of Hindman's finite sums theorem

DOI10.1090/PROC/13856zbMATH Open1477.03174arXiv1610.07500OpenAlexW2543836030MaRDI QIDQ4596010FDOQ4596010

Authors: Lorenzo Carlucci 

Publication date: 8 December 2017

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

Abstract: 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.

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

Recommendations

• New bounds on the strength of some restrictions of Hindman’s Theorem
• New bounds on the strength of some restrictions of Hindman's theorem
• Effectiveness of Hindman’s Theorem for Bounded Sums
• A weak variant of Hindman's theorem stronger than Hilbert's theorem
• A simple proof and some difficult examples for Hindman's theorem

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Applications of computability and recursion theory (03D80) 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Primitive Recursive Bounds for Van Der Waerden Numbers
• On the strength of Ramsey's theorem for pairs
• Slicing the truth. On the computable and reverse mathematics of combinatorial principles
• Ramsey theory for discrete structures
• Ramsey's theorem and recursion theory
• Open questions in reverse mathematics
• The Existence of Certain Ultrafilters on N and a Conjecture of Graham and Rothschild
• Open Problems in Partition Regularity
• Hilbert versus Hindman
• Effectiveness of Hindman’s Theorem for Bounded Sums
• Title not available (Why is that?)
• Brown's lemma in second-order arithmetic

Cited In (11)

• The reverse mathematics of Hindman's theorem for sums of exactly two elements
• Restrictions of Hindman's theorem: an overview
• Effectiveness of Hindman’s Theorem for Bounded Sums
• Title not available (Why is that?)
• Note on finitary Hindman numbers
• A weak variant of Hindman's theorem stronger than Hilbert's theorem
• New bounds on the strength of some restrictions of Hindman's theorem
• Hindman's theorem for sums along the full binary tree, \(\Sigma^0_2\)-induction and the pigeonhole principle for trees
• A note on Hindman-type theorems for uncountable cardinals
• New bounds on the strength of some restrictions of Hindman’s Theorem
• New Hindman spaces

This page was built for publication: ``Weak yet strong restrictions of Hindman's finite sums theorem

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