Weaker cousins of Ramsey's theorem over a weak base theory
Weaker cousins of Ramsey's theorem over a weak base theory
复制标题
拉姆齐弱基理论的弱表亲
DOI：
10.1016/j.apal.2021.103028
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Katarzyna W. Kowalik
中科院分区：
文献类型：
--
作者：
Marta Fiori;L. Kolodziejczyk;Katarzyna W. Kowalik
本文致力于对拉姆齐对定理的一些众所周知的推论进行逆向数学研究，重点是链-反链原理 CAC、升序-降序原理 ADS 和对对的内聚拉姆齐定理 CRT 2 2。我们在基本理论 RCA 0⁎ 上研究这些原理，该理论比逆向数学中考虑的通常基本理论 RCA 0 弱，因为它只允许 Δ 1 0 感应与 Σ 1 0 感应相对。在 RCA 0⁎ 中，可能会发生 N 的无界子集与 N 不双射对应的情况。因此，拉姆齐理论原理至少分为两个变体：“正常”和“长”，具体取决于见证该原理的集合需要是无限的含义。我们证明了我们原理的正常版本，例如拉姆齐对和两种颜色的定理，等价于它们与适当的 Σ 1 0 可定义割的相对化。因此，它们在 RCA 0⁎ 上都是 Π 3 0 - 但不是 Π 1 1 - 保守的，并且，在 RCA 0⁎+‐ RCA 0 的任何模型中，如果它们为真，那么相对于某个集合，它们可计算为真。长版本表现出两种行为之一：它们要么暗示 RCA 0 优于 RCA 0⁎，要么是 Π 3 0-保守于 RCA 0⁎。保护结果是使用所谓的分组原理的变体获得的。我们还表明，内聚集合原理 COH（CRT 2 2 的加强）在 RCA 0⁎ 模型中永远无法计算为真，因此，不能从 RT 2 2 到 RCA 0⁎ 上遵循。
The paper is devoted to a reverse-mathematical study of some well-known consequences of Ramsey's theorem for pairs, focused on the chain-antichain principle CAC, the ascending-descending sequence principle ADS, and the Cohesive Ramsey Theorem for pairs CRT 2 2. We study these principles over the base theory RCA 0⁎, which is weaker than the usual base theory RCA 0 considered in reverse mathematics in that it allows only Δ 1 0-induction as opposed to Σ 1 0-induction. In RCA 0⁎, it may happen that an unbounded subset of N is not in bijective correspondence with N. Accordingly, Ramsey-theoretic principles split into at least two variants,“normal” and “long”, depending on the sense in which the set witnessing the principle is required to be infinite. We prove that the normal versions of our principles, like that of Ramsey's theorem for pairs and two colours, are equivalent to their relativizations to proper Σ 1 0-definable cuts. Because of this, they are all Π 3 0-but not Π 1 1-conservative over RCA 0⁎, and, in any model of RCA 0⁎+¬ RCA 0, if they are true then they are computably true relative to some set. The long versions exhibit one of two behaviours: they either imply RCA 0 over RCA 0⁎ or are Π 3 0-conservative over RCA 0⁎. The conservation results are obtained using a variant of the so-called grouping principle. We also show that the cohesive set principle COH, a strengthening of CRT 2 2, is never computably true in a model of RCA 0⁎ and, as a consequence, does not follow from RT 2 2 over RCA 0⁎.
登录
查看更多内容
如果无穷大可以很弱，那么拉姆齐定理有多强？
DOI：
10.1017/jsl.2022.46
发表时间：
2022
期刊：
The Journal of Symbolic Logic
影响因子：
--
作者：
KOLODZIEJCZYK LESZEK ALEKSANDER;KOWALIK KATARZYNA W.;YOKOYAMA KEITA
通讯作者：
YOKOYAMA KEITA
用于对着色的有序值拉姆齐数的一些上限
DOI：
10.1007/s00029-020-00577-3
发表时间：
2020
期刊：
Selecta Mathematica
影响因子：
--
作者：
Kolodziejczyk Leszek Aleksander;Yokoyama Keita
通讯作者：
Yokoyama Keita
拉姆齐对、集合和证明大小的定理
影响因子：
0.9
作者：
Kolodziejczyk Leszek Aleksander;Wong Tin Lok;Yokoyama Keita
通讯作者：
Yokoyama Keita
关于拉姆齐对定理
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
Keita Yokoyama;Sam Sanders;Takahiro Yamamoto;坂井哲;A. Shioura;Yu Kawakami;S. Kusuoka and S. Liang;Keita Yokoyama
通讯作者：
Keita Yokoyama