On notions of computability-theoretic reduction between Π21 principles
On notions of computability-theoretic reduction between Π21 principles
复制标题
关于 Π21 原理之间的可计算性理论约简概念
DOI：
10.1142/s0219061316500021
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
C. Jockusch
中科院分区：
文献类型：
--
作者：
D. Hirschfeldt;C. Jockusch
研究了Π21原理之间关于可计算性理论可约性的几个概念。本文有助于分析拉姆齐定理和相关原理在这些概念下的各种版本的行为。在其他结果中，我们证明了对于每一个n≥3，都有一个∅(n−2)上的解都具有PA次的RT2n实例，并利用这一结果证明了Konig引理严格地位于RT22和RT23之间。我们还回答了Dorais，Dzhafarov，Hirst，Mileti和Shafer(2016)提出的关于比较Ramsey定理和瘦集合定理的版本的两个问题，这些定理具有相同的指数但不同的颜色数量。仍然关于颜色数对Ramsey理论性质的可计算方面的影响这一主题，我们证明了对于每个m≥2，存在ℕ的(m+1)-染色c，使得ℕ的每个m-染色有一个无限齐次集，它不计算c的任何无限齐次集，并将这一结果与Dzhafarov和Igusa(即将出现)引入的无限信息约简的概念联系起来。接下来，我们引入和研究一个新的概念，它提供了关于RCA0的ω模型的蕴涵思想的统一版本，以及相关概念，允许我们计算需要多少个原理P的应用才能将另一个原理归结为P。最后，我们填补了Cholak，Jockusch和Slaman(2001)中定理12.2的证明中的一个空白。
Several notions of computability-theoretic reducibility between Π21 principles have been studied. This paper contributes to the program of analyzing the behavior of versions of Ramsey’s Theorem and related principles under these notions. Among other results, we show that for each n ≥ 3, there is an instance of RT2n all of whose solutions have PA degree over ∅(n−2) , and use this to show that Konig’s Lemma lies strictly between RT22 and RT23 under one of these notions. We also answer two questions raised by Dorais, Dzhafarov, Hirst, Mileti, and Shafer (2016) on comparing versions of Ramsey’s Theorem and of the Thin Set Theorem with the same exponent but different numbers of colors. Still on the topic of the effect of the number of colors on the computable aspects of Ramsey-theoretic properties, we show that for each m ≥ 2, there is an (m + 1)-coloring c of ℕ such that every m-coloring of ℕ has an infinite homogeneous set that does not compute any infinite homogeneous set for c, and connect this result with the notion of infinite information reducibility introduced by Dzhafarov and Igusa (to appear). Next, we introduce and study a new notion that provides a uniform version of the idea of implication with respect to ω-models of RCA0, and related notions that allow us to count how many applications of a principle P are needed to reduce another principle to P. Finally, we fill in a gap in the proof of Theorem 12.2 in Cholak, Jockusch, and Slaman (2001).