A Relation on $(\omega, <)$ of Intermediate Degree Spectrum on a Cone

基本信息

• 论文ID: 2412.01071
• 标题: A relation on (ω,<) of intermediate degree spectrum on a cone
• 作者: Jad Damaj and Matthew Harrison-Trainor
• 分类: math.LO (数理逻辑)
• 发表时间: November 7, 2025 (arXiv v2: November 5, 2025)
• 论文链接: https://arxiv.org/abs/2412.01071

摘要

本文研究自然数线性序 $(\omega,<)$ 上关系的度谱（degree spectra）问题。给定 $(\omega,<)$ 上的附加关系 $R$（如后继关系），$R$ 的度谱是指在 $(\omega,<)$ 的所有可计算副本中 $R$ 的图灵度集合。已知 $(\omega,<)$ 上关系的度谱分为四类：可计算度、所有c.e.度、所有$\Delta^0_2$度，或介于c.e.度和$\Delta^0_2$度之间的中间度谱。前三类的例子容易构造，但直到最近，是否存在"在锥上"具有中间度谱的关系仍是开放问题。Bazhenov等人构造了中间度谱的例子，但该例子是"非自然的"（通过对角化构造，依赖于哥德尔编码的选择）。本文使用"on-a-cone"范式限制研究"自然"关系，主要结果是构造了一个基于结构原因具有中间度谱的自然关系。

研究背景与动机

核心问题

本文研究可计算结构理论中的一个基本问题：关系的内在复杂性如何通过度谱来刻画。具体而言：

1. 度谱分类问题：Wright证明了 $(\omega,<)$ 上关系的度谱要么是单点集（可计算度），要么包含所有c.e.度，要么是所有$\Delta^0_2$度，要么介于c.e.度和$\Delta^0_2$度之间。前三类例子已知，但是否存在真正的中间度谱长期未解决。
2. 自然性问题：Bazhenov, Kalociński, and Wrocławski BKW22构造了中间度谱的例子，但该构造：
   • 依赖复杂的优先论证和对角化
   • 非规范（依赖哥德尔编码选择）
   • 不能相对化（相对于0'不保持中间性）
   • 在锥上度谱退化为c.e.度
3. "在锥上"范式：为捕捉"自然"关系的概念，采用Martin猜想相关的"on-a-cone"形式化：如果某性质在某个图灵度之上的所有度上都成立，则认为该性质"几乎处处"成立。这排除了依赖特殊编码的病态例子。

研究意义

• 理论意义：完整刻画 $(\omega,<)$ 上关系的度谱结构，回答可计算结构理论的基本问题
• 方法论意义：展示"on-a-cone"范式在排除非自然构造方面的有效性
• 技术贡献：发展了编码序列（coding sequence）的理论工具，可能适用于其他结构

核心贡献

1. 主要定理（Theorem 3.7）：构造了一个可计算的一元函数 $f$，其度谱在锥上严格介于c.e.度和$\Delta^0_2$度之间，且锥基为可计算度（即对所有预言机都成立）
2. 自然关系的显式描述：该函数 $f$ 有简单的结构描述——定义域分为循环块，奇数位置块按 $L_1L_2L_3\ldots$ 枚举自然数，偶数位置块按 $L_1L_1L_2L_1L_2L_3\ldots$ 枚举使每个数出现无穷次
3. 度谱刻画定理：
   • Theorem 3.3：块函数度谱包含非c.e.度当且仅当无穷多块嵌入到更后的块
   • Theorem 3.6：当所有块（除有限个）嵌入到后续块时，度谱为所有$\Delta^0_2$度当且仅当存在无穷编码序列
4. 多样性结果（Theorem 4.17）：对任意偶数序数 $\alpha \geq 6$，存在块函数度谱包含所有 $\beta$-c.e.度（$\beta < \alpha$）但不包含所有 $\alpha$-c.e.度，证明了不可数多个不同的度谱存在
5. 技术创新：引入编码序列（coding sequences）和编码树（coding trees）的概念，发展了最大/最小编码树的秩理论来精细刻画度谱

方法详解

任务定义

度谱（Degree Spectrum）：给定可计算结构 $\mathcal{A}$ 和关系 $R$，度谱定义为 $\text{DgSp}_\mathcal{A}(R) = \{\deg_T(\varphi(R)) : \mathcal{B} \text{ 是 } \mathcal{A} \text{ 的可计算副本}, \varphi: \mathcal{A} \cong \mathcal{B}\}$

在锥上的度谱：如果存在 $X$ 使得对所有 $Y \geq_T X$，某性质关于相对化度谱 $\text{DgSp}^Y_\mathcal{A}(R)$ 成立，则称该性质"在锥上"成立。

中间度谱问题：构造关系 $R$ 使得在锥上：

• 度谱严格包含所有c.e.度（存在非c.e.度）
• 度谱严格包含于$\Delta^0_2$度（存在不在度谱中的$\Delta^0_2$度）

核心概念：块函数与编码序列

块函数（Block Functions）

定义 2.6：函数 $f: (\omega,<) \to (\omega,<)$ 是块函数，如果对每个 $n$，存在区间 $[a,b]$ 包含 $n$ 且在 $f$ 和 $f^{-1}$ 下封闭。最小这样的区间称为 $f$-块。

关键性质：

• 块之间不重叠，定义域可分解为块的并
• 每个块有有限大小，可枚举所有块类型 $I_n$
• 对应字符串 $\alpha_f(i) = n$ 其中 $I_n$ 是第 $i$ 个块的类型

编码序列（Coding Sequences）

定义 3.4：区间序列 $[a_1,b_1], [a_2,b_2], \ldots$ 和映射 $\varphi_i: [a_i,b_i] \to [a_{i+1},b_{i+1}]$ 构成 $f$-编码序列如果：

1. 每个区间在块下封闭
2. $\varphi_i$ 是保序的非递减嵌入
3. $\varphi_{i+1} \circ \varphi_i$ 保持 $f$
4. $\varphi_1$ 不保持 $f$（存在 $x$ 使 $\varphi_1(f(x)) \neq f(\varphi_1(x))$）
5. $a_{i+1} > b_i$（区间严格递增）

直观理解：编码序列提供了在构造可计算副本时"编码"$\Delta^0_2$集合的机制：

• 当集合元素进入/离开时，通过在线性序中插入元素改变编码元组对应的区间
• 奇偶步的映射交替保持/不保持 $f$，对应集合元素的0/1状态
• 无穷编码序列允许元素值无限次改变（$\Delta^0_2$性质）

中间度谱构造

例子描述（Theorem 3.7的函数）

块序列为： $L_1, L_1, L_2, L_1, L_3, L_2, L_4, L_1, L_5, L_2, L_6, L_3, L_7, L_1, L_8, \ldots$

其中 $L_k$ 是长度为 $k$ 的循环。模式：

• 奇数位置：$L_1, L_2, L_3, L_4, \ldots$（递增枚举）
• 偶数位置：$L_1, L_1, L_2, L_1, L_2, L_3, \ldots$（每个数无穷次）

关键性质：

• 每个块无穷次出现 → 度谱包含非c.e.度（Theorem 3.3）
• 任意两块至多相邻一次 → 任何编码序列长度 $\leq 5$（链接会断裂）
• 无无穷编码序列 → 度谱不含所有$\Delta^0_2$度（Theorem 3.6）

包含非c.e.度的证明思路（Theorem 3.3）

充分性（无穷多块嵌入后续块）：

• 对任意元组 $c$，选择 $a$ 为大于 $c$ 的大小 $>1$ 的块
• 证明 $a$ 是 $c$ 上的差异自由（d-free）元组
• 给定量词自由公式 $\varphi(c,a,b)$，构造 $a' = a+1, b' = b+1$
  • $a'$ 不再是块，故 $f$ 在 $a'$ 上值改变
  • 对存在公式 $\psi(c,a',b')$，找到 $a'', b''$ 使 $f$ 在 $c,a'',b''$ 上值同 $c,a,b$
  • 利用块嵌入性质：$a''$ 是 $a$ 嵌入的目标块
• 由Theorem 3.2（来自HT18），度谱严格包含c.e.度

不含所有$\Delta^0_2$度的证明思路（Theorem 3.6B）

必要性（无无穷编码序列）：

• 构造$\Delta^0_2$集合 $C$ 使得对所有可计算副本 $L_e \cong (\omega,<)$： $\Phi_i^{f^{L_e}} \neq C \text{ 或 } \Psi_j^C \neq f^{L_e}$
• 需求 $R_{e,i,j}$ 策略：
  1. 选择未被约束的 $x$，初始 $C(x)=0$（Phase 0）
  2. 当计算 $\Phi_i^{f^{L_e}}(x)=C(x)$ 和 $\Psi_j^C[0,\ldots,m_0] = f^{L_e}[0,\ldots,m_0]$ 出现时，改变 $C(x)$（Phase 1）
  3. 交替改变 $C(x)$ 每次打破计算
• 关键论证：如果需求进入任意多个阶段，则构造出无穷（弱）编码序列
  • 阶段 $s_n$ 对应区间 $[a_n, b_n]$ 和映射 $\pi_{s_n}: L_e \to (\omega,<)$
  • 定义 $\varphi_i = \pi_{i+1} \circ \pi_i^{-1}$
  • 由计算性质，奇偶阶段 $\varphi_i$ 交替保持/不保持 $f$
• 由Lemma 3.5，弱编码序列可转化为强编码序列，矛盾

编码树理论（Section 4）

最大编码树（Maximal Coding Tree）

• 定义 4.8：节点为所有有限弱编码序列，扩展关系为序列延伸
• 秩：$\text{maxrank}(f) = \text{rank}(T_{\max}(f))$
• Theorem 4.9：若 $\alpha = \text{maxrank}(f)$，则在锥上存在非 $\alpha$-c.e.度不在度谱中
  • 证明：在对角化构造中维护秩函数 $r(x,s): \omega^2 \to \alpha+1$
  • 每次改变 $C(x)$ 对应延伸编码序列，秩严格下降
  • 由树良基性，$C$ 是 $\alpha$-c.e.集合

最小编码树（Minimal Coding Tree）

• 定义 4.11：节点为有限强编码序列，但秩定义更复杂
• 允许关系（permitting）：$\sigma$ 允许 $\tau$ 如果：
  • 最后区间 $[a_n,b_n]$ 和 $[a'_n,b'_n]$ 满足 $a_n < a'_n$
  • 存在保 $f$ 的映射 $\psi: [a_n,b_n] \to [a'_n,b'_n]$ 与 $\varphi_{n-1}, \varphi'_{n-1}$ 交换
• 秩定义：$\text{minrank}(\sigma) \geq \alpha$ 如果：
  • 存在无穷序列 $\sigma_0, \sigma_1, \ldots$ 每个允许下一个
  • 对所有 $\beta < \alpha$ 和所有 $i$，存在 $\tau_i$ 扩展 $\sigma_i$ 且 $\text{minrank}(\tau_i) \geq \beta$
• Theorem 4.12：若 $\alpha = \text{minrank}(f)$，则度谱包含所有 $\beta$-c.e.度（$\beta < \alpha$）
  • 证明：给定 $\beta$-c.e.集合 $X$（秩函数 $r: \omega^2 \to \beta$），构造 $L \cong (\omega,<)$ 使 $f^L \equiv_T X$
  • 为每个 $e$ 维护编码序列 $CS_{e,s}$ 满足 $\text{minrank}(CS_{e,s}) \geq r(e,s)$
  • $X(e)$ 改变时，延伸编码序列（秩下降）
  • $X(e)$ 不变但需调整时，横向移动到被允许的同秩序列

实验结果（定理验证）

主要结果

1. 中间度谱的存在性（Theorem 3.7）

函数：$f$ 的块序列 $L_1L_1L_2L_1L_3L_2L_4L_1\ldots$

验证：

• 包含非c.e.度：每个 $L_k$ 无穷次出现，满足Theorem 3.3条件
• 不含所有$\Delta^0_2$度：任何编码序列长度 $\leq 5$
  • 证明：任意编码序列在 $[a_1,b_1]$ 或 $[a_2,b_2]$ 有链接在 $[a_2,b_2]$ 或 $[a_3,b_3]$ 变为脆弱
  • 脆弱链接在 $[a_{i+2},b_{i+2}]$ 或 $[a_{i+3},b_{i+3}]$ 必断裂
  • 断裂链接无法继续延伸（奇偶性矛盾）

结论：这是第一个可计算的、自然的、可相对化的中间度谱例子

2. 度谱的多样性（Theorem 4.17）

构造：对偶数序数 $\alpha \geq 6$，基于秩为 $\alpha$ 的树 $T$ 构造函数 $f$

块类型：对 $\sigma = \langle a_0,\ldots,a_n \rangle \in T$，定义 $B_\sigma = x_0 + L_{2\ell(\sigma|_0)+2} + \cdots + L_{2\ell(\sigma|_n)+2} + x_1 + x_2 + x_3$ 其中"三明治元素" $x_0,x_1,x_2,x_3$ 的函数值依 $|\sigma|$ 奇偶性不同

块序列：

• 偶数位置：$L_1, L_3, L_5, \ldots$（奇数长度循环）
• 奇数位置：$B_{\sigma_1}, L_{j(1)}, B_{\sigma_2}, L_{j(2)}, \ldots$
  • $\sigma_1, \sigma_2, \ldots$ 递归枚举 $T$，每个无穷次
  • $j(i)$ 枚举奇数，每个无穷次，且 $j(i) \leq 2i+1$

验证：

• 最小秩 $\geq \alpha$：$T$ 嵌入到最小编码树（通过自然映射 $\sigma \mapsto [a_1,b_1],\ldots,[a_{|\sigma|},b_{|\sigma|}]$）
• 最大秩 $\leq \alpha$：
  • 脆弱链接的序列长度 $\leq 5 < \alpha$
  • 其他序列对应 $T^*$（$T$ 中元素对的树）的路径
  • 通过归纳证明 $\text{rank}^*(T^*) \leq \alpha$（关键：$\alpha$ 为偶数）

结论：存在不可数多个不同的度谱（对应不同的 $\alpha$）

具体例子分析（Example 4.15）

对Theorem 3.7的函数 $f$：

最大编码树秩：$\text{maxrank}(f) \leq 6$

• 任何长度5的编码序列有脆弱链接
• 脆弱链接在2步内断裂

最小编码树秩：$\text{minrank}(f) = 3$

• 下界：对 $\ell < m < n$，序列 $[a_1,b_1]$（类型$L_\ell$）→ $[a_2,b_2]$（类型$L_m$）→ $[a_3,b_3]$（$L_\ell$ 和 $L_n$ 的组合）显示秩 $\geq 3$
• 上界：任何有脆弱链接的序列秩为0（被允许的序列有断裂链接）

度谱结论：

• 包含所有2-c.e.度（由 $\text{minrank}=3$）
• 不含所有6-c.e.度（由 $\text{maxrank} \leq 6$）
• 通过特殊论证：不含所有3-c.e.度

相关工作

历史脉络

1. 早期工作：
   • Downey等DKMY09：一元关系度谱要么可计算要么所有$\Delta^0_2$度
   • KnollKno09：在 $\omega$ 和 $\zeta$ 上的研究
2. Wright的分类定理Wri18：
   • 度谱要么是单点集，要么包含所有c.e.度
   • 排除了介于可计算度和c.e.度之间的情况
   • 留下开放问题：是否存在介于c.e.度和$\Delta^0_2$度之间的度谱
3. BKW的突破BKW22：
   • 首次构造中间度谱的一元函数
   • 局限性：
     • 非规范（依赖哥德尔编码）
     • 不可相对化（在锥上退化为c.e.度）
     • 依赖计数函数的非可计算性
4. On-a-cone范式：
   • 起源于Martin猜想Mon19
   • MontalbánMon13：研究锥上的可计算结构理论
   • Harrison-TrainorHT18：首次系统研究锥上的度谱
   • Csima & Harrison-TrainorCHT17：锥上的范畴性度

本文相比相关工作的优势

技术贡献对比

• 本文的编码序列理论 vs BKW的计数函数方法：
  • 编码序列提供几何/组合直观
  • 编码树的秩理论精确刻画 $\alpha$-c.e.度
  • 允许系统化构造（Theorem 4.17）

结论与讨论

主要结论

1. 存在性：存在自然的（在锥上的）中间度谱关系
2. 多样性：存在不可数多个不同的中间度谱
3. 刻画定理：编码序列的存在性完全刻画度谱是否为所有$\Delta^0_2$度
4. 精细结构：最小/最大编码树的秩提供 $\alpha$-c.e.度包含的上下界

局限性

1. 最小/最大秩的间隙（Example 4.15）：
   • $\text{minrank}(f) = 3$ 但 $\text{maxrank}(f) = 6$
   • 度谱实际不含所有3-c.e.度（需特殊论证）
   • 间隙来自"允许"关系的复杂行为，非仅序列长度
2. 奇数序数情况（Question 4.18）：
   • Theorem 4.17仅证明偶数 $\alpha \geq 6$
   • 奇数情况的秩计算更复杂（归纳步骤失败）
3. 完整刻画的缺失（Question 4.21）：
   • 最小/最大秩仅给出上下界
   • 确切判定度谱是否包含所有 $\alpha$-c.e.度仍困难
4. 不可比度谱（Conjecture 4.16）：
   • 作者猜测存在不可比的度谱
   • 需要构造不同"允许行为"的函数

未来方向

1. 开放问题：
   • Question 4.19：包含非c.e.度是否必包含所有2-c.e.度？
   • Question 4.20：是否存在无穷降链？
   • Question 4.21：精确刻画 $\alpha$-c.e.度包含的条件
2. 推广方向：
   • 扩展到其他结构（不仅 $(\omega,<)$）
   • 研究更高元关系（非一元函数）
   • 连接到Martin猜想的其他方面
3. 技术改进：
   • 简化编码树秩的计算
   • 发展处理"允许"关系的一般理论
   • 构造具有特定度谱性质的系统方法

深度评价

优点

1. 理论深度：
   • 完全解决"在锥上"的中间度谱问题
   • 发展了编码序列/编码树的完整理论框架
   • 证明了不可数多样性（Theorem 4.17）
2. 技术创新：
   • 编码序列概念：优雅地捕捉$\Delta^0_2$编码的本质
   • 最小/最大编码树二分：区分"单元素编码"和"多元素独立编码"
   • 秩理论：精确连接到 $\alpha$-c.e.层次
3. 自然性：
   • 例子有显式描述（$L_1L_1L_2L_1L_3L_2\ldots$）
   • 所有参数可计算（$\alpha_f, c_f$等）
   • 可完全相对化（锥基为可计算度）
4. 系统性：
   • 充要条件（Theorems 3.3, 3.6）
   • 统一框架（适用所有块函数）
   • 可推广性（Theorem 4.17的构造方案）

不足

1. 技术复杂性：
   • 编码树秩的定义相当技术化（Definition 4.11）
   • 最小秩的归纳定义不直观
   • Theorem 4.17的证明需要精细的秩计算
2. 结果的不完整性：
   • 最小/最大秩间隙问题未解决
   • 仅处理偶数序数 $\alpha$
   • 度谱的完整分类仍缺失
3. 例子的限制：
   • 仅考虑块函数（特殊的一元函数）
   • 更高元关系的情况未探讨
   • 与其他结构的联系不明确
4. 表述问题：
   • 记号繁重（$\pi_s, \pi_{s+1}$等的区分）
   • 某些证明冗长（Theorem 4.17）
   • 缺少直观图示（虽有简单图）

影响力

1. 对领域的贡献：
   • 解决重要开放问题：Harrison-Trainor在HT18中提出的"在锥上"版本
   • 方法论贡献："on-a-cone"范式在排除病态例子的有效性
   • 理论工具：编码序列理论可能适用于其他$\Delta^0_2$-分类问题
2. 实用价值：
   • 主要是理论贡献，无直接应用
   • 但理解度谱对可计算模型论和逆数学有基础意义
3. 可复现性：
   • 构造完全显式，可验证
   • 证明细节充分（虽然技术性强）
   • 无需计算实验

适用场景

1. 理论研究：
   • 可计算结构理论
   • 度理论
   • $\alpha$-c.e.集合的性质研究
2. 潜在推广：
   • 其他可分类结构（如布尔代数、树等）
   • 更高阶的超算术层次
   • 逆数学中的编码问题
3. 教学价值：
   • 展示"自然性"概念的形式化
   • 优先论证与结构性质的结合
   • 度谱理论的高级例子

参考文献（关键引用）

1. BKW22 Bazhenov, Kalociński, Wrocławski: 首个中间度谱例子
2. HT18 Harrison-Trainor: 锥上度谱的系统研究，提出本文解决的问题
3. Wri18 Wright: 度谱的四分类定理
4. DKMY09 Downey et al.: 一元关系的度谱
5. Mar75 Martin: Borel确定性（Martin测度的基础）
6. AK00 Ash & Knight: 可计算结构理论的标准参考

总结评述

本文是可计算结构理论的重要进展，通过引入编码序列的精巧理论，彻底解决了 $(\omega,<)$ 上关系的"自然"中间度谱问题。与先前工作相比，本文的例子不仅存在，而且是可计算的、显式的、可相对化的，真正体现了"自然性"。

最大亮点是编码序列/编码树理论的发展，它不仅解决了存在性问题，还提供了系统化构造和分类工具（Theorem 4.17证明不可数多样性）。这一理论框架可能对其他结构的度谱研究产生深远影响。

主要挑战在于最小/最大编码树秩之间的间隙，以及"允许"关系带来的技术复杂性。作者正确指出，度谱的完整刻画需要理解这些复杂的组合行为，而非仅依赖编码序列的长度。

总体而言，这是一篇技术深刻、结果重要的论文，为可计算结构理论提供了新的工具和视角。