Hindman's theorem does not code $\emptyset^{(\omega)}$ in one application

技术摘要：“希德曼定理（Hindman's theorem）在单次应用中并不编码 $\emptyset^{(\omega)}$”

问题陈述
本文探讨了希德曼定理（HT）在计算论层面的复杂度，特别是其解相对于输入着色的强度。希德曼定理指出：对于自然数 $\mathbb{N}$ 的任何有限着色，都存在一个无限集 $H$，使得 $H$ 的所有非空有限和的集合（记作 $FS(H)$）是单色的。

先前的研究确立了以下界限：

1. 上界： Blass, Hirst, 和 Simpson (1987) 证明，对于每一个可计算着色，都存在一个可以从 $\emptyset^{(\omega)}$（空集的 $\omega$-跳跃）计算出的解。
2. 下界： 同上述作者证明，存在某种可计算着色，使得每一个解都计算出停机集 $\emptyset'$。随后，Liao (2026) 对此进行了改进，证明对于某些可计算着色，不存在 $\Pi^0_3$ 解。

本文旨在解决的核心开放性问题是：对于希德曼定理的一次单次应用，$\emptyset^{(\omega)}$ 这个上界是否是最优的？具体而言，是否每一个算术级的希德曼定理实例都允许存在一个不计算 $\emptyset^{(\omega)}$ 的解？

方法论
作者采用了改编自 Towsner 关于希德曼定理组合证明的迫近技术（forcing technique）。该方法论包含以下组成部分：

1. 重构： 问题被转化为有限并集定理（FUT）的语言，FUT 与 HT 是计算等价的。这涉及对非空有限子集集 $P_{fin}(\mathbb{N})$ 进行着色，并寻求一个无限块序列 $H$，使得有限并集集合 $FU(H)$ 是单色的。
2. Towsner 树与匹配： 作者利用了 Towsner 关于“半匹配”（half-match）和“全匹配”（full-match）的概念。若对于每一个有限集 $F$，对于每一个无限块序列 $X$，对于每一个有限并 $b \in FU(X)$，都存在一个 $a \in F$ 使得 $f(a \cup b) = f(b)$，则称 $F$ “半匹配” $X$。而“全匹配”则要求 $f(a) = f(a \cup b) = f(b)$。
   • 他们构造了一个“Towsner 序列”，即一个诱导树状结构的嵌套半匹配序列（称为 Towsner 树）。
   • 他们确立了对于一个算术级着色 $f$，存在一个 $f''$-可计算的 Towsner 序列。
3. 迫近概念： 定义了一种新的迫近概念，使用“P-条件”，即由有限个块序列 $I$ 和一个无限资源库 $X$ 组成的对 $(I, X)$。一个条件被称为“$f$-匹配”的，如果它满足与着色相关的特定扩展性质。
4. 第一跳控制： 核心创新在于设计了一个具有特定可定义属性的“迫近问题”（forcing question）。这使得构造一个泛型滤子（generic filter）成为可能，从而使生成的解 $G$ 能够避开某个特定的非算术集 $C$。该迫近关系旨在控制解的第一跳，确保解保持在相对于输入的特定算术度之内，同时避开目标锥（target cone）。
5. 对角线论证： 为了确保 $C \not\leq_T G$，作者通过满足要求 $R^C_e: W^G_e \neq C$ 来进行论证。通过分析针对 $\Sigma^0_1$ 公式设计的迫近问题，他们证明了对于任何非算术集 $C$ 和算术级着色，都可以通过扩展条件来迫使 $G$ 在某个元素上与 $C$ 不同。

主要贡献与结果

1. 主定理（锥回避）： 主要结果（主定理 1.5）指出：设 $C$ 为一个非算术度的集合。对于每一个 $\ell \geq 1$ 以及每一个算术度的着色 $f: \mathbb{N} \to \ell$（或 $P_{fin}(\mathbb{N}) \to \ell$），都存在一个无限集 $H$，使得 $FS(H)$是$f$-单色的，且$C \not\leq_T H$。

   • 推论： 通过令 $C = \emptyset^{(\omega)}$，作者证明了每一个算术级的希德曼定理实例都允许存在一个不计算 $\emptyset^{(\omega)}$ 的解。这表明希德曼定理在单次应用中的计算论上界并非最优。

2. 迭代的局限性： 作者澄清，这一结果并不意味着希德曼定理在反向数学中弱于 $\text{ACA}^+_0$。锥回避是针对图灵可约性（$C \not\leq_T H$）成立的，但在算术可约性方面未必成立。因此，该定理不能通过迭代来构建一个排除 $\emptyset^{(\omega)}$ 的希德曼定理 $\omega$-模型。

3. 简单着色： 本文研究了对“简单着色”（即颜色的性质仅取决于组成部分及其相对位置的着色）的希德曼定理限制。

   • 他们证明，有限并集定理在简单着色上的限制在 $\text{RCA}_0$ 上等价于 $\text{ACA}_0$。
   • 他们指出，Blass, Hirst, 和 Simpson 用于证明下界的那个基于“极短间隙”（very short gaps）的特定着色，就是一个简单着色。

4. Towsner 树的复杂度： 作者证明（命题 2.24），对于 Blass, Hirst, 和 Simpson 所构造的特定着色，每一个 Towsner 序列都计算出 $\emptyset'$。这表明，虽然 Towsner 树是强大的工具，但它们对于某些可计算着色的存在本身就蕴含了显著的计算能力，尽管这并不排除存在其他证明或不依赖于此类树的全匹配的存在。

意义
本文解决了关于 $\emptyset^{(\omega)}$ 上界对于希德曼定理单次应用是否紧致的问题。通过证明可以回避非算术锥，作者展示了希德曼定理在处理算术输入时，本质上并不需要 $\omega$-跳的全部强度。这精炼了对该定理计算内容的理解，区分了寻找“一个”解所需的复杂度与寻找“一个能计算特定高阶集合的”解所需的复杂度。这项工作也将组合证明（Towsner 的证明）与迫近技术相结合，以实现对解的图灵度（Turing degrees）的精确控制。