算數階層

算術階層是遞歸論或可計算性理論中的概念，將自然數的子集按照定義它們的公式的複雜度分類。

定義

按公式定義

設 $\phi (x)$ 為自然數的語言中的公式，定義 $\phi$ 為 $\Delta _{0}$ 公式當且僅當 $\phi$ 中的所有量詞都是有界量詞（即形如 $\exists n<t$ 或 $\forall n<t$ 的量詞，其中 $t$ 為該語言中的項）。

定義 $\phi (x)$ 為 $\Sigma _{1}^{0}$ 公式當且僅當 $\phi (x):=\exists n\,\theta (n,x)$，其中 $\theta$ 為 $\Delta _{0}$；定義 $\phi$ 為 $\Pi _{1}^{0}$ 公式當且僅當 $\phi (x):=\forall n\,\theta (n,x)$，其中 $\theta$ 為 $\Delta _{0}$。

更進一步定義 $\phi (x)$ 為 $\Sigma _{n+1}^{0}$ 公式當且僅當 $\phi (x):=\exists n\,\theta (n,x)$，其中 $\theta$ 為 $\Pi _{n}^{0}$ 公式；定義 $\phi (x)$ 為 $\Pi _{n+1}^{0}$ 公式當且僅當 $\phi (x):=\forall n\,\theta (n,x)$，其中 $\theta$ 為 $\Sigma _{n}^{0}$ 公式。

設 $A\subseteq \mathbb {N}$；若存在 $\Sigma _{n}^{0}$ 公式定義 $A$ 則稱 $A$ 為 $\Sigma _{n}^{0}$ 集合，若存在 $\Pi _{n}^{0}$ 公式定義 $A$ 則稱 $A$ 為 $\Pi _{n}^{0}$ 公式。（若有公式 $\phi$ 與集合 $A$，使 $A=\{x\;\vert \;\mathbb {N} \vDash \phi (x)\}$，則稱 $\phi$ 定義 $A$。）

按可計算性定義

若集合 $A$ 可以用圖靈機（或任何等價的計算模型）計算得出，則稱 $A$ 為 $\Delta _{0}$ 集合。若 $A$ 為遞歸可枚舉集合則稱 $A$ 為 $\Sigma _{1}^{0}$ 集合，若 $A$ 的補集 $\mathbb {N} \backslash A$ 遞歸可枚舉則稱 $A$ 為 $\Pi _{1}^{0}$ 集合。這一定義實際上與上面給出的定義是等價的。

更高階層的算術類可以通過波斯特定理與可計算性聯繫起來：設 $\mathbb {0} ^{(n)}$ 為零不可解度的第 $n$ 次圖靈跳躍，則任何集合 $A$ 是 $\Sigma _{n+1}^{0}$ 集合當且僅當 $A$ 可以用具備 $\mathbb {0} ^{(n)}$ 的預言機遞歸枚舉；任何集合是 $\Pi _{n+1}^{0}$ 集合當且僅當其補集滿足以上條件。

舉例

• 所有遞歸集合都是 $\Delta _{0}$ 集合、所有遞歸可枚舉集合都是 $\Sigma _{1}^{0}$ 集合（逆命題亦成立）。
• 停機集合（即所有停機的圖靈機）是 $\Sigma _{1}^{0}$ 集合，它在 $\Sigma _{1}^{0}$ 類中是完全的。
• 所有有限遞歸可枚舉集合的編號（記作 $\mathrm {Fin}$）是 $\Sigma _{2}^{0}$-完全集合（因此所有無限遞歸可枚舉集合的編號是 $\Pi _{2}^{0}$-完全集合）。
• 所有 $\Sigma _{1}^{0}$-完全集合作為遞歸可枚舉集合的編號是 $\Sigma _{3}^{0}$-完全集合。

參考資料

• H. D. Ebbinghaus, J. Flum, Wolfgang Thomas. Mathematical Logic (Undergraduate Texts in Mathematics) 2nd edition. Springer. 1996. ISBN 9780387942582 （英語）.  引文格式1維護：冗餘文本 (link)
• Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 （英語）.