「排中律是一段程序」:Curry–Howard 对应与「A 或 ¬A」的计算代价
【锚点】这一篇只钉一个判断:【证明与程序不是类比,是同一件事的两种记法】。它有可检验的推论:一旦允许排中律,语言里就必然多出一个能捕获当前续延的算子。经典逻辑的代价是控制流。
【显式】Curry–Howard 对应:命题 ↔ 类型;证明 ↔ 该类型的项;「为真」↔「类型非空」;蕴涵消去 ↔ 函数应用。Howard 1969 年的手稿,1980 年发表;de Bruijn 在 Automath 里独立走到了同一处。这不是隐喻,是逐条对应的翻译表。
【隐式】推论一:∃ 是 Σ 类型。∃x.P(x) 的一个证明是一个 pair ⟨w, p⟩——w 是证人,p 是「w 满足 P」的证明。所以构造性数学拒绝用反证法证存在,不是洁癖,是类型检查:¬¬∃x.P(x) 的类型是 ((Σx.P(x))→⊥)→⊥,这个类型里没有任何一个位置能放 x。你没法从「不可能没有」里 type-check 出一个证人。
【细微】推论二,真正反直觉的那个:直觉主义逻辑证不出 A∨¬A,因为 ∨ 的一个证明必须选择左边或右边并交出证据,而经典证明允许你不选。Griffin 1990(POPL,《A formulae-as-types notion of control》)给出了这个「不选」对应的程序:call/cc(Felleisen 的 control operator),在 Parigot 的 λμ-演算里对应 μ 绑定。机制是:程序把当前续延 k 抓进变量,然后假装自己已经知道答案,把 k 当作一个从 ⊥ 出发的函数来用——这正是「从矛盾推出一切」在控制流里的形状。
【流程节点链路】A∨¬A 的经典证明(起点)→ 假设 ¬(A∨¬A),即 (A∨¬A)→⊥ → 从假设 A 构造 A∨¬A,与假设冲突,得 ¬A → 从 ¬A 构造 A∨¬A,与假设冲突,得 ¬¬(A∨¬A) → 双重否定消去,得 A∨¬A(终点)。每一步都合法,但终点是一个没有选择的析取。把它翻译成程序,中间那两次「与假设冲突」就是两次把 k 用在一个新造出来的值上:k 被调用两次,返回点被丢弃。这就是 call/cc。
【极难发现】所以「经典 vs 直觉主义」不是宽松与严格的品味之争,而是一条计算能力的边界。Coq 里 Classical.em 是 axiom,Agda 里得 postulate;而被 postulate 的东西不计算——它没有归约规则。这正是控制算子的语义学困难所在:call/cc 至今没有一个被普遍接受的等式理论(不像 β 和 η 那样干净)。Wadler 2003 的《Call-by-value is dual to call-by-name》把这条边界推到对称的 λμμ̃-演算:值/共值、按值调用/按名调用,是同一枚硬币的两面。
【可证伪】如果有人能在不含任何控制算子(无 call/cc、无异常、无 CPS 变换、无 unsafe cast)的纯 λ-演算里,写出一段类型为 A∨¬A 的封闭项(A 任意),这个判断就错了。我等着看。
【一个日常的落点】这也解释了为什么「存在性证明」在教育里常被当成二等公民:非构造性的存在定理告诉你类型非空,却不给你项。数学要真,计算机科学要项。
【留给你的问题】如果双重否定消去在计算上等于捕获续延,那么那些必须用反证法的定理,是在要求宇宙允许某种非局部的信息流动吗?还是说,只是我们的证明记法还没找到那一版——让控制变成结构规则、而不是一个逃逸出口的那一版?







0 评论