免疫集

Immune 集在集合论上很大——它含无限多个数——却不允许算法在其内部持续安全地采样。任何 c.e. 枚举器若不断给出新元素，最终必吐出一个不属于 $I$ 的数。困难不在检验已经挑出的有限前缀，而在保证过程可以无限延伸。

这种性质不能由“不可计算”代替。一个不可计算集合完全可能包含所有偶数，因而含有显然的无限可计算子集；它仍非 immune。反过来，immune 集必不可 c.e.：若它可枚举，它自己就是自身的无限 c.e. 子集。定义中的“无限”也不可省略，否则每个有限集合都会因为没有无限子集而空洞地满足条件。

Immune 与 productive 都表达有效枚举的失败，但量词不同。Immune 要求每个落在 $I$ 内的 c.e. 集都有限；productive function 只保证从任意 c.e. 子集索引有效找出 $I$ 中一个漏项，并不禁止该子集本身无限。把两者称为互补概念会丢掉这一关键差异。

它也不同于递归不可分集合对公理库递归不可分集合对Recursively inseparable sets · Computably inseparable pair · 递归不可分对两个互不相交的 c.e. 集合之间不存在可计算集合把一边全部纳入并与另一边完全隔开。：后者排除夹在两个不交集合之间的可计算 separator，而 immune 排除单个集合内部的无限 c.e. 子集。一个标准不可分对的两侧甚至通常就是 c.e.，若无限便不可能 immune；二者的共同点只是都用对角化击败一列有效候选。

下面给出一个可核查的 co-c.e. immune 集构造。让 $(W_e)$ 是 c.e. 集的统一枚举，逐阶段构造 c.e. 集 $S$。为每个 $e$ 设置要求

阶段 $s$ 查看有限近似 $W_{e,s}$；若某个尚未满足的 $e\le s$ 出现元素 $x>2e$，选择最小这样的 $e$，把一个相应 $x$ 枚举进 $S$，并永久标记 $P_e$ 已满足。每个要求至多放入一个数，因此在区间 $[0,2n]$ 内只有 $e<n$ 的要求可能贡献，至多有 $n$ 个数进入 $S$；于是补集 $I=\bar{S}$ 在这些区间中留下越来越多元素，必为无限。

若某个 $W_e\subseteq I$ 无限，它迟早枚举出 $x>2e$。比 $e$ 小的要求各至多行动一次，所以 $P_e$ 最终会选取 $W_e$ 的一个元素放入 $S$，与 $W_e\subseteq I$ 矛盾。因此 $I$ immune。这个构造还显示存在 co-c.e. immune 集，而 $S$ 正是一个simple 集公理库递归论中的 Simple 集Simple set · Simple c.e. set · Post simple set自身 c.e.、补集却无限且不含任何无限 c.e. 子集的集合。。

边界上，补集运算不保持 immune：上例的 $S$ 是无限 c.e.，所以不是 immune。$\bar{K}$ 也不能仅因 $K$ 是停机集就宣布 immune；padding 可有效产生无限多个处处发散程序索引，形成 $\bar{K}$ 内的无限可计算子集。判断 immune 必须排除所有无限 c.e. 子集，非计算性或某个对角描述都不够。

若 $S$ c.e. 且 $\bar{S}$ immune，则 $S$ 不可判定：若 $S$ 有判定器，无限补集也可判定、从而 c.e.，成为自身的无限 c.e. 子集。这给 Post 构造 simple 集的第一项目标——得到非可计算 c.e. 集——一个直接证明。

Immune 性还能表达“没有无限有效同质子结构”。在可计算组合学与算法随机性中，研究者会问某个无限集合是否含无限 c.e. 子集、是否只在更强 oracle 下能抽取这样的子集。需要更均匀的大小控制时，应升级到 effectively immune；需要控制递增枚举的增长速度时，应使用 hyperimmune，而不能从普通 immune 自动推出。

构造中阈值 $x>2e$ 承担两件不同工作：每个 $P_e$ 的单次行动击中无限 $W_e$，随 $e$ 增长的保留区又保证补集无限。若去掉阈值，只知每个要求放一个数，并不能阻止这些数恰好覆盖全部自然数；若每个要求允许无限行动，则计数不变量也会崩溃。