Effectiveness of Hindman’s Theorem for Bounded Sums

DOI10.1007/978-3-319-50062-1_11zbMATH Open1480.03005arXiv1603.08249OpenAlexW2962772396MaRDI QIDQ2970955FDOQ2970955

Authors: Damir D. Dzhafarov, Carl G. jun. Jockusch, Reed Solomon, Linda Brown Westrick 

Publication date: 4 April 2017

Published in: Computability and Complexity (Search for Journal in Brave)

Abstract: We consider the strength and effective content of restricted versions of Hindman's Theorem in which the number of colors is specified and the length of the sums has a specified finite bound. Let $mathsf{HT}_k^{leqn}$ denote the assertion that for each $k$-coloring $c$ of $mathbbN$ there is an infinite set $XsubseteqmathbbN$ such that all sums $su{m}_{xinF}x$ for $FsubseteqX$ and $0<|F|leqn$ have the same color. We prove that there is a computable $2$-coloring $c$ of $mathbbN$ such that there is no infinite computable set $X$ such that all nonempty sums of at most $2$ elements of $X$ have the same color. It follows that $mathsf{HT}_2^{leq2}$ is not provable in $mathsf{RCA}_0$ and in fact we show that it implies $mathsf{SRT}_2^2$ in $mathsf{RCA}_0$. We also show that there is a computable instance of $mathsf{HT}_3^{leq3}$ with all solutions computing $0^{\prime }$. The proof of this result shows that $mathsf{HT}_3^{leq3}$ implies $mathsf{ACA}_0$ in $mathsf{RCA}_0$.

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

Recommendations

• ``Weak yet strong restrictions of Hindman's finite sums theorem
• Bounds of certain harmonic sums
• The Helly bound for singular sums
• A bounded consistency theorem for strong summabilities
• New bounds on the strength of some restrictions of Hindman's theorem
• New bounds on the strength of some restrictions of Hindman’s Theorem
• On the boundedness of Weyl sums
• scientific article; zbMATH DE number 4151012
• On sums of \(S\)-integers of bounded norm
• scientific article; zbMATH DE number 3953473

zbMATH Keywords

Hindman's theoremreverse mathematicsRamsey's theoremcomputable combinatorics

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
• Ultrafilters: Some old and some new results
• On the strength of Ramsey's theorem for pairs
• Ramsey's theorem and recursion theory
• A short proof of Hindman's theorem
• A simple proof and some difficult examples for Hindman's theorem
• On the role of the collection principle for \(\Sigma ^0_2\)-formulas in second-order reverse mathematics
• Open Problems in Partition Regularity
• Probabilistic constructions of computable objects and a computable version of Lovász local lemma

Cited In (10)

• The reverse mathematics of Hindman's theorem for sums of exactly two elements
• Restrictions of Hindman's theorem: an overview
• ``Weak yet strong restrictions of Hindman's finite sums theorem
• 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
• Hindman's theorem and choice
• Thin set versions of Hindman's theorem
• Finiteness classes arising from Ramsey-theoretic statements in set theory without choice

This page was built for publication: Effectiveness of Hindman’s Theorem for Bounded Sums

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