算数阶层

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

 定义 
 按公式定义 

设  为自然数的语言中的公式，定义  为  公式当且仅当  中的所有量词都是有界量词（即形如  或  的量词，其中  为该语言中的项）。

定义  为  公式当且仅当 ，其中  为 ；定义  为  公式当且仅当 ，其中  为 。

更进一步定义  为  公式当且仅当 ，其中  为  公式；定义  为  公式当且仅当 ，其中  为  公式。

设 ；若存在  公式定义  则称  为  集合，若存在  公式定义  则称  为  公式。（若有公式  与集合 ，使 ，则称  定义 。）

 按可计算性定义 
若集合  可以用图灵机（或任何等价的计算模型）计算得出，则称  为  集合。若  为递归可枚举集合则称  为  集合，若  的补集  递归可枚举则称  为  集合。这一定义实际上与上面给出的定义是等价的。

更高阶层的算术类可以通过波斯特定理与可计算性联系起来：设  为零不可解度的第  次图灵跳跃，则任何集合  是  集合当且仅当  可以用具备  的预言机递归枚举；任何集合是  集合当且仅当其补集满足以上条件。

 举例 
 所有递归集合都是  集合、所有递归可枚举集合都是  集合（逆命题亦成立）。
 停机集合（即所有停机的图灵机）是  集合，它在  类中是完全的。
 所有有限递归可枚举集合的编号（记作 ）是 -完全集合（因此所有无限递归可枚举集合的编号是 -完全集合）。
 所有 -完全集合作为递归可枚举集合的编号是 -完全集合。

 参考资料 



Category:數理邏輯
Category:递归论
Category:描述集合论
Category:等级制度
Category:複雜度類