递归论中的 Simple 集

形式陈述

集合 $S\subseteq\mathbb N$ 称为 simple，若 $S$ 是可计算枚举集合，并且补集 $\overline S$ 是immune 集。展开定义即

S\text{ c.e.},\qquad \overline S\text{ infinite},\qquad \forall e\,[W_e\subseteq\overline S\Rightarrow W_e\text{ finite}].

因此 simple 集是 c.e. 集的一个严格子类；“simple”不表示其成员资格可简单判定。事实上每个 simple 集都不可计算：若 $S$ 可判定，无限的 $\overline S$ 也可判定并可枚举，直接违反 immune 性。

常用等价要求写成

P_e:\quad W_e\text{ infinite}\Longrightarrow W_e\cap S\ne\varnothing.

若 $S$ c.e. 且 coinfinite，所有 $P_e$ 成立恰好说明补集中没有无限 c.e. 子集。这种逐要求形式使定义可以用阶段构造实现。

直觉

Simple 集一边允许算法不断枚举自己的元素，另一边又把剩余空间切得足够零散，使任何无限有效枚举都无法永远躲在补集里。构造者不必知道 $W_e$ 是否真的无限；只需等待它露出一个足够大的元素，然后把该元素吸收到 $S$ ，便永久破坏“ $W_e$ 是补集的无限子集”这一可能性。

难点是同时保留无限补集。若见到每个枚举元素就全部放进 $S$ ，当然能击中所有 $W_e$ ，却可能得到 $S=\mathbb N$ ；若为保留空间而完全不行动，又无法满足要求。大小 restraint 把二者平衡：低编号要求只获准拿走一个远处元素，因而任何有限初段附近都有可计数的剩余。

Simple 性只组织 c.e. 子集，不直接控制 Turing degree。Post 最初希望这种“补集无有效无限片段”的稀薄性会迫使 $S$ 不完全，但 simple 只立即给出非可计算；能否计算 $0'$ 是另一组全局 oracle 要求。

例子与边界

固定可接受编号给出的统一枚举 $(W_e)$ 。从 $S_0=\varnothing$ 开始。阶段 $s$ 搜索最小的尚未满足 $e\le s$ ，使有限近似 $W_{e,s}$ 含某个 $x>2e$ ；若找到，就选其中一个 $x$ 放入 $S_{s+1}$ ，并把 $P_e$ 标记完成，否则保持不变。令 $S=\bigcup_sS_s$ 。

阶段规则是有效的，故 $S$ c.e.。若 $W_e$ 无限，它最终出现大于 $2e$ 的元素；只有有限多个更小要求可能先行动，故 $P_e$ 终会满足。对任意 $n$ ，落在 $[0,2n]$ 的已枚举元素只能来自 $e<n$ ，而每个这样的要求至多选一个，所以该区间至少留下 $n+1$ 个数不在 $S$ ；补集无限。若补集含无限 c.e. 集 $W_e$ ， $P_e$ 又强迫它和 $S$ 相交，矛盾。因此这确实是一个 simple 集。

边界必须逐项保留。一个 finite c.e. 集的补集虽无限，却含大量无限可计算子集，所以不 simple；一个 immune 集自身不能是无限 c.e.，也不是 simple 的另一种写法；一个 coinfinite 非计算 c.e. 集若漏掉某个无限可计算集合，同样不 simple。

Simple 也不等于 Turing 不完备。存在 low simple 集，其 degree 严格低于 $0'$ ；另一方面，加强为 effectively simple 会导出 Turing 完备性。由此可见，同一补集交叉性质可与不同 jump 行为共存，不能把 Post 问题的历史动机写成定义结论。

推论与应用

Simple 集是优先法的原型。每个 $P_e$ 只需一次行动，要求之间几乎不伤害；加入 low、incomplete 或其他 degree 条件后，元素的枚举可能破坏先前依赖有限 oracle use 的计算，才出现 restraint、injury 与优先次序。基础构造因而提供了读懂复杂有限伤害论证的最小模型。

它还说明“c.e. 非计算”可以由补集的组合结构保证，而无需直接归约停机问题。证明不可计算只用一行反证：若 $S$ 可计算， $\overline S$ 是无限 c.e. 子集。与creative 集的 many-one 完全性相比，simple 性刻画的是补集避开有效无限子集的失败，两种性质回答不同问题；它们的对比不把 immune 与 productive 误当逻辑互补。

在可计算结构或形式理论中，类似要求可用于构造一个有效生成对象，同时让其余部分没有无限有效子对象。迁移时仍须重建“每个要求只取有限资源”和“全局保留无限空间”两项不变量；只把术语 simple 借来描述稀疏外观，不会自动得到递归论结论。

参考资料

Emil L. Post, “Recursively Enumerable Sets of Positive Integers and Their Decision Problems,” Bulletin of the American Mathematical Society 50(5), 1944, pp. 284–316，simple sets 与 Post 问题。
Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer, 1987，Chapter II，simple sets and priority constructions。
André Nies, Computability and Randomness, Oxford University Press, 2009，pp. 35–37，simple、hypersimple 与 low simple 构造。

形式陈述 ​

反向链接

形式陈述