Effectiveness of Hindman’s Theorem for Bounded Sums

DOI10.1007/978-3-319-50062-1_11MaRDI QIDQ2970955zbMATH OpenOpenAlexFDO

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)

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

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)

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$.

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

Cites work

• A short proof of Hindman's theorem
• A simple proof and some difficult examples for Hindman's theorem
• Finite sums from sequences within cells of a partition of N
• 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
• Probabilistic constructions of computable objects and a computable version of Lovász local lemma
• Ramsey's theorem and recursion theory
• Subsystems of second order arithmetic
• Ultrafilters: Some old and some new results

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
• A weak variant of Hindman's theorem stronger than Hilbert's theorem
• Note on finitary Hindman numbers
• 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)