Corrigendum to: “On the strength of Ramsey's Theorem for pairs”
Corrigendum to: “On the strength of Ramsey's Theorem for pairs”
复制标题
勘误：“关于拉姆齐对定理的强度”
DOI：
10.2178/jsl/1254748700
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
C. Jockusch
中科院分区：
文献类型：
--
作者：
Peter A. Cholak;T. Slaman;C. Jockusch
[2]中给出的几个证明包含明显的错误或空白，尽管据我们所知，所有声称有可证明的结果。所需要的更正说明如下。除非另有说明，所有参考文献均为[2]，我们采用该论文的符号和术语。1。引理7。10断言原则D\和SRT^在RCAo上是等价的。然而，D\意味着SRT2的证明有一个隐藏的应用B£！J，因此实际上在RCA0 + BLĻ中执行。问题是，在每次添加一个元素来构建H时，每个添加到H中的元素c必须与之前选择的所有元素形成合适颜色的一对。要得到这样一个c的存在似乎需要BS^。这个差距最近被Chong， Lempp和Yang弥补了，他们在b[3]定理1.4中表明，在RCA0中，D^意味着BT%，因此Dl意味着SRT^。2. 引理7.1证明RT^等于SRT^ & COH / RCA0。然而，这里给出的RT2意味着RCAo中的COH的证据是有严重缺陷的。Joseph Mileti和后来的Jeffrey Hirst都指出了这一点。RT2在RCAo + IS2中隐含COH的证明可以很容易地从定理12.5的证明中提取出来。Mileti，同时还有Lempp和Jockusch观察到，当A的特征函数被限制为A^时，可以通过k有效地限定A的特征函数的变化数量来消除IS2的使用，因此证明这个数字是有限的只需要Si -归纳。因此，在RCAo中可以证明RT^蕴涵着COH，因此RT^等价于SRT^ & COH。3. Joseph Mileti指出了在第50页底部的断言证明中的一个漏洞，即对于每一个C齐次集合a和每一个可计算的着色C，存在一个无限的C齐次集合B，且Bf为0'，且设a是C的无限齐次集合d是a的度！，所以d»0'。设C是任意可计算的双着色对。我们必须证明C有一个跳次不超过d的无限齐次集。设C为d ' O = 07的阶，设a为a' = C的阶
Several proofs given in [2] contain significant errors or gaps, although to our knowledge all results claimed there are provable. The needed corrections are described below. All references are to [2] unless otherwise stated, and we adopt the notation and terminology ofthat paper. 1 . Lemma 7. 1 0 asserts that the principles D\ and SRT^ are equivalent over RCAo. However, the proof that D\ implies SRT2 has a hidden application of B£!J and thus is actually carried out in RCA0 + BLĻ The problem is that, in the construction of H by adding one element at a time, each element c added to H must form a pair of the appropriate color with all previously chosen elements. To get the existence of such a c one seems to need BS^. This gap was recently closed by Chong, Lempp, and Yang, who showed in [3], Theorem 1.4, that, in RCA0, D^ implies BT%, and hence Dl implies SRT^. 2. Lemma 7.1 1 asserts that RT^ is equivalent to SRT^ & COH over RCA0. However, the proof given there that RT2 implies COH in RCAo is seriously flawed. This was pointed out by Joseph Mileti and later by Jeffrey Hirst. A proof that RT2 implies COH in RCAo + IS2 can easily be extracted from the proof of Theorem 12.5. Mileti, and simultaneously Lempp and Jockusch, observed that it is possible to eliminate the use of IS2 by effectively bounding in terms ofk the number of changes in the characteristic function of A when it is restricted to A^, so that proving that this number is finite requires only Si -induction. Thus, it is provable in RCAo that RT^ implies COH, and hence that RT^ is equivalent to SRT^ & COH. 3. Joseph Mileti pointed out a gap in the proof of the claim at the bottom of page 50 that a certain computable 2-coloring of pairs C is "jump universal" in the sense that for every C -homogeneous set A and every computable coloring C, there exists an infinite C-homogeneous set B with Bf 0', and let A be an infinite homogeneous set for C. Let d be the degree of A! , so that d » 0' . Let C be any computable 2-coloring of pairs. We must show that C has an infinite homogeneous set with jump of degree at most d. Let c be a degree with d » O 07, and let a be a degree with a' = c. Since