Sigma-0-n 集

$\mathrm{\Sigma }$ 的存在首块表示证明成员资格时先交出一个候选证据。第一个全称块会质询这份证据在所有挑战下是否成立，下一存在块又允许针对挑战作回应。随着块交替，成员资格从一次无界搜索变成有限轮、但每轮都遍历自然数的证据博弈。

这一视角解释了为什么 ${\mathrm{\Sigma }}_1^0$ 有普通半判定器：只需并行尝试见证，某个见证成功便停止。到 ${\mathrm{\Sigma }}_2^0$ 的 $\mathrm{\exists }u\mathrm{\forall }v$，找到候选 $u$ 后仍无法在有限时刻确认没有反例 $v$；必须借一次停机预言机判断反例搜索是否永远失败。更高层依次增加 oracle jump。

“属于 ${\mathrm{\Sigma }}_n^0$”不是说书写时第一个字符恰为 $\mathrm{\exists }$。公式可以重排、加入无用量词或采用不同算术编码；分类看是否存在等价正常形。也不能把每个量词都算一次交替，例如 $\mathrm{\exists }u\mathrm{\exists }v$ 仍只有一个存在块。

对角停机集 $K$ 有正常形

其中 $T$ 是有限步运行谓词，故 $K\in {\mathrm{\Sigma }}_1^0$。机器直接模拟 $e$ 在自身上的运行，一旦停机就接受；非成员上永不结束。这是 ${\mathrm{\Sigma }}_1^0$ 与 c.e. 的操作对应，而不是把“存在”仅当作符号标签。

令 $\mathrm{FIN}=\{e:W_e\text{ 有限}\}$。用阶段枚举 $W_{e,s}$ 可写成

把 $x,s$ 合成一个全称块可见 $\mathrm{FIN}\in {\mathrm{\Sigma }}_2^0$；它实际上 ${\mathrm{\Sigma }}_2^0$-complete。候选界 $b$ 是第一块证据，后续所有阶段都必须证实再无大元素出现。有限观察永远可能被下一阶段的新元素推翻，说明它通常不在 ${\mathrm{\Sigma }}_1^0$。

${\mathrm{\Sigma }}_n^0$ 与$\Pi^0_n$ 集公理库Pi-0-n 集Pi-zero-n set · Π⁰_n set · Pi arithmetical class能由以全称量词块开头、含 n 个交替无界数值量词块的有效算术公式定义的集合类。不是互斥类别：同时属于两者的集合正是 ${\mathrm{\Delta }}_n^0$。取补会把 ${\mathrm{\Sigma }}_n^0$ 精确送到 ${\mathrm{\Pi }}_n^0$，却不会把一个给定集合“自动留在原类”。有限并、有限交仍在 ${\mathrm{\Sigma }}_n^0$ 内；对一个统一 ${\mathrm{\Sigma }}_n^0$ 家族再作可计算编号的并，可把编号并入首个存在块而保持层级，但同样的无限交通常会改变首块与层数。

每层都有标准完全问题。$0^{(n)}$ 在合适的统一编号下对 ${\mathrm{\Sigma }}_n^0$ many-one 完全：任何本层集合都能通过总可计算映射把其量词—计算条件编译成一个第 $n$ 跳停机实例。完全性给出的不仅是不可判定，还证明该集合无法落入更低层，除非整个层级发生矛盾性的塌缩。

相对化保留正常形：在矩阵中加入 oracle 谓词 $C(t)$，得到 ${\mathrm{\Sigma }}_n^{0,C}$。Post 定理说明 ${\mathrm{\Sigma }}_{n+1}^{0,C}$ 恰是相对于 $C^{(n)}$ c.e.；因此处理带背景数据库、理论或已有不可计算信息的搜索时，只需把基准从 $0$ 换成 $C$，不改变交替结构。

实际分类程序索引集时，先把性质写成阶段量词通常最稳妥：出现一次有限计算可用存在阶段，要求所有输入成功引入全称输入，再为每个输入选择停机阶段。随后要另做下界归约；只展示一个 ${\mathrm{\Sigma }}_n^0$ 公式只能证明上界，不能证明这是最小 $n$。