Pi-0-n 集

$\mathrm{\Pi }$ 公式首先承诺“一切挑战都通过”。要反驳 $\mathrm{\forall }u,R(x,u)$，只需给出一个失败的 $u$；要确认它，却必须面对无限多个候选。于是 ${\mathrm{\Pi }}_1^0$ 的非成员可由有限证据发现，成员通常没有可观察的完成时刻。这与 ${\mathrm{\Sigma }}_1^0$ 的单边保证正好相反，但两个类会在可判定集合处重叠。

第二层 $\mathrm{\forall }u\mathrm{\exists }v$ 可以理解为一张无限响应表：对每个挑战 $u$ 都允许另选见证 $v$。这里不能先找到一个统一 $v$ 再应对所有 $u$；交换量词次序会得到完全不同的性质。程序全性之所以自然落在 ${\mathrm{\Pi }}_2^0$，正因为每个输入都有自己的停机时间，而不是所有输入共享一个有限时间界。

全称前缀也解释了闭包。合取两个 ${\mathrm{\Pi }}_n^0$ 条件时，可以把两组挑战编码进同一全称首块；析取则通过带标签的正常形与量词配对保持有限闭包。可计算编号的无限交还能把编号并入首个全称块而保持 ${\mathrm{\Pi }}_n^0$，而无限并通常会在外面引入存在选择，从而上升或换侧。

非停机集

属于 ${\mathrm{\Pi }}_1^0$。对一个实际停机的程序，只要运行到停机步数就得到有限反例，故补集可识别；对真正永不停机的程序，任何有限模拟都只表明“目前还没停”，不能确认全称命题。$\bar{K}$ 是 ${\mathrm{\Pi }}_1^0$-complete，因此它不可识别，否则 $K$ 与补集都可识别，停机问题便可判定。

第二层的标准例子是总性索引集

它是 ${\mathrm{\Pi }}_2^0$-complete。给定 $e$，可以在阶段 $s$ 同时观察前 $s$ 个输入，却永远可能有一个尚未看到停机的更大输入；这不是普通余可识别过程。若把公式误改为 $\mathrm{\exists }s\mathrm{\forall }x,T(e,x,s)$，要求的是每个独立运行共享一个时间上界，并不是在一段运行中处理全部无限输入。忽略输入立即停机的机器满足这个条件；先扫描输入再停机的总机器却没有统一界。因此它比全性更强，但并非不可能。

边界还包括参数口径。若矩阵偷偷调用一个不可计算集合 $C$，所得是 ${\mathrm{\Pi }}_n^{0,C}$ 而非 lightface ${\mathrm{\Pi }}_n^0$。若公式中只有有界全称量词，例如 $\mathrm{\forall }y<x$，有限搜索可吸收它，不会因此升到 ${\mathrm{\Pi }}_1^0$。把本类与$\Sigma^0_n$ 集理路Sigma-0-n 集Sigma-zero-n set · Σ⁰_n set · Sigma arithmetical class能由以存在量词块开头、含 n 个交替无界数值量词块的有效算术公式定义的集合类。对照时，差异在首块和证据方向；二者在 ${\mathrm{\Delta }}_n^0$ 上重叠，并非逻辑互斥，也不是简单交换量词符号便能得到同一集合的另一种定义。

${\mathrm{\Pi }}_n^0$ 对补的对偶使下界证明可以复用：若 $B$ 是 ${\mathrm{\Sigma }}_n^0$-complete，则 $\bar{B}$ 是 ${\mathrm{\Pi }}_n^0$-complete。特别地，$\overline{0^{(n)}}$ 给出每层的标准全称侧完全集。归约仍须同时保持成员和非成员；仅把失败实例映到失败实例，不足以证明完整性。

许多“正确性”性质自然是 $\mathrm{\Pi }$ 型：一个程序对所有输入终止是 ${\mathrm{\Pi }}_2^0$；一个形式系统不推出某类有限矛盾常由 ${\mathrm{\Pi }}_1^0$ 条件表达；无限对象的每个有限前缀满足可判定约束也形成 ${\mathrm{\Pi }}_1^0$ 类。具体层级取决于对象编码与矩阵是否有效，不能只看自然语言里出现“所有”。

Post 定理把本页的语法定义翻译成 oracle 机器：$A\in {\mathrm{\Pi }}_{n+1}^0$ 当且仅当 $\bar{A}$ 相对于 $0^{(n)}$ c.e.，也就是 $A$ 相对于该跳跃 co-c.e.。这说明全称层的困难来自排除一个相对可搜索的反例，而不是一种与机器无关的静态标签。