查看“︁算数阶层”︁的源代码

{{no footnotes|time=2019-04-17T04:08:39+00:00}}
{{NoteTA
|G1 = IT
|G2 = Math
}}
'''算术阶层'''是[[递归论]]或[[可计算性理论]]中的概念，将[[自然数]]的[[子集]]按照定义它们的公式的复杂度分类。

== 定义 ==
=== 按公式定义 ===

设 <math>\phi(x)</math> 为自然数的[[形式语言|语言]]中的公式，定义 <math>\phi</math> 为 <math>\Delta_0</math> 公式当且仅当 <math>\phi</math> 中的所有量词都是有界量词（即形如 <math>\exists n<t</math> 或 <math>\forall n<t</math> 的量词，其中 <math>t</math> 为该语言中的项）。

定义 <math>\phi(x)</math> 为 <math>\Sigma^0_1</math> 公式当且仅当 <math>\phi(x):=\exists n\,\theta(n,x)</math>，其中 <math>\theta</math> 为 <math>\Delta_0</math>；定义 <math>\phi</math> 为 <math>\Pi^0_1</math> 公式当且仅当 <math>\phi(x):=\forall n\,\theta(n,x)</math>，其中 <math>\theta</math> 为 <math>\Delta_0</math>。

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

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

=== 按可计算性定义 ===
若集合 <math>A</math> 可以用[[图灵机]]（或任何等价的[[计算模型]]）计算得出，则称 <math>A</math> 为 <math>\Delta_0</math> 集合。若 <math>A</math> 为[[递归可枚举集合]]则称 <math>A</math> 为 <math>\Sigma^0_1</math> 集合，若 <math>A</math> 的补集 <math>\mathbb{N}\backslash A</math> 递归可枚举则称 <math>A</math> 为 <math>\Pi^0_1</math> 集合。这一定义实际上与上面给出的定义是等价的。

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

== 举例 ==
* 所有[[递归集合]]都是 <math>\Delta_0</math> 集合、所有[[递归可枚举集合]]都是 <math>\Sigma^0_1</math> 集合（[[逆命题]]亦成立）。
* [[停机问题|停机集合]]（即所有停机的图灵机）是 <math>\Sigma^0_1</math> 集合，它在 <math>\Sigma^0_1</math> 类中是[[完备 (复杂度)|完全]]的。
* 所有有限递归可枚举集合的编号（记作 <math>\mathrm{Fin}</math>）是 <math>\Sigma^0_2</math>-完全集合（因此所有无限递归可枚举集合的编号是 <math>\Pi^0_2</math>-完全集合）。
* 所有 <math>\Sigma^0_1</math>-完全集合作为递归可枚举集合的编号是 <math>\Sigma^0_3</math>-完全集合。

== 参考资料 ==
* {{cite book|language=en|author=H. D. Ebbinghaus, J. Flum, Wolfgang Thomas|title=Mathematical Logic (Undergraduate Texts in Mathematics)|url=https://archive.org/details/mathematicallogi1996ebbi|year=1996|publisher=Springer|edition=2nd edition|isbn=9780387942582}}
* {{cite book|language=en|author=Robert I. Soare|title=Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets|year=2004|publisher=Springer|isbn=9780387152998}}

[[Category:集合论]]
[[分类:数学概念]]
[[Category:递归论]]
[[Category:计算机科学]]