论文标题
Hindman定理的薄套装版本
Thin Set Versions of Hindman's Theorem
论文作者
论文摘要
在本文中，我们研究了Hindman定理HT的变化的相反数学强度，该变化是通过将HT与薄的定理TS结合在一起而构建的，以获得我们称为Thin-HT的原理。 Thin-ht说，每种颜色$ c：\ mathbb {n} \ to \ mathbb {n} $都有一个无限的套装$ s \ subseteq \ subseteq \ mathbb {n} $，其有限的款项对$ c $很薄，这意味着$ c（s）\ neq iq i $ $ s $ s $ s $ s in s s s s s in s $ c（s）。我们表明，有一个可计算的实例，使每个解决方案都像HT一样计算$ \ emptyset' $（参见Blass，Hirst和Simpson 1987）。在分析此证明时，我们推断出薄ht意味着$ aca_0 $ over $ rca_0 +iς^0_2 $。另一方面，使用RumyantSev和Shen的Lovász本地引理的可计算版本，我们表明存在一个可计算的实例，即限制了薄ht对完全2个元素的总和，以使任何解决方案相对于$ \ emptyset' $具有对角度不可误的程度。因此，没有$σ^0_2 $解决方案的薄ht限制的可计算实例。
In this paper we examine the reverse mathematical strength of a variation of Hindman's Theorem HT constructed by essentially combining HT with the Thin Set Theorem TS to obtain a principle which we call thin-HT. thin-HT says that every coloring $c: \mathbb{N} \to \mathbb{N}$ has an infinite set $S \subseteq \mathbb{N}$ whose finite sums are thin for $c$, meaning that there is an $i$ with $c(s) \neq i$ for all $s \in S$. We show that there is a computable instance of thin-HT such that every solution computes $\emptyset'$, as is the case with HT (see Blass, Hirst, and Simpson 1987). In analyzing this proof, we deduce that thin-HT implies $ACA_0$ over $RCA_0 + IΣ^0_2$. On the other hand, using Rumyantsev and Shen's computable version of the Lovász Local Lemma, we show that there is a computable instance of the restriction of thin-HT to sums of exactly 2 elements such that any solution has diagonally noncomputable degree relative to $\emptyset'$. Hence there is a computable instance of this restriction of thin-HT with no $Σ^0_2$ solution.
