算术阶层是递归论或可计算性理论中的概念，将自然数的子集按照定义它们的公式的复杂度分类。
定义
按公式定义
设 \phi(x) 为自然数的语言中的公式，定义 \phi 为 \Delta_0 公式当且仅当 \phi 中的所有量词都是有界量词（即形如 \exists n 或 \forall n 的量词，其中 t 为该语言中的项）。
定义 \phi(x) 为 \Sigma^0_1 公式当且仅当 \phi(x):=\exists n\,\theta(n,x)，其中 \theta 为 \Delta_0；定义 \phi 为 \Pi^0_1 公式当且仅当 \phi(x):=\forall n\,\theta(n,x)，其中 \theta 为 \Delta_0。
更进一步定义 \phi(x) 为 \Sigma^0_{n+1} 公式当且仅当 \phi(x):=\exists n\,\theta(n,x)，其中 \theta 为 \Pi^0_n 公式；定义 \phi(x) 为 \Pi^0_{n+1} 公式当且仅当 \phi(x):=\forall n\,\theta(n,x)，其中 \theta 为 \Sigma^0_n 公式。
设 A\subseteq\mathbb{N}；若存在 \Sigma^0_n 公式定义 A 则称 A 为 \Sigma^0_n 集合，若存在 \Pi^0_n 公式定义 A 则称 A 为 \Pi^0_n 公式。（若有公式 \phi 与集合 A，使 A=\{x\;\vert\;\mathbb{N}\vDash\phi(x)\}，则称 \phi 定义 A。）
按可计算性定义
若集合 A 可以用图灵机（或任何等价的计算模型）计算得出，则称 A 为 \Delta_0 集合。若 A 为递归可枚举集合则称 A 为 \Sigma^0_1 集合，若 A 的补集 \mathbb{N}\backslash A 递归可枚举则称 A 为 \Pi^0_1 集合。这一定义实际上与上面给出的定义是等价的。
更高阶层的算术类可以通过波斯特定理与可计算性联系起来：设 \mathbb{0}^{(n)} 为零不可解度的第 n 次图灵跳跃，则任何集合 A 是 \Sigma^0_{n+1} 集合当且仅当 A 可以用具备 \mathbb{0}^{(n)} 的预言机递归枚举；任何集合是 \Pi^0_{n+1} 集合当且仅当其补集满足以上条件。
举例
- 所有递归集合都是 \Delta_0 集合、所有递归可枚举集合都是 \Sigma^0_1 集合（逆命题亦成立）。
- 停机集合（即所有停机的图灵机）是 \Sigma^0_1 集合，它在 \Sigma^0_1 类中是完全的。
- 所有有限递归可枚举集合的编号（记作 \mathrm{Fin}）是 \Sigma^0_2-完全集合（因此所有无限递归可枚举集合的编号是 \Pi^0_2-完全集合）。
- 所有 \Sigma^0_1-完全集合作为递归可枚举集合的编号是 \Sigma^0_3-完全集合。
参考资料
*
*
评论 (0)