算数阶层

维基百科,自由的百科全书
(重定向自算术谱系
跳转至: 导航搜索

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

定义[编辑]

按公式定义[编辑]

为自然数的语言中的公式,定义 公式当且仅当 中的所有量词都是有界量词(即形如 的量词,其中 为该语言中的项)。

定义 公式当且仅当 ,其中 ;定义 公式当且仅当 ,其中

更进一步定义 公式当且仅当 ,其中 公式;定义 公式当且仅当 ,其中 公式。

;若存在 公式定义 则称 集合,若存在 公式定义 则称 公式。(若有公式 与集合 ,使 ,则称 定义 。)

按可计算性定义[编辑]

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

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

举例[编辑]

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

参考资料[编辑]

  • H. D. Ebbinghaus, J. Flum, Wolfgang Thomas. Mathematical Logic (Undergraduate Texts in Mathematics) 2nd edition. Springer. 1996. ISBN 9780387942582 (英语). 
  • Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 (英语).