递归不可分集合对

$A$ 与 $B$ 分别提供两种互斥的有限证据。机器可以逐步看见某个数进入左边或右边，但对永远不进入任何一边的数没有规定。Separator 试图把这块未定区域一次性补成总的二值答案，同时不能错放两侧任何已知元素。递归不可分说，任何可计算补全都必在某处与左、右枚举发生冲突。

这比“两个集合都不可判定”更强。两个不相关的不可判定集合可能容易用奇偶性隔开；反过来，不可分证明必须针对任意候选判定器制造一个具体破坏点。自指正适合完成这件事：让程序查看 separator 对自己的分类，再输出迫使自身索引落到相反一边的值。

不可分性研究的是一对集合及其间隙，不能归结为其中某个immune 集公理库免疫集Immune set · Computably immune set · 免疫集合自身无限、却不含任何无限 c.e. 子集的自然数集合。的性质。标准不可分对的两侧本来就是 c.e.；若某侧无限，它自身就是无限 c.e. 子集，所以不可能是 immune。两类对象都排除某种有效选择，却分别量化 separator 与内部 c.e. 子集；共同使用对角化，并不使一个概念成为另一个概念的定义前提。

固定部分可计算函数编号 ${\phi }_e$，定义

两集合通过交错模拟可枚举，且因一个确定计算不可能同时输出 $0,1$ 而不交。假设可计算集合 $C$ 分隔它们。由 $C$ 的判定器有效生成代码变换 $f(e)$：若 $e\in C$，$f(e)$ 是恒输出 $1$ 的程序索引；若 $e\notin C$，则是恒输出 $0$ 的索引。Kleene 递归定理公理库Kleene 递归定理Kleene recursion theorem每个总可计算的程序代码变换都存在一个与其变换结果计算同一偏函数的程序索引。给出 $d$ 使 ${\phi }_d={\phi }_{f(d)}$。

若 $d\in C$，程序输出 $1$，于是 $d\in A_1$，但 separator 要求 $A_1\cap C=\varnothing$；若 $d\notin C$，程序输出 $0$，于是 $d\in A_0\subseteq C$。两种情况都矛盾，所以 $(A_0,A_1)$ 递归不可分。这一证明真正使用了两侧的输出语义，不是把停机问题的不可判定性原样改名。

若取任意不可计算 $D$ 与补集 $\bar{D}$，二者也没有可计算 separator，因为唯一可能的 $C$ 必须等于 $D$；但除非 $D$ 可判定，两侧不可能同时 c.e.。这个例子说明一般定义为何过宽，也说明 c.e. pair 假设带来额外内容。另一边界是 separator 只需夹在 $A$ 和 $\bar{B}$ 之间，不必恰等于其中一侧；证明某个自然候选不可计算，并没有排除所有别的 separator。

对合适的、一致且有效公理化的算术理论，可以把“理论证明 $\theta$”与“理论证明 $\mathrm{\neg }\theta$”的 Gödel 编码排成两个不交 c.e. 集；对角构造表明它们递归、甚至有效不可分。任何可计算 separator 都会给每个相关句子分派一个与理论证明保持一致的总判断，从而违背不可完备性机制。这种应用需要理论足以表示计算，不能仅凭一致性对任意弱系统宣布不可分。

递归不可分对也能产生不可判定理论与不可分的 ${\mathrm{\Pi }}_1^0$ 类，并可加强成有效不可分性。给定可计算 separator 的索引，可统一得到 $C$ 与 $\bar{C}$ 的 c.e. 索引，再由 $p$ 产出不可能位于两者之外的数，因而有效击败该候选。这个机制与 productive function 在形式上相似：二者都把有效候选变成漏项或冲突，但一个作用于成对的不交超集，另一个作用于单个集合的 c.e. 子集，定义不可互换。

归约证明中，不可分对常比单一完全集保留更多信息。把源对 $A_0,A_1$ 分别映到目标性质的“肯定区”和“否定区”，若目标存在可计算 separator，复合映射便会分隔源对。这个方法特别适合证明两种可枚举语义之间没有总、可靠的分类器。