数学里的构造主义与直觉主义（一）

¬(p∧¬p)

翻开数学史的书籍，构造主义仿佛是二十世纪初期的一股叛逆思潮。它曾经很酷，但是却缺乏主流数学家的关注，甚至遭到批判。本文试图梳理一下构造主义的脉络，始于构造主义，终于 univalence axiom (i.e. homotopy type theory).

§-1. 构造主义和直觉主义

用过分简单的话讲，构造主义的核心就是 “要证明一个东西存在，必须把它构造出来”。这直接否定了人们熟悉的反证法。把反证法拿走，后果有多严重呢？

从某些层面上讲，它并没有人们想象的那么严重——只要澄清了一些概念并且做一些仔细地重新叙述，有些用反证法证明的命题其实并不需要反证法：比如欧几里得仔细选取的对 “素数有无穷个” 这个命题的陈述，本质上说的是

任意一个有限集合到素数的集合都存在一个单射。

完全避开了 “无穷” 的概念这一蹚浑水。（从欧几里得对平面几何第五公理的谨慎态度也可以理解，他绝对不会用 “素数有无穷个” 这种描述。）

“√2是无理数” 这个命题，也可以转化为

对任意的自然数m，n，我们有m²＞2n²或者m²＜2n².

并且可以构造性地证明（证明比一般的用反证法证明稍微冗长些）。

在另一些层面上，构造主义带来的困难则大得多——构造主义的一支，布劳威尔（L. E. J. Brouwer）的直觉主义直接要求 "there exists" 被解读为 'there can be constructed', 也就是说 'we can compute'. 这直接导致了了以下的 “神逻辑”:

(★)对于数列(αₙ)，即使 “∀n，αₙ＝0（对任意的n，αₙ＝0）” 这一命题不成立，我们也不能得出∃n，αₙ ≠ 0（“存在” n使得αₙ ≠ 0）

因为——虽然在非直觉主义的意义下有这么一个n，但是这个n并不是被构造出来的。没有 “算法” 告诉你怎么计算出这个n.

§0. 如何解读神逻辑

要理解这个神逻辑，不能拘泥于 “存在” 这两个字在自然语言中的字面意思，而是把 “∃” 这个量词 (quantifier) 看做一个纯粹的符号，再接受布劳威尔对这个词的解读——换句话讲建构在直觉主义上的数学和逻辑，其实是我们熟悉的那套东西的一个兄弟，只是 “∃” 这个基因发生了一点变异。

由于 “∃” 的变异，直觉主义的数学发展相比迟缓。因为，(★)直接否定了数学中一个常用的逻辑命题——排中律！排中律的陈述很简单：

对于任意的命题P，P∨¬P成立。（也就是说，P或非P总有一个成立。）

加上量词的版本更能体现排中律和(★)的不可调和之处——加上量词的排中律是这样的：

¬(∀x. Px) ⇒ ∃x.(¬Px).

用直觉主义的方式来阐释 “∃”, 显然无法接受排中律——即使我们否定了 “对任意的x，都有Px” 这一命题，我们也不能算出一个使得Px不成立的x.

把排中律抽走，对直觉主义的数学影响有多大呢？很大：

（注意：这里原文有误，已修改）由 Diaconescu's theorem 排中律是选择公理的推论，抽走排中律，选择公理也不能成立，这就抽走了很多现代数学里最重要的引理，动摇了很多比较现代的理论的基石——

1. 分析上，没有排中律，不能得出∀x∈ℝ，(x＝0)∨(|x|＞0)（即使知道x＝0不成立也不能推出的x绝对值大于0.）类似地，也没有中值定理。

2. 代数上，没有选择公理，甚至不能证明任意一个环的存在极大理想！

这种限制对于很多数学家而言是万万不能接受的。实际上，没有排中律的话，甚至不能说一个实数要么是有理数，要么是无理数！（提示，设(αₙ)是一个取值在{0，1}中的递减数列，

∞ αₙ

考虑∑ ─的有理性和前面的神逻辑(★)的关系）ₙ₌₁ n！

§1. 一个有趣的观点

实际上，高中或者大学的某些数学之所以对一部分人困难，就是因为我们就放弃了构造主义！

首先，高中的数学和初中是很不一样的——并不是说初中研究了线性函数和二次函数，高中就研究三次四次函数，大学再研究五次六次函数。回头看来，两者最大的区别是，用的数学基础发生了重大变化——初中的数学，无所谓基础，所有的研究对象都是实数轴上的一次或者二次函数，所有的函数都可以在计算器上摁出来，其实在学生脑子里默默建构了构造主义的习惯。而高中开始，数学就慢慢地建立在集合论的基础上了。

集合论带来的，是非构造性。两个集合之间的映射，定义起来并不平凡：

给定集合X，Y他们之间的一个映射是一个关系，对于任意的x ∈ X，有唯一的f(x) ∈ Y，这个关系记作 f：X → Y.

换句话讲，f：X → Y对应的是Ⅹ × Y的一个满足如下条件的子集R

∀x ∈ X，∃！y ∈ Y，(存在唯一的 y ∈ Y)使得 (x，y) ∈ R.

真正理解这个定义的人，难免 痛恨 “一个映射/函数就是一个公式” 的常见误解（鄙人就曾经是痛恨者中的一员）。回过头来看，这种误解其实代表着构造主义和集合论的冲突。按照集合论的定义，实数轴上的实值函数，其实是ℝ × ℝ的一类的子集，对每个x∈ℝ “分配” 了一个值y∈ℝ——有没有让人窥见选择公理的影子？大多数这样的函数，都是 “不可计算” 的。

就是这一点点非构造主义，以奇怪的形式把很多人绊倒在构造在集合论基础上的现代数学的门槛上。门槛本身在哪里并不重要——可能在集合论，也可能在数学分析，或者实变函数论，但归根结底都是那一点点非构造主义。

类似的例子还有抽象代数。很多人在初次学习的时候本能地拒绝 “一个群是一个集合加上一个满足某些条件的二元运算” 这样的抽象定义，但是能接受矩阵群的概念，本质上也是非构造主义在作祟。用面向对象编程的语言来说，矩阵和一个抽象的集合的元素的区别在于，矩阵群自带元素的 constructor 和 methods. 但是用抽象的集合给出的群，就好像只带着 virtual methods 的 object, 会被一些人脑子里的编译器拒绝。

§2. 集合论与计算机，一个小故事

实际上，集合论以及上述的非构造主义，不光把一部分学生拦在了现代数学的门槛之外，还拦住了一个重要的角色——计算机。

这个 “拦住” 是实质性的：不是说囿于计算性能的门槛，计算机虽说可以理解集合论，但无法用于实际用途。而是由于某些原因，多数数学家接受的作为数学基础的 ZFC 集合论，实在无法让计算机接受。

实际上，在集合论的框架下，多数数学家也没办法从纯粹集合论的角度思考数学——比如实数的概念，只有在最严格的分析中才视作有理数的柯西序列的等价类，平时脑子里想象的都是实数轴上的点。数学基础和实践的这种巨大差异，才是计算机的最大绊脚石。

就算有办法把以 ZFC 集合论为基础的内容硬塞给计算机，其实还有下面这种风险：假设某一天计算机利用强大的计算能力，用纯粹的逻辑找到了黎曼猜想的证明，但人类仔细阅读计算机给出的证明的时候，发现在关键的一步，计算机说

因为0∈2，所以...

等等，0∈2 是什么鬼？！计算机辩解道，根据定义，万物都是集合，首先有空集∅，然后通过 0＝∅，1＝{0}，2＝{0，1}，. . . 来定义自然数ℕ嘛。人类数学家急了，这只是自然数的集合论模型之一啊！0∈2 这种依赖于模型的东西，怎么能用来证明这么重要的定理呢？这时候，另一台计算机，用另一个自然数的集合论模型，也找到了一个黎曼猜想的证明，但是这台计算机里，自然数的模型ℕ₁是通过0＝{∅}，1＝{0}，2＝{1}，. . .来定义的。而在证明的关键一步，它用到了 0∈1，1∈2... 我们甚至没法比较两台计算机给出的证明是否相同。

在人类看来，两个自然数的模型的选取，本来是无关紧要的东西，不管怎么说，任意两个模型都是同构的嘛。对重要命题的证明不应该依赖于模型的选取，这就好像对一个关于整数的结论的证明不应该依赖于整数的十进制表示一样显然。同构的话，对一个成立的命题，可以通过同构 “搬” 到另一个上，但显然，“可以搬动的性质” 并不包括0∈2这种奇怪的东西——这又是一个没法跟计算机解释的怪现象。

§3. 从集合论到类型论 (type theory)

花开两朵，各表一枝。七十年代末，瑞典人 Martin-Löf 做出了一个重要的发现，即 algorithmic mathematics, 也就是计算机科学, 等价于只用直觉主义逻辑的数学。在 Martin-Löf 发展的构造性类型理论 (constructive type theory) 中，有以下的对应关系

第一个公式：

Programming

Program，procedure，algorithm input

output，result

⋮

α：·A

⋮

record s1：T1；s2：T2 end .

⋮

第二个公式：

Mathematics function argument value

⋮

α∈A

⋮

T1 × T2

⋮

熟悉集合论的读者应该能注意到上述表格的第一行的不寻常之处——在 Martin-Löf type theory 中，一个 “函数” 就是一个 “公式”！（只不过这个公式可以稍微复杂一点，写成一段代码或者算法而已。）这套观点完全丢弃了原来对函数的定义，X → Y的函数不再是Ⅹ × Y的一个特殊子集，而是从一个类型X的输入到一个类型Y的输出的一个计算的步骤(procedure) !

实际上，尽管离学术界广泛接受还有一定距离，type theory 其实很有适用于数学基础的潜力，并且是一个从诞生之初就适合计算机理解的数学基础。

在类型论中，“集合” 的概念被 “类型” (type) 取代，自然数、整数、有理数，都有对应的类型。乍一看这和集合论 “万物都是集合” 没啥不同，只是把 “放在一起的一堆东西” 的名字从集合 (set) 改成了类型 (type), 并且把记号α ∈ A 改成了α：A. 实际上，两者差了十万八千里——在集合论中，我们可以构造一个集合α， 和另一个集合A（两者都是从空集∅出发，用 ZFC 集合论允许的运算进行构造得到的结果，比如{∅，0，1，3} × {1，2}），再讨论

α ∈ A是否成立？

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。