算术层级的 Post 定理

一段有限机器运行可以由自然数编码，并由有界计算检查。普通 c.e. 条件“存在一个接受阶段”因此是 ${\mathrm{\Sigma }}_1^0$。若机器查询 $0^{\prime }$，每个肯定 oracle 答案又带一个存在停机见证，每个否定答案则要求排除所有停机阶段；把整段有限运行的 oracle 一致性移到前束形，恰多出一轮交替。每增加一次 jump，正好支付一层无界量词。

反方向从公式出发。对 $\mathrm{\exists }\overrightarrow{u},\psi$，机器枚举候选 $\overrightarrow{u}$；若 $\psi$ 的真值可由较低 jump 决定，就能在找到真见证时接受。全称首块通过取补处理。于是量词块不是被一次性“算完”，而是由相应层的 oracle 负责决定内层问题，外层保留一边的无界搜索。

$\mathrm{\Delta }$ 刻画来自两边同时可相对枚举。若 $A$ 和补集都有 $0^{(n)}$-识别器，交错运行便得到总判定器；若 $A$ 已可由该 oracle 判定，分别在答案为真、假时接受即可枚举两边。这是相对版本的“c.e. 与 co-c.e. 交集等于可计算”。

取 $n=0$，预言机 $0^{(0)}=\varnothing$ 不提供信息。定理退化为

停机集 $K$ 是第一行的标准完全例：有限运行历史给 ${\mathrm{\Sigma }}_1^0$ 上界，对任意 c.e. 集 $W_e$，把“输入 $x$ 的识别器何时接受”有效编译成一个停机实例，得到 $W_e{\le }_{m}K$。

取 $n=1$，$A\in {\mathrm{\Delta }}_2^0$ 当且仅当 $A{\le }_T{0}^{\prime }$。例如 $K$ 自己在 ${\mathrm{\Delta }}_2^0$，而总性索引集 $\mathrm{TOT}$ 是 ${\mathrm{\Pi }}_2^0$-complete，因而不在 ${\mathrm{\Delta }}_2^0$；否则 $\mathrm{TOT}$ 也属于 ${\mathrm{\Sigma }}_2^0$，其 ${\mathrm{\Pi }}_2^0$-完备性就会导致第二层塌缩。${\mathrm{\Sigma }}_2^0$ 的有限性索引集 $\mathrm{FIN}$ 可由 $0^{\prime }$ 相对枚举：猜一个界，再用 $0^{\prime }$ 检查是否还会枚举出更大元素。

完备性结论不能误读为每个 ${\mathrm{\Sigma }}_n^0$ 集都与 $0^{(n)}$ Turing 等价。可计算集合也因加入无用量词属于所有更高 $\mathrm{\Sigma }$ 层，却仍只有 degree $\mathbf{0}$；只有 complete 集达到该层的统一最大难度。定理也不涉及资源上界，不能据其形式相似就把 ${\mathrm{\Sigma }}_n^0$ 与多项式层级的 ${\mathrm{\Sigma }}_n^P$ 等同。最后，jump 的具体编码需固定可接受编号；不同标准编码保持 degree 和有效完备性，却未必字面相等。

Post 定理把严格性化为可核查的 jump 不等式。对每个 $n\ge 1$，$0^{(n)}$ 是 ${\mathrm{\Sigma }}_n^0$-complete，却不在 ${\mathrm{\Delta }}_n^0$：否则第三行会给出 $0^{(n)}{\le }_T{0}^{(n-1)}$，直接违背跳跃定理。因此 ${\mathrm{\Sigma }}_n^0\ne {\mathrm{\Pi }}_n^0$。进一步，${\mathrm{\Sigma }}_n^0\cup {\mathrm{\Pi }}_n^0\subseteq {\mathrm{\Delta }}_{n+1}^0$，而 $0^{(n+1)}\notin {\mathrm{\Delta }}_{n+1}^0$，所以相邻层也确有新集合。严格性不是“量词看起来更多”的句法印象，而是 jump 不能由原 oracle 计算的语义事实。

它也把索引集分类变成系统流程。先把性质写成量词正常形得到上界，再从对应的 $0^{(n)}$ 或其补集构造 many-one 归约得到下界；若只需 degree 上界，则直接设计 $0^{(n-1)}$-预言机判定器。停机、全性、有限性、等价性等程序性质由此落在不同层，而 Rice 定理给出的笼统不可判定性被细分成可核查的完整度。

Shoenfield 极限定理是 ${\mathrm{\Delta }}_2^0$ 行的动态版本：$A{\le }_T{0}^{\prime }$ 当且仅当 ${\chi }_A$ 有可计算稳定近似。把两条定理合用，可在公式、oracle 程序与阶段构造之间往返。二者在这一层相接，但分工不同：Post 定理刻画整条算术层级，极限定理则刻画一次 jump 以下对象的动态逼近。