算數階層

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

定義

按公式定義

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

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

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

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

按可計算性定義

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

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

舉例

• 所有遞迴集合都是 ${\displaystyle \Delta _{0}}$ 集合、所有遞迴可列舉集合都是 ${\displaystyle \Sigma _{1}^{0}}$ 集合（逆命題亦成立）。
• 停機集合（即所有停機的圖靈機）是 ${\displaystyle \Sigma _{1}^{0}}$ 集合，它在 ${\displaystyle \Sigma _{1}^{0}}$ 類中是完全的。
• 所有有限遞迴可列舉集合的編號（記作 ${\displaystyle \mathrm {Fin} }$）是 ${\displaystyle \Sigma _{2}^{0}}$-完全集合（因此所有無限遞迴可列舉集合的編號是 ${\displaystyle \Pi _{2}^{0}}$-完全集合）。
• 所有 ${\displaystyle \Sigma _{1}^{0}}$-完全集合作為遞迴可列舉集合的編號是 ${\displaystyle \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 （英語）.