算术层级

算术层级通过定义自然数集合所需的交替量词数量对其进行分类，将逻辑复杂性与不可计算程度联系起来。

Definition

算术层级通过计算可计算矩阵（computable matrix）前无界量词的交替次数，对一阶算术（first-order arithmetic）中可定义的集合进行分层，其中西格玛-n（sigma-n）集合由以存在量词开头的块定义，皮-n（pi-n）集合由以全称量词开头的块定义。

Scope

本主题涵盖了通过可计算关系上的量词交替将可定义集合分类为西格玛（sigma）、皮（pi）和德尔塔（delta）层级，波斯特定理（Post's theorem）将该层级与迭代停机问题和图灵跳跃（Turing jumps）联系起来，层级的严格性，以及其向分析层级（analytical hierarchy）的扩展。

Core questions

• 量词交替如何衡量集合的复杂性？
• 每个层级的西格玛、皮和德尔塔类之间有何关系？
• 该层级如何与迭代停机问题相对应？
• 为什么该层级是严格的，每个层级都比前一个层级更大？

Key theories

量词分类

如果一个集合可以通过n个交替量词块（以存在量词开头）在可计算关系上定义，则为西格玛-n；如果以全称量词开头，则为皮-n；可计算可枚举集合恰好是西格玛-1集合。

波斯特定理

一个集合恰好是西格玛-(n+1)当且仅当它相对于第n个图灵跳跃是可计算可枚举的，这使得层级的各个级别与迭代的相对停机问题相关联。

层级的严格性

每个图灵跳跃都比前一个严格更复杂，因此算术层级的每个级别都严格包含其下方的级别，并且该层级不会崩溃。

Clinical relevance

算术层级是逻辑和计算机科学中可定义问题复杂性的标准衡量工具：它将可计算集合的完全性（totality）、有限性（finiteness）和余有限性（cofiniteness）等问题定位在精确的层级上，并构成了可计算可枚举（computably enumerable）与需要更强不可计算资源之间界限的框架。

History

克莱尼（Kleene）和莫斯托夫斯基（Mostowski）在大约1943年独立提出了算术层级，通过可计算谓词（computable predicates）上的量词复杂性对集合进行分类。波斯特定理将该层级与图灵跳跃联系起来，统一了基于可定义性和基于可计算性的视角，该框架后来向上扩展到分析层级。

Key figures

• Stephen Cole Kleene
• Andrzej Mostowski
• Emil Post

Seminal works

• rogers1987
• soare1987
• cutland1980

Frequently asked questions

层级中更高的级别意味着什么？

更多的交替量词意味着更复杂的定义，并且根据波斯特定理，一个问题需要更多次迭代停机问题才能决定。层级中较高的集合在计算上比其下方的集合更难访问。

可计算可枚举集合位于何处？

它们占据西格玛-1级别，可以通过可计算关系上的单个存在量词定义。它们的补集占据皮-1级别，而同时属于这两者的集合，即德尔塔-1集合，恰好是可计算集合。