New Bounds on the Strength of Some Restrictions of Hindman's Theorem
New Bounds on the Strength of Some Restrictions of Hindman's Theorem
复制标题
Hindman 定理某些限制强度的新界限
DOI：
10.1007/978-3-319-58741-7_21
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
K. Zdanowski
中科院分区：
文献类型：
--
作者：
L. Carlucci;L. Kolodziejczyk;Francesco Lepore;K. Zdanowski
证明了Hindman有限和定理的各种自然约束的有效内容和逻辑强度的上界和下界。例如，我们证明了长度最多为2和4种颜色的和的Hindman定理包含$\mathsf{ACA}_0$。一个正在出现的{\em leitmotive}是，已知的欣德曼定理的下界及其对最多2个元素和的限制已经对许多限制版本有效，这些限制版本具有简单的证明和更好的可计算性和证明理论上界，而不是已知的完整版本的上界。我们强调解集中的稀疏性条件的作用，我们称之为分离性。
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.