可计算性理论中的算术分层 算术分层是描述自然数集上可定义性复杂度的分类体系。让我们从分层的基本动机开始理解。 分层动机 在可计算性理论中，我们关心哪些自然数集是可判定的（递归集）或可半判定的（递归可枚举集）。但许多自然数集（如皮亚诺算术的真语句集）不可计算。算术分层通过量词交替的复杂度，对这些集合进行精细分类。其核心思想是：一个集合的定义中量词（∀, ∃）交替的次数越多，其计算复杂度越高。 公式的算术分层 首先对一阶算术公式分类（定义域为自然数，含符号+, ×, 0, 1, =, <）： Σ₀公式 （亦称Δ₀公式）：所有量词均有界（如∀x <y, ∃z≤t），即量词范围受限于某个变量。 Σ₁公式 ：形如∃y φ(x,y)，其中φ是Σ₀公式。 Π₁公式 ：形如∀y φ(x,y)，其中φ是Σ₀公式。 一般地， Σₙ₊₁公式 ：形如∃y ψ(x,y)，其中ψ是Πₙ公式。 Πₙ₊₁公式 ：形如∀y ψ(x,y)，其中ψ是Σₙ公式。 Δₙ公式 ：既是Σₙ又是Πₙ的公式。 集合的算术分层 一个自然数集A ⊆ ℕ属于 Σₙ层 （记作A ∈ Σₙ），若存在Σₙ公式φ(x)使得A = {n ∈ ℕ | φ(n)为真}。类似定义Πₙ层和Δₙ层。注意： Σ₀ = Π₀ = Δ₀（有界公式定义的集合恰好是原始递归集）。 Δ₁集合恰好是递归集（可判定集）。 Σ₁集合恰好是递归可枚举集（可半判定集）。 对n≥1，Δₙ集合严格介于Σₙ和Πₙ之间。 分层的基本性质 包含关系 ：Σₙ ∪ Πₙ ⊆ Δₙ₊₁。 真包含性 ：Σₙ ⊊ Δₙ₊₁，Πₙ ⊊ Δₙ₊₁（由波斯特定理推广）。 对偶性 ：A ∈ Σₙ 当且仅当补集Aᶜ ∈ Πₙ。 归一性 ：每个Σₙ（或Πₙ）集合可被一个“通用”Σₙ（Πₙ）集合多一归约定义，存在通用Σₙ集。 与图灵度的联系 算术分层与图灵跳跃操作密切相关： Σ₁集合的图灵度不超过0′（停机问题的度）。 一般地，Σₙ₊₁集合可被Πₙ集的图灵机判定，即度不超过0⁽ⁿ⁺¹⁾（n次跳跃后的一次跳跃）。 算术分层中所有集合的图灵度构成算术度，严格低于任何非算术度。 完备性问题 每层Σₙ或Πₙ存在完备集： 例如，Σ₁的完备集是停机问题K。 Π₁的完备集是全体语句的集合。 高层完备集可通过对低层集的量化定义得到，如Tot = {e | φ_ e是全函数}是Π₂完备集。 应用与意义 算术分层是描述不可计算问题复杂度的标尺： 在逆向数学中，用于分析公理系统的证明强度。 在描述复杂性中，与多项式时间分层类比。 在模型论中，用于分类可定义集的结构性质。