Myhill 同构定理 | Codeboy's Blog

形式陈述

一一归约 $A\le_1B$ 是many-one 归约的加强：见证 $f:\mathbb N\to\mathbb N$ 还须单射，并满足

x\in A\iff f(x)\in B.

集合 $A,B$ 称递归同构或 computably isomorphic，若存在总可计算双射 $h:\mathbb N\to\mathbb N$ ，使

x\in A\iff h(x)\in B.

自然数上的总可计算双射其逆可由搜索唯一原像计算，故 $h$ 也是可计算置换。Myhill 同构定理断言

A\cong_{\mathrm{rec}}B \quad\Longleftrightarrow\quad A\le_1B\ \text{且}\ B\le_1A.

正向取 $h,h^{-1}$ 即得两条一一归约；逆向是定理的有效 Cantor–Bernstein 内容。一个重要推论是任意两个creative 集递归同构，因为 creative 集都对 c.e. 集一一完备。

直觉

普通 Cantor–Bernstein 从两边的单射得到双射，但经典证明会按双向图的整条无限分量决定配对方向；“这个分量向后是否有起点”未必可判定。Myhill 的结论要求更强：不只证明某个双射集合论上存在，还要逐输入有效算出配偶。

双向一一归约形成一张二部图。左边自然数经 $f$ 指向右边，右边经 $g$ 指回左边；单射保证每点至多有一个前驱，归约保证同一连通链上左点属于 $A$ 当且仅当相邻右点属于 $B$ 。与其先判断整条链的类型，不如有限阶段 back-and-forth：每次取最小未配对点，沿可计算的正向链寻找第一个未配对对侧点。当前只配了有限多点，所以搜索必会结束。

这种构造保留的不只是基数。每个候选配对都沿 $f$ 、 $g$ 的奇数长度复合取得，因此自动保持成员颜色；左右轮流处理最小未配对点，又分别保证最终定义域全、值域满。有效性来自阶段操作只做有限搜索，而不是预知无限分量。

例子与边界

设 $f:A\le_1B$ 、 $g:B\le_1A$ 。构造有限匹配 $M_s$ 。偶数阶段取最小尚未配对的左点 $x$ ，依次考察

f(x),\quad f(g(f(x))),\quad f(g(f(g(f(x))))),\ldots

直到遇到未配对右点 $y$ ，加入 $(x,y)$ 。奇数阶段对最小未配对右点对称地沿 $g,f$ 链找未配对左点。若搜索落入有限环而所有对侧点已配完，环内同样多的本侧点也已配完，与起点未配对矛盾；若链无限，有限的 $M_s$ 也不可能占满它。因此每阶段终止。要计算 $h(x)$ ，模拟构造直到左点 $x$ 被配；要计算 $h^{-1}(y)$ ，模拟到右点 $y$ 被配。最小点策略保证二者都最终发生。

沿链每走一步都保持“左属 $A$ iff 右属 $B$ ”，所以所得 $h$ 是所需置换。这个 stage trace 也说明为什么单射重要：若两条链可合并，沿前向寻找未配对点可能无法维持一一匹配。

互相 many-one 可归约不够。取可计算集合 $A=\{0\}$ 与 $B=\{0,1\}$ ；二者都非空且补集非空，可通过把成员送到目标中的固定成员、把非成员送到固定非成员而双向 many-one 归约。但任何置换都保持集合基数，不可能把单元素集送到双元素集。这里的归约恰因允许折叠多个输入而丢失了同构所需的信息。

本定理也不是Myhill–Nerode 定理。后者用右同余有限指数刻画正则语言并导出最小 DFA；本页研究自然数集合的一一归约与可计算置换。两者除共同的人名外没有定理上的蕴含关系，证明工具和研究对象也完全不同。

推论与应用

对 creative 集，定理说明“通用 c.e. 问题”在可接受编号下具有统一形状。给定 creative $C$ ，存在可计算置换把标准对角停机集 $K$ 送到 $C$ ；置换同时搬运正实例和负实例，不需额外 oracle。由此，许多关于 creative 集且在可计算置换下不变的性质只需在 $K$ 上证明一次。

定理还给可计算结构中的 Schröder–Bernstein 现象划出准确边界：两条可计算嵌入一般未必由经典分量选择法直接给出可计算同构，而本页额外拥有“嵌入同时保持一个二色谓词”的一一归约结构，back-and-forth 才能有效完成。迁移到其他结构时，必须检查相应有限搜索是否仍保持全部关系，而非只看底层集合有两条注入。

在复杂度理论中，Berman–Hartmanis 猜想把这种图景类比到多项式时间同构的 NP-complete 集，但多项式时间不能容忍无界阶段搜索，且已知归约的可逆性要求更强。Myhill 定理本身是绝对可计算性结果，不提供多项式时间界，也不能作为该猜想的证明。

参考资料

John Myhill, “Creative Sets,” Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 1(2), 1955, pp. 97–108，递归同构与 creative 集定理。
Piergiorgio Odifreddi, Classical Recursion Theory, Vol. I, North-Holland, 1989，p. 320，Myhill isomorphism theorem。
Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability, MIT Press, 1987，章节 “One-One Reducibility and Recursive Isomorphism”。

形式陈述 ​

形式陈述