算数阶层

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

设 ${\displaystyle \mathrm{\varphi <!--\; \varphi \; -->}(x)}$ 为自然数的语言中的公式，定义 ${\displaystyle \mathrm{\varphi <!--\; \varphi \; -->}}$ 为 ${\displaystyle {\mathrm{\Delta <!--\; \Delta \; -->}}_0}$ 公式当且仅当 ${\displaystyle \mathrm{\varphi <!--\; \varphi \; -->}}$ 中的所有量词都是有界量词（即形如 或 的量词，其中 ${\displaystyle t}$ 为该语言中的项）。

定义 ${\displaystyle \mathrm{\varphi <!--\; \varphi \; -->}(x)}$ 为 ${\displaystyle {\mathrm{\Sigma <!--\; \Sigma \; -->}}_1^0}$ 公式当且仅当 ${\displaystyle \mathrm{\varphi <!--\; \varphi \; -->}(x):=\mathrm{\exists <!--\; \exists \; -->}n\mathrm{\theta <!--\; \theta \; -->}(n,x)}$，其中 ${\displaystyle \mathrm{\theta <!--\; \theta \; -->}}$ 为 ${\displaystyle {\mathrm{\Delta <!--\; \Delta \; -->}}_0}$；定义 ${\displaystyle \mathrm{\varphi <!--\; \varphi \; -->}}$ 为 ${\displaystyle {\mathrm{\Pi <!--\; \Pi \; -->}}_1^0}$ 公式当且仅当 ${\displaystyle \mathrm{\varphi <!--\; \varphi \; -->}(x):=\mathrm{\forall <!--\; \forall \; -->}n\mathrm{\theta <!--\; \theta \; -->}(n,x)}$，其中 ${\displaystyle \mathrm{\theta <!--\; \theta \; -->}}$ 为 ${\displaystyle {\mathrm{\Delta <!--\; \Delta \; -->}}_0}$。

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

设 ${\displaystyle A\subseteq <!--\; \subseteq \; -->\mathbb{N}}$；若存在 ${\displaystyle {\mathrm{\Sigma <!--\; \Sigma \; -->}}_n^0}$ 公式定义 ${\displaystyle A}$ 则称 ${\displaystyle A}$ 为 ${\displaystyle {\mathrm{\Sigma <!--\; \Sigma \; -->}}_n^0}$ 集合，若存在 ${\displaystyle {\mathrm{\Pi <!--\; \Pi \; -->}}_n^0}$ 公式定义 ${\displaystyle A}$ 则称 ${\displaystyle A}$ 为 ${\displaystyle {\mathrm{\Pi <!--\; \Pi \; -->}}_n^0}$ 公式。（若有公式 ${\displaystyle \mathrm{\varphi <!--\; \varphi \; -->}}$ 与集合 ${\displaystyle A}$，使 ${\displaystyle A=\{x|\mathbb{N}\models <!--\; \models \; -->\mathrm{\varphi <!--\; \varphi \; -->}(x)\}}$，则称 ${\displaystyle \mathrm{\varphi <!--\; \varphi \; -->}}$ 定义 ${\displaystyle A}$。）

若集合 ${\displaystyle A}$ 可以用图灵机（或任何等价的计算模型）计算得出，则称 ${\displaystyle A}$ 为 ${\displaystyle {\mathrm{\Delta <!--\; \Delta \; -->}}_0}$ 集合。若 ${\displaystyle A}$ 为递归可枚举集合则称 ${\displaystyle A}$ 为 ${\displaystyle {\mathrm{\Sigma <!--\; \Sigma \; -->}}_1^0}$ 集合，若 ${\displaystyle A}$ 的补集 ${\displaystyle \mathbb{N}\mathrm{\setminus <!--\; \setminus \; -->}A}$ 递归可枚举则称 ${\displaystyle A}$ 为 ${\displaystyle {\mathrm{\Pi <!--\; \Pi \; -->}}_1^0}$ 集合。这一定义实际上与上面给出的定义是等价的。

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