差分递归可枚举度的下确界研究

### 差分递归可枚举度的下确界研究 #### 1. 引言 在可计算性理论中，递归可枚举（r.e.）度和差分递归可枚举（d.r.e.）度是重要的研究对象。对于任意集合 $A, B \subseteq \omega$，$A$ 和 $B$ 的图灵度的上确界总是存在的，且等于 $A \oplus B$ 的图灵度。然而，Kleene - Post 证明了 $A$ 和 $B$ 的图灵度的下确界可能不存在。后来，Lachlan 证明了存在这样的递归可枚举集 $A$ 和 $B$，并且指出对于任意递归可枚举集 $A$ 和 $B$，它们在递归可枚举度中的下确界（如果存在）与在 $\Delta_0^2$ 度中的下确界是相同的。 但对于差分递归可枚举度，情况并非如此。Kaddah 证明了存在差分递归可枚举度 $a, b, c$ 和 3 - 递归可枚举度 $x$，使得 $a$ 是 $b, c$ 在差分递归可枚举度中的下确界，但在 3 - 递归可枚举度中不是，因为 $a < x < b, c$。本文在此基础上进行了扩展，证明了这种下确界差异在递归可枚举度中是稠密存在的。 #### 2. 定理陈述 给定递归可枚举度 $u < v$，存在差分递归可枚举度 $a, b_1, b_2$ 和 3 - 递归可枚举度 $x$，满足 $u < a < x < b_1, b_2 < v$，并且 $b_1$ 和 $b_2$ 在差分递归可枚举度中的下确界是 $a$。 #### 3. 需求分析 为了证明上述定理，我们需要构造三个差分递归可枚举集 $A, B_1, B_2$，一个 3 - 递归可枚举集 $X$ 以及辅助函数 $\Gamma_1, \Gamma_2$ 和 $\Delta_j$，满足以下需求： - **G 需求**：$A, B_1, B_2, X \leq_T V$。 - **R 需求**：$X = \Gamma_1^{B_1,A,U} = \Gamma_2^{B_2,A,U}$。 - **$P_n$ 需求**：$X \neq \Phi_n^{A,U}$。 - **$N_n$ 需求**：若 $\Phi_{e}^{B_1,A,U} = \Phi_{e}^{B_2,A,U} = D_j$，则 $D_j = \Delta_j^{A,U}$，其中 $n = \langle e, j \rangle$，$\{D_j : j \in \omega\}$ 是所有递归可枚举集差集的标准列表。 ##### 3.1 G 和 R 策略 - **G 策略**：为了满足 $G$ 需求，我们采用延迟许可论证，这一方法最早由 Sacks 在其著名的密度定理中引入。 - **R 策略**：对于 $R$ 需求，我们使用常规的编码策略。具体规则如下： 1. 当 $\Gamma_i^{B_i,A,U}(x)$ 在阶段 $s$ 首次定义时，其使用 $\gamma_i(x)[s]$ 被选为一个新数。 2. 如果在 $\Gamma_i^{B_i,A,U}(x)$ 定义后，$x$ 在阶段 $t$ 进入或退出 $X$，则 $\Gamma_i^{B_i,A,U}(x)[t]$ 必须被未定义或恢复，以确保最终定义与 $X(x)$ 一致。在构造中，我们从 $B_i \cup A$ 中放入或取出一个小于或等于 $\gamma_i(x)[t]$ 的数。 3. 对于每个 $x$，存在一个阶段 $s_x$，使得在 $s_x$ 之后，$\Gamma_i^{B_i,A,U}(x)$ 永远不会被未定义。 4. $\gamma_i(x)$ 关于 $x$ 是递增的。 ##### 3.2 P 策略 满足 $P$ 需求的基本思想是标准的 Friedberg - Muchnik 论证。具体步骤如下： 1. 选择一个见证 $x$ 用于 $P$ 需求，并等待 $\Phi^{A,U}(x) \downarrow = 0$。 2. 当看到 $\Phi^{A,U}(x) \downarrow = 0$ 时，将 $x$ 放入 $X$ 并对 $A \upharpoonright \phi(x)$ 施加限制。 3. 由于在 $\Phi^{A,U}(x) \downarrow = 0$ 后，即使对 $A \upharpoonright \phi(x)$ 施加限制，$U \upharpoonright \phi(x)$ 的变化仍可能破坏 $\Phi^{A,U}(x)$ 的计算，我们通过 $\Psi$ 威胁 $V \leq_T U$ 来对 $U$ 施加“间接”限制。 设 $\alpha$ 是一个 $P$ 策略，它将运行循环 $j$（$j \in \omega$），从循环 0 开始。每个循环 $j$ 只能启动循环 $j + 1$，但可以停止任何 $j' > j$ 的循环。所有循环共同定义一个函数 $\Psi_{\alpha}$，循环 $j$ 负责定义 $\Psi_{\alpha}^U(j)$。具体运行步骤如下： 1. 选择 $x_j$ 作为一个新数。 2. 等待一个阶段 $s_0$，使得 $\Phi^{A,U}(x_j) \downarrow [s_0] = 0$。 3. 保护 $A \upharpoonright \phi(x_j)[s_0]$ 不受其他策略影响。 4. 设置 $\Psi_{\alpha}^U(j)[s_0] = V(j)[s_0]$，使用 $\psi_{\alpha}(j) = \phi(x_j)[s_0]$，并同时启动循环 $j + 1$。 5. 等待 $U \upharpoonright \phi(x_j)[s_0]$ 或 $V(j)$ 发生变化： - 如果 $U \upharpoonright \phi(x_j)[s_0]$ 先变化，则取消所有 $j' > j$ 的循环，并将循环 $j$ 的 $A$ 限制降至 0，返回步骤 2。 - 如果 $V(j)$ 先变化，则停止 $j' > j$ 的循环，进入步骤 6。 6. 将 $x_j$ 放入 $X$ 并等待 $U \upharpoonright \phi(x_j)[s_0]$ 发生变化。 7. 定义 $\Psi_{\alpha}^U(j) = V(j) = 1$，使用为 0，并启动循环 $j + 1$。 $\alpha$ 有两种可能的结果： - $(j, f)$：存在一个阶段 $s$，在此之后没有新的循环运行。这意味着某个循环 $j_0$ 在步骤 2 或 6 永远等待。如果在步骤 2 永远等待，则 $\Phi^{A,U}(x_{j_0}) \downarrow = 0$ 不成立；如果在步骤 6 永远等待，则 $\Phi^{A,U}(x_{j_0}) \downarrow = 0$ 且 $x_{j_0} \in X$。无论哪种情况，$x_{j_0}$ 都是 $P$ 需求的见证。 - $(j, \infty)$：某个循环 $j_0$ 无限次运行，但没有 $j' < j$ 的循环这样做。这意味着循环 $j_0$ 无限次从步骤 5 回到步骤 2，因此 $\Phi^{A,U}(x_{j_0})$ 发散，$x_{j_0}$ 是 $P$ 需求的见证。 当 $\alpha$ 在步骤 6 将 $x_j$ 放入 $X$ 时，如果 $\Gamma_i^{B_i,A,U}(x_j)$ 已定义，则必须使其未定义。为此，我们将其使用 $\gamma_i(x_j)$ 放入 $B_i$。但由于 $B_i \leq_T V$，我们需要 $V$ 的许可，这通过 $V(j)$ 的变化来实现。因此，步骤 6 可修改为： $(6')$ 将 $x_j$ 放入 $X$，将 $\gamma_i(x_j)$ 放入 $B_i$ 并等待 $U \upharpoonright \phi(x_j)[s_0]$ 发生变化。 以下是 $P$ 策略的流程图： ```mermaid graph TD; A[选择 x_j 作为新数] --> B[等待 Φ^{A,U}(x_j) ↓ [s_0] = 0]; B --> C[保护 A ⇾ ϕ(x_j)[s_0]]; C --> D[设置 Ψ_α^U(j)[s_0] = V(j)[s_0]，启动循环 j + 1]; D --> E{U ⇾ ϕ(x_j)[s_0] 或 V(j) 变化}; E -- U ⇾ ϕ(x_j)[s_0] 先变化 --> F[取消 j' > j 的循环，返回步骤 2]; E -- V(j) 先变化 --> G[停止 j' > j 的循环，进入步骤 6]; G --> H[将 x_j 放入 X，等待 U ⇾ ϕ(x_j)[s_0] 变化]; H --> I[定义 Ψ_α^U(j) = V(j) = 1，启动循环 j + 1]; ``` ##### 3.3 N 策略 设 $\beta$ 是一个 $N_e$ 策略，它致力于构造一个部分函数 $\Delta_{\beta}$，使得如果 $\Phi_{e}^{B_1,A,U} = \Phi_{e}^{B_2,A,U} = D_j$，则 $\Delta_{\beta}^{A,U}$ 是良定义的且能正确计算 $D_j$。 首先定义协议函数： - $l(\beta, s) = \max\{y < s : \Phi^{B_1,A,U} \upharpoonright y \downarrow [s] = \Phi^{B_2,A,U} \upharpoonright y \downarrow [s] = D_s \upharpoonright y\}$。 - $m(\beta, s) = \max\{0, l(\beta, t) : t < s \text{ 且 } t \text{ 是 } \beta \text{ - 阶段}\}$。 如果 $s = 0$ 或 $s$ 是 $\beta$ - 阶段且 $l(\beta, s) > m(\beta, s)$，则称阶段 $s$ 是 $\beta$ - 扩张阶段。 如果不涉及 $U$ 的变化和 $V$ 的许可，该需求的基本策略与 Kaddah 引入的策略相同：在定义 $\Delta^{A,U}(z)$ 后，允许 $P$ 策略同时破坏 $\Phi^{B_i,A,U}(z)$ 的计算，而不是像 Lachlan 的极小对构造那样保护其中一个。由于我们构造的 $B_i$ 是差分递归可枚举的，我们可以从其中一个集合中移除数字以恢复计算，并在某个参数 $z$ 处迫使 $D$ 和 $\Phi^{B_i,A,U}$ 产生分歧。具体步骤如下： 1. 在某个 $\beta$ - 扩张阶段 $s_0$，定义 $\Delta^{A,U}(z)[s_0] = D_{s_0}(z)$，其中 $\delta(z) = s_0$（假设 $D_{s_0}(z) = 0$，因为这是最复杂的情况）。 2. 在阶段 $s_1 > s_0$，某个优先级较低的 $P_e$ 策略将一个小数字 $x$ 放入 $X_{s_1}$，为了满足