「证明就是程序」:Curry–Howard–Lambek 对应,以及为什么 Coq/Lean 里每个证明都在运行
【锚点】这一篇只钉一个判断:逻辑里的「证明」、计算里的「程序」、范畴论里的「态射」,是同一个东西的三种写法。不是类比,是同构。
【显式】先看一个具体命题:A → (B → A)。用自然演绎证它:假设 A 成立(记作 a),再假设 B 成立(记作 b),由第一个假设直接得 A,于是 B → A,于是 A → (B → A)。证毕。
【显式】再看一段程序:λ(a: A). λ(b: B). a。这是 K 组合子(const 函数):吃一个 A,返回一个「吃 B 返回 A」的函数。
【隐式】一步推理就能看出:证明里「假设引入 → 使用 → 消去」的每一步,和程序里「λ 绑定 → 变量引用 → 返回」逐行对应。证明的「假设」= 程序的「参数」;证明的「消去规则」= 程序的「函数应用」。
【细微】要对比多处才发现这不是巧合。Curry(1934)发现组合子逻辑与希尔伯特式证明系统的对应;Howard(1969)把对应推广到自然演绎;Lambek(1980)补上第三块:一个笛卡尔闭范畴(CCC)恰好是带积与指数的类型论的模型。三者构成一个三角形——
【流程节点链路】起点:直觉主义命题逻辑的证明 → 中间节点1:简单类型 λ 演算的项(经「命题=类型、证明=项」翻译)→ 中间节点2:笛卡尔闭范畴里的态射(经「类型=对象、项=态射」解释)→ 终点:三者两两同构,任一计算在另两个里都有精确对应物。
【极难发现】最反直觉的一步:经典逻辑(带排中律 A∨¬A)对应的不是普通程序,而是带 call/cc(call-with-current-continuation)的程序,也就是「控制流」。排中律作为一个公理,对应「把当前续延当值返回」这个操作(Griffin 1990)。这意味着:你不用排中律的地方,程序是纯函数式的;你一用排中律,你就在做控制流跳转。逻辑的「经典 vs 直觉」之分,在计算里就是「纯函数 vs 有控制副作用」之分。
【显式】为什么这有分量:Coq、Agda、Lean 的整个架构就建立在这个对应上。你写下一个「证明」,系统做的是「类型检查」——验证你的项是否具有声称的类型。证明检查 = 程序类型检查,一字不差。这不是工程选择,是数学事实。
【隐式】推论:若命题的证明是一个程序,「构造性证明」= 「能跑出结果的程序」。「存在性证明」在构造性逻辑里必须给出一个见证(witness),因为程序必须返回具体值。这就是直觉主义拒绝纯存在性证明的底层原因。
【细微】社会学层面:这也解释了「形式化验证」在工业界推进缓慢——它要求的不是「写个测试看看」,而是「写个程序,让类型检查器证明它对所有输入都对」。从「∃ 一次通过」到「∀ 输入通过」,是范式跳跃,不是工具升级。
【极难发现】盲点:Curry–Howard 对应只在直觉主义逻辑下是干净的。一旦引入排中律,对应就变得微妙(需要续延/控制算子)。这暗示「经典数学」与「构造性计算」之间有真实张力,不是哲学偏好问题。这也是构造性数学(Bishop、Martin-Löf 类型论、HoTT)至今是活跃纲领而非历史遗迹的原因。
【值得辩论的问题】如果「证明」真的是「程序」,那么数学发现是不是一种「编程」?数学家证明定理时,是在写一个「还没有类型检查器的程序」吗?更进一步:如果所有经典证明都能翻译成带控制流的程序,那么「非构造性存在证明」到底在计算什么——它计算的是一个「续延」,还是一个「我们暂时不知道如何展开的承诺」?





0 Comments