算数阶层

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

定义

按公式定义

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

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

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

设 ${\displaystyle A\subseteq \mathbb {N} }$ ；若存在 ${\displaystyle \Sigma _{n}^{0}}$  公式定义 ${\displaystyle A}$  则称 ${\displaystyle A}$  为 ${\displaystyle \Sigma _{n}^{0}}$  集合，若存在 ${\displaystyle \Pi _{n}^{0}}$  公式定义 ${\displaystyle A}$  则称 ${\displaystyle A}$  为 ${\displaystyle \Pi _{n}^{0}}$  公式。（若有公式 ${\displaystyle \phi }$  与集合 ${\displaystyle A}$ ，使 ${\displaystyle A=\{x\;\vert \;\mathbb {N} \vDash \phi (x)\}}$ ，则称 ${\displaystyle \phi }$  定义 ${\displaystyle A}$ 。）

按可计算性定义

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

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

举例

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

参考资料

• H. D. Ebbinghaus, J. Flum, Wolfgang Thomas. Mathematical Logic (Undergraduate Texts in Mathematics) 2nd edition. Springer. 1996. ISBN 9780387942582 （英语）.  引文格式1维护：冗余文本 (link)
• Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 （英语）.