算术层级

层级记录的是证据与反证据轮流出现的深度。$\mathrm{\exists }u,R(x,u)$ 只需找到一个有限见证；$\mathrm{\forall }u\mathrm{\exists }v,R(x,u,v)$ 则要求面对任意挑战 $u$ 都能给出回应 $v$。每次从存在换到全称或反过来，验证者与反驳者的角色交换一次，无法被一个单边无界搜索简单消去。

量词数不是唯一指标：连续十个存在量词仍是一个块，可以用配对函数压成一个见证；有界量词也能由有限搜索吸收到可判定矩阵。真正计数的是无界量词块的交替。公式被加上无用量词后会落入更高类，所以一个集合“属于 ${\mathrm{\Sigma }}_n^0$”只给上界；要说它恰在第 $n$ 层，还需证明不属于更低类或给出相应完备性。

层级把语法复杂性与计算复杂性连接起来，却不度量运行时间。一个可判定关系即使极慢仍位于基层；相反，${\mathrm{\Sigma }}_1^0$ 的存在搜索可能永远等不到非成员的证据。它也不同于多项式层级：后者限制有限输入上的多项式时间和多项式长度见证，而这里的量词遍历全部自然数，允许绝对不可判定集合出现。

令 $T(e,x,s)$ 表示“第 $e$ 个程序在输入 $x$ 上于 $s$ 步内停机”。有限模拟使 $T$ 可判定。借助可接受编号公理库程序编号与可接受编号Program indexing · Acceptable numbering · Gödel numbering对部分可计算函数进行有效枚举，并要求编号支持通用解释与有效参数编译。，对角停机集满足

所以 $K\in {\mathrm{\Sigma }}_1^0$。其补集由 $\mathrm{\forall }s\mathrm{\neg }T(e,e,s)$ 定义，属于 ${\mathrm{\Pi }}_1^0$。若 $K$ 同时属于 ${\mathrm{\Pi }}_1^0$，两边的搜索可交错成判定器，与停机不可判定性矛盾；这给出第一层已经不塌缩的具体分离。

总函数索引集

属于 ${\mathrm{\Pi }}_2^0$，而且是 ${\mathrm{\Pi }}_2^0$-complete。这里“每个输入最终停机”不能用一个共同步数 $s$ 替代；量词次序若误写成 $\mathrm{\exists }s\mathrm{\forall }x$，只会描述在统一步数内对所有无限输入停机这种过强、实际上不可能由普通有限程序满足的性质。

边界方面，${\mathrm{\Delta }}_n^0$ 是集合同时拥有两种定义，不通常称某个单一字符串“既以存在又以全称开头”。完整一阶算术真句集合也不在任何有限层；对每个固定 $n$ 的受限真理可算术定义，不意味着把所有 $n$ 合并后仍停留在某个固定层。任意集合参数会把 lightface 层级相对化或推向 boldface 语境，不能悄悄塞进矩阵 $R$。

${\mathrm{\Sigma }}_n^0$ 与 ${\mathrm{\Pi }}_n^0$ 各自对有限并、有限交封闭，并在取补时互换；${\mathrm{\Delta }}_n^0$ 对补、有限并交封闭。加入一个无用的外层量词块可得层间包含，而 Post 定理和迭代跳跃给出严格分离：对每个 $n\ge 1$，$0^{(n)}$ 是 ${\mathrm{\Sigma }}_n^0$-complete，故有限层级不会在某一层永久塌缩。

第一层有直接机器含义：${\mathrm{\Sigma }}_1^0$ 恰是 c.e. 集，${\mathrm{\Pi }}_1^0$ 恰是 co-c.e. 集，${\mathrm{\Delta }}_1^0$ 恰是可计算集。更高层通过相对枚举延续同一模式：${\mathrm{\Sigma }}_{n+1}^0$ 是相对于 $0^{(n)}$ c.e. 的集合，${\mathrm{\Delta }}_{n+1}^0$ 是可由 $0^{(n)}$ 决定的集合。这样，公式交替不是纯语法计数，而有统一的 oracle 操作解释。

算术层级还用于精确说明程序性质的不可判定程度。停机是 ${\mathrm{\Sigma }}_1^0$，全性是 ${\mathrm{\Pi }}_2^0$，c.e. 集的有限性是 ${\mathrm{\Sigma }}_2^0$；Rice 定理只给一般不可判定性，层级则继续区分哪一边可相对搜索、需要多少跳跃。做归约证明时，以对应层的完全集为源问题，可以同时得到不可判定性和层级下界。