Effectiveness of Hindman's Theorem for Bounded Sums
Effectiveness of Hindman's Theorem for Bounded Sums
复制标题
Hindman 有界和定理的有效性
DOI：
10.1007/978-3-319-50062-1_11
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
L. Westrick
中科院分区：
文献类型：
--
作者：
D. Dzhafarov;C. Jockusch;Reed Solomon;L. Westrick
我们考虑限制形式的Hindman定理的强度和有效内容，其中色数是指定的，和的长度有一个指定的有限界。设$\mathsf{ht}^{\leq n}_k$表示对于$\mathbb{N}$的每个$k$-着色$c$，存在一个无限集合$X\subseteq\mathbb{N}$，使得$F\subseteq X$和$0<；|F|\leq n$在F}x$中的所有和$\sum_{x\具有相同的颜色。我们证明了存在$\mathbb{N}$的可计算$2$-着色$c$，使得不存在无限可计算集合$X$，使得$X$的至多$2$元素的所有非空和都具有相同的颜色。由此推论，$\mathsf{ht}^{\leq 2}_2$在$\mathsf{rca}_0$中是不可证明的，事实上我们证明了它蕴含$\mathsf{srt}^2_2$在$\mathsf{rca}_0$中。我们还证明了存在一个$\mathsf{ht}^{\leq 3}_3$的可计算实例，所有解的计算都是$0‘$。证明了：$\mathsf{ht}^{\leq3}_3$蕴含$\mathsf{aca}_0$.
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}^{\leq n}_k$ denote the assertion that for each $k$-coloring $c$ of $\mathbb{N}$ there is an infinite set $X \subseteq \mathbb{N}$ such that all sums $\sum_{x \in F} x$ for $F \subseteq X$ and $0 < |F| \leq n$ have the same color. We prove that there is a computable $2$-coloring $c$ of $\mathbb{N}$ 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}^{\leq 2}_2$ 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}^{\leq 3}_3$ with all solutions computing $0'$. The proof of this result shows that $\mathsf{HT}^{\leq 3}_3$ implies $\mathsf{ACA}_0$ in $\mathsf{RCA}_0$.