算数阶层

Template:No footnotes Template:NoteTA 算术阶层是递归论或可计算性理论中的概念，将自然数的子集按照定义它们的公式的复杂度分类。

定义

按公式定义

设 $\varphi (x)$ 为自然数的语言中的公式，定义 $\varphi$ 为 ${\mathrm{\Delta }}_0$ 公式当且仅当 $\varphi$ 中的所有量词都是有界量词（即形如 $\mathrm{\exists }n<t$ 或 $\mathrm{\forall }n<t$ 的量词，其中 $t$ 为该语言中的项）。

定义 $\varphi (x)$ 为 ${\mathrm{\Sigma }}_1^0$ 公式当且仅当 $\varphi (x):=\mathrm{\exists }n\theta (n,x)$，其中 $\theta$ 为 ${\mathrm{\Delta }}_0$；定义 $\varphi$ 为 ${\mathrm{\Pi }}_1^0$ 公式当且仅当 $\varphi (x):=\mathrm{\forall }n\theta (n,x)$，其中 $\theta$ 为 ${\mathrm{\Delta }}_0$。

更进一步定义 $\varphi (x)$ 为 ${\mathrm{\Sigma }}_{n+1}^0$ 公式当且仅当 $\varphi (x):=\mathrm{\exists }n\theta (n,x)$，其中 $\theta$ 为 ${\mathrm{\Pi }}_n^0$ 公式；定义 $\varphi (x)$ 为 ${\mathrm{\Pi }}_{n+1}^0$ 公式当且仅当 $\varphi (x):=\mathrm{\forall }n\theta (n,x)$，其中 $\theta$ 为 ${\mathrm{\Sigma }}_n^0$ 公式。

设 $A\subseteq \mathbb{N}$；若存在 ${\mathrm{\Sigma }}_n^0$ 公式定义 $A$ 则称 $A$ 为 ${\mathrm{\Sigma }}_n^0$ 集合，若存在 ${\mathrm{\Pi }}_n^0$ 公式定义 $A$ 则称 $A$ 为 ${\mathrm{\Pi }}_n^0$ 公式。（若有公式 $\varphi$ 与集合 $A$，使 $A=\{x|\mathbb{N}\models \varphi (x)\}$，则称 $\varphi$ 定义 $A$。）

按可计算性定义

若集合 $A$ 可以用图灵机（或任何等价的计算模型）计算得出，则称 $A$ 为 ${\mathrm{\Delta }}_0$ 集合。若 $A$ 为递归可枚举集合则称 $A$ 为 ${\mathrm{\Sigma }}_1^0$ 集合，若 $A$ 的补集 $\mathbb{N}\mathrm{\setminus }A$ 递归可枚举则称 $A$ 为 ${\mathrm{\Pi }}_1^0$ 集合。这一定义实际上与上面给出的定义是等价的。

更高阶层的算术类可以通过波斯特定理与可计算性联系起来：设 ${\mathrm{𝟘}}^{(n)}$ 为零不可解度的第 $n$ 次图灵跳跃，则任何集合 $A$ 是 ${\mathrm{\Sigma }}_{n+1}^0$ 集合当且仅当 $A$ 可以用具备 ${\mathrm{𝟘}}^{(n)}$ 的预言机递归枚举；任何集合是 ${\mathrm{\Pi }}_{n+1}^0$ 集合当且仅当其补集满足以上条件。

举例

• 所有递归集合都是 ${\mathrm{\Delta }}_0$ 集合、所有递归可枚举集合都是 ${\mathrm{\Sigma }}_1^0$ 集合（逆命题亦成立）。
• 停机集合（即所有停机的图灵机）是 ${\mathrm{\Sigma }}_1^0$ 集合，它在 ${\mathrm{\Sigma }}_1^0$ 类中是完全的。
• 所有有限递归可枚举集合的编号（记作 $\mathrm{F}\mathrm{i}\mathrm{n}$）是 ${\mathrm{\Sigma }}_2^0$-完全集合（因此所有无限递归可枚举集合的编号是 ${\mathrm{\Pi }}_2^0$-完全集合）。
• 所有 ${\mathrm{\Sigma }}_1^0$-完全集合作为递归可枚举集合的编号是 ${\mathrm{\Sigma }}_3^0$-完全集合。

参考资料

• Template:Cite book
• Template:Cite book