You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

关于库珀《可计算性理论》中塞尔曼枚举可归约性定理证明的困惑

关于库珀《可计算性理论》中塞尔曼枚举可归约性定理证明的困惑

最近翻Barry Cooper 2004年出版的《Computability Theory》,在第179页下半部分看到了塞尔曼定理及其证明梗概,原文内容我直接抄录如下:

THEOREM 11.1.13 (Selman's Theorem, 1971)
对于任意 $A,B\subseteq\mathbb{N}$
$$A \mathrel{\leq_e} B ;\Longleftrightarrow; \forall X[B\text{ c.e. in }X \Rightarrow A\text{ c.e. in }X]$$

PROOF (sketch) 从左到右的推导我就留给你自己琢磨啦。

反过来,假设 $A \mathrel{\not\leq_e} B$。我们将构造一个集合 $C = \bigcup_{s\geq 0} C _ s$,使得 $B$ 在 $C$ 中是递归可枚举的,但 $A$ 在 $C$ 中不是递归可枚举的。

我们需要满足“$B$ c.e. in $C$”这个条件——(原文此处内容未完整呈现)

备注:内容来源于stack exchange,提问作者Gro-Tsen

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.04.17 09:27:58