递归可枚举集

递归可枚举集是Σ_1

在递归论学到KP和EDST时，我产生了一个疑问：作为由图灵机的定义域定义的r.e.关系和作为Σ⁰₁ 公式定义的关系如何一样，当我们在集合论（的模型）中处理图灵机时，我们将它看成什么。

这里我稍微记录一下二者是如何交互的。

定义1：我们说Δ⁰₀ 公式是指满足如下条件的最小的一阶算术公式集合：

1. 原子公式是 Δ⁰₀ 的；

2. 若 φ，ψ 是 Δ⁰₀ 的，则 ¬φ，φ → ψ 都是 Δ⁰₀ 的；

3. 若 φ(ˉx，y) 是 Δ⁰₀ 的，则 ∀y＜z φ(ˉx，y) 和 ∃y＜z φ(ˉx，y) 都是 Δ⁰₀ 的，这里 x，y 都是自然数变量。

接下来是Σ⁰ₙ 公式。

定义2：1. 一个公式φ(ˉx) 是 Σ⁰₁ 的当且仅当存在 Δ⁰₀ 公式 ψ(ˉx，y) 使得 φ(ˉx) ↔ ∃x ψ(ˉx，y) ；

2. 一个公式 φ 是 Π⁰₁ 的当且仅当 ¬φ 是 Σ⁰₁ 的；

3. 一个公式 φ 是 Σ⁰ₙ₊₁ 的当且仅当存在 Π⁰ₙ 公式 ψ(y) 使得 φ ↔ ∃y ψ(y) ；

4. 一个公式 φ 是 Π⁰ₙ₊₁ 的当且仅当存在 Σ⁰ₙ 公式 ψ(y) 使得 φ ↔ ∀y ψ(y) ；

5. 一个公式是 Δ⁰ₙ 的当且仅当 φ，¬φ 都是 Σ⁰ₙ 的。

一个关系R ⊂ ℕⁿ 为 Σ⁰ₙ 的当且仅当存在 Σ⁰ₙ 的公式 φ(ˉx) 使得 R＝{ˉx，φ(ˉx)} ，一个函数 f：ℕⁿ → ℕ 称为是 Σ⁰ₙ 当且仅当其图像 Gf＝{(ˉx，y)：y＝f(ˉx)} 作为关系是 Σ⁰ₙ 的，类似地可定义 Π⁰ₙ，Δ⁰ₙ 的关系和函数。

现在，我们称一个关系R ⊂ ℕⁿ 是递归可枚举的（r.e.）当且仅当存在 e 使得R＝{ˉx：Φₑ(ˉx)↓} ，即其为一个图灵机的定义域。

很多递归论的教材里会把Σ⁰₁ 关系 P 定义为存在递归关系 R 使得 P(ˉx) ↔ ∃yR(ˉx，y) ，然后证明 Σ⁰₁ 关系正好就是递归可枚举关系。但这种方法多少有些衔尾蛇的感觉。

定理：一个关系R ⊂ ℕⁿ 是 Σ⁰₁ 的当且仅当它是递归可枚举的。

proof：考察Kleene的原始递归谓词T(e，ˉx，z) ，这个原始递归谓词实际上是 Δ⁰₀ 的，其意思大概就是在说：“ e 是一个图灵机程序，并且 z 是这个图灵机对输入 ˉx 时的计算过程的编码，且计算过程停机”。具体的用一个 Δ⁰₀ 公式表示这个关系只涉及到特定的编码技巧，虽然复杂但没有本质上的困难。

则对任何图灵机Φₑ ，都有 ∀ˉx [Φₑ(ˉx)↓↔∃z T(e，ˉx，z)] 从而我们就能将 R：＝{ˉx：Φₑ(ˉx)↓} 写成 {ˉx：∃z T(e，ˉx，z)} 。这也就完成了定理的证明。 ▢

实际上，我们甚至能只用多项式来得到所有递归可枚举关系。称一个关系 R ⊂ ℕⁿ 是丢番图的，当且仅当存在正整数系数多项式 P(ˉx，ˉy) 和 Q(ˉx，ˉy) 使得 R＝{ˉx：∃ˉy P(ˉx，ˉy)＝Q(ˉx，ˉy)}。由著名的马季亚谢维奇定理——就是那个解决了希尔伯特第十问题的定理——一个关系是递归可枚举的当且仅当它是丢番图的。

这表明我们可以放心地在集合论里用比较简单的公式表示递归可枚举关系，而不用讨论到底什么是（集合论中的）图灵机。

但有时候我们必不可少的遇到在集合论的模型中讨论有关图灵机的满足关系，比如M╞ Φₑ(x)↓这种表述。这时候我们怎么看待图灵机呢？这里实际上也可以直接用克林尼的原始递归谓词代替： M╞ Φₑ (x)↓⇔ M╞ ∃z T(e，x，z)

这样就没有任何疑惑了。