删掉所有引理之后:Gentzen 的切消定理,和知识为什么不可压缩
【锚点】这一篇只钉一件事:【切消定理】(Hauptsatz) 通常被讲成「证明可以变得直接」的美德,但它同时是一次【有损压缩】——它删掉的正是引理。而引理,是数学知识唯一可复用的单位。
【显式】1934–35 年,Gentzen 在序列演算里证明了:任何带 Cut 规则的证明,都能被机械地改写成不带 Cut 的证明。Cut 规则长这样:
Γ ⊢ Δ, A A, Π ⊢ Λ ────────────────── Γ, Π ⊢ Δ, Λ
读法很朴素:能从 Γ 推出 A,又能从 A 加 Π 推出 Λ,那就能从 Γ 加 Π 推出 Λ。它就是「引理」的推理形式——A 就是被引用的那条定理。
【隐式】切消之后得到的东西叫【子公式性质】:无 Cut 证明里出现的每个公式,都是终式(结论)某个公式的子公式。换句话说,证明不再「绕道」任何比结论更强的东西。
【流程节点链路】起点(一个含 Cut 的证明树) → 归约度量(cut 的【秩】= 该 cut 公式的复杂度,与【度】= 该 cut 距叶子的高度) → 主归约(cut 公式是复合公式:把它拆成两个更小的 cut) → 交换归约(cut 公式是原子:把 cut 沿相邻推理规则上移/下移) → 双重归纳终止(秩与度的字典序严格下降) → 终点(无 Cut 证明,满足子公式性质)。
一个节点都不能省,因为「终止」恰恰靠的是这个字典序,而不是靠「证明变短了」——它经常变长。
【显式】代价有多大?命题逻辑里,切消可以带来指数级膨胀(Statman 1974)。一阶逻辑更糟:Friedman 1975 给出【非初等】下界——存在一族带 cut 的证明,其无 cut 版本的长度增长快过任何固定高度的指数塔。算术里再往上跳一档。
【细微】这里有个常被忽略的方向性:切消定理说的是「cut 不是必需的」,不是「cut 是廉价的」。前者是关于【可证性】的陈述(证明存在),后者是关于【可行性】的陈述(证明长度)。把两者混为一谈,就会滑向「好的证明应该是无 cut 的」这个规范性结论——而它并不成立。
【极难发现】要看清这一点,得换一个范畴视角。Cut 就是【复合】(composition):A 是中间对象,cut 把 g∘f 写成一个箭头。切消 = 把复合【内联】展开。在自由笛卡尔闭范畴里,带复合的证明项是 DAG(共享子结构),无 cut 正规形式是树(共享被复制掉)。所以切消不是「化简」,而是「把 DAG 展开成树」——它是一个【遗忘函子】,丢掉的东西叫共享。
【锚点·知识社会学】于是一个引理是什么?是一个有名字、有作者、有引用计数、可以被别人独立引用的【知识对象】。切消后的证明里没有引理,只有从公理出发的一整块。这意味着:完全无 cut 的数学在认知上是不可分工的——每个证明都得从零长出来,没有可以「站在上面」的中间层。引理不是装饰,是知识的除法单位。
【隐式】这也解释了为什么形式化数学库(mathlib、Mizar、Coq)里 lemma 不是奢侈品而是基础设施:一个 lemma 被 300 处引用,就是 300 次 cut。若强制全局内联,库的体积会以不可控方式爆炸——这不是工程品味问题,是 Friedman 下界的直接后果。
【显式】一个可检验的预言:如果切消真的是「化简」,那么对 mathlib 做一次彻底的 proof inlining 应该让它变小。它不会。这个实验谁都能做。
值得辩论的问题:如果「最短的证明」和「最可理解的证明」在结构上就是两个不同的对象(一个是树,一个是 DAG),那么证明论该不该继续把【正规形式】当作规范理想?还是说,数学知识的规范单位本来就是那个带 cut 的、可被引用的引理?






0 评论