论文标题
如果无穷大可能很弱，拉姆齐的定理有多强？
How strong is Ramsey's theorem if infinity can be weak?
论文作者
论文摘要
我们研究了拉姆齐定理对$ n $ tuples的$ k $颜色的一阶后果，固定的$ n，k \ ge 2 $，比相对较弱的二阶算术理论$ \ mathrm {rca}^*_ 0 $。使用Chong-Mourad编码引理，我们表明，在$ \ Mathrm {rca}^*_ 0 + \ neg \ mathrm {i}σ^0_1 $，$ \ mathrm {rt}^n_k $与任何适当的相关性相同的情况下，均与univizative coptife coptife coptife coptife unive cutine cutine cutine cutine cutine cutige coptife，具有相同一阶宇宙的模型的扩展。 我们给出了$ \ mathrm {rca}^*_ 0 + \ mathrm {rt}^n_k $ for $ n \ ge 3 $的一阶后果。我们表明，它们形成了PA的非绝对可容易的子理论，其$π_3$片段为$ \ Mathrm {b}σ_1 + \ exp $ ans $π_ {\ ell + 3} $ fragment for $ \ ell \ ge 1 $在$ \ ell \ ge 1 $之间。 \ Mathrm {B}σ_{\ Ell+1} $和$ \ Mathrm {B}σ_{\ Ell+1} $。我们还考虑了$ \ mathrm {rca}^*_ 0 + \ mathrm {rt}^2_k $的一阶后果。我们表明，它们形成了$ \ mathrm {i}σ_2$的子理论，其$π_3$片段为$ \ mathrm {b}σ_1 + \ exp $，其$π_4$ fragment严格弱于$ \ mathrm {b}σ_2$，但不包含$ \ n.1 此外，我们考虑一个原理$δ^0_2 $ - $ \ MATHRM {rt}^2_2 $，定义为$ \ Mathrm {rt}^2_2 $，但均具有$ 2 $ -COLOURINGS和允许$δ^0_2 $ -Sets的解决方案。我们表明，$δ^0_2 $ - $ \ mathrm {rt}^2_2 $ over $ \ mathrm {rca} _0 + \ \ \ \ \ \ \ \ \}σ^0_2 $相似的行为与$ \ mathrm {rt}^2_2 $ \ m m iathrm mathrm {rca} $ \ MATHRM {RCA} _0 + \ MATHRM {B}σ^0_2 +δ^0_2 $ - $ \ MATHRM {rt}^2_2 $是$π_4$ - 但不是$π_5$ - converativate，而不是$π_5$ -Convertative to $ \ \ althrm {b}。但是，我们用来见证缺乏$π_5$ -Conservativity的语句在$ \ mathrm {rca} _0 +\ mathrm {rt}^2_2 $中无法证明。
We study the first-order consequences of Ramsey's Theorem for $k$-colourings of $n$-tuples, for fixed $n, k \ge 2$, over the relatively weak second-order arithmetic theory $\mathrm{RCA}^*_0$. Using the Chong-Mourad coding lemma, we show that in a model of $\mathrm{RCA}^*_0 + \neg \mathrm{I}Σ^0_1$, $\mathrm{RT}^n_k$ is equivalent to its own relativization to any proper $Σ^0_1$-definable cut, so its truth value remains unchanged in all extensions of the model with the same first-order universe. We give an axiomatization of the first-order consequences of $\mathrm{RCA}^*_0 + \mathrm{RT}^n_k$ for $n \ge 3$. We show that they form a non-finitely axiomatizable subtheory of PA whose $Π_3$ fragment is $\mathrm{B}Σ_1 + \exp$ and whose $Π_{\ell+3}$ fragment for $\ell \ge 1$ lies between $\mathrm{I}Σ_\ell \Rightarrow \mathrm{B}Σ_{\ell+1}$ and $\mathrm{B}Σ_{\ell+1}$. We also consider the first-order consequences of $\mathrm{RCA}^*_0 + \mathrm{RT}^2_k$. We show that they form a subtheory of $\mathrm{I}Σ_2$ whose $Π_3$ fragment is $\mathrm{B}Σ_1 + \exp$ and whose $Π_4$ fragment is strictly weaker than $\mathrm{B}Σ_2$ but not contained in $\mathrm{I}Σ_1$. Additionally, we consider a principle $Δ^0_2$-$\mathrm{RT}^2_2$, defined like $\mathrm{RT}^2_2$ but with both the $2$-colourings and the solutions allowed to be $Δ^0_2$-sets. We show that the behaviour of $Δ^0_2$-$\mathrm{RT}^2_2$ over $\mathrm{RCA}_0 + \mathrm{B}Σ^0_2$ is similar to that of $\mathrm{RT}^2_2$ over $\mathrm{RCA}^*_0$, and that $\mathrm{RCA}_0 + \mathrm{B}Σ^0_2 + Δ^0_2$-$\mathrm{RT}^2_2$ is $Π_4$- but not $Π_5$-conservative over $\mathrm{B}Σ_2$. However, the statement we use to witness lack of $Π_5$-conservativity is not provable in $\mathrm{RCA}_0 +\mathrm{RT}^2_2$.
