有趣的数学游戏(39页).doc

《有趣的数学游戏(39页).doc》由会员分享，可在线阅读，更多相关《有趣的数学游戏(39页).doc（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-有趣的数学游戏-第 39 页实数、超实数和博弈游戏：数学的结构之美（一）一个博弈游戏让我们来玩一个游戏。下面有五行石子，白色的石子都是我的，黑色的石子都是你的。我们轮流拿走一个自己的石子，并且规定如果一个石子被拿走了，它后面的所有石子都要被扔掉。谁先没有拿的了，谁就输了。比如说，如果你先走的话，你可以把第四行的第三个石子拿走，按规定第四行将会只剩下前面两个石子：现在轮到我走了。我可以拿走第二行倒数第二个石子，于是整个棋局变成了这样：现在，假如说你拿走了第二行中的第一个石子（于是第二行就没了），那么我就赢定了。我可以拿走第一行中的第一个石子，从而让整个棋局只剩下后面三行：这三行中有四个白石子，

2、有三个黑石子，并且每一行都是同种石子。于是整个局面完全变成了一个拼石子个数的游戏，我只需要一个一个地拿走白色石子，你必然将会率先无路可走。受此启发，我们自然地想到了一种刻画棋局的方式：把每个白色石子记作 +1 ，把每个黑色石子记作 -1 。于是 + + = 4 2 1 = 1 ，结果是一个正数，这就表明该局面下我将必胜，即使此时轮到我先走。你会发现上面的说法很有道理。毕竟白色的石子越多，对我越有利，给我带来的效用为正；而黑色的石子会减小我获胜的希望，当然应该给它赋上一个负的值。四白三黑算出来的结果为正 1 ，直观意义就是我能以一步的优势获胜。如果棋局是这样：那么 + = 2 4 = -2 ，是

3、一个负数，这就意味着不管谁先走，你都能必胜，因为你能比我多走两步。我们不妨把一个棋局对应的数叫做棋局的“特征值”。特征值为正，就表明不管谁先走我都能必胜；特征值为负，就表明不管谁先走你都能必胜；而特征值的绝对值，则直观地量化了胜负的悬殊。现在，考虑下面这个棋局：那么 + = 2 2 = 0 ，这表明此时的情形介于“我必胜”和“你必胜”之间。事实上也是这样如果我先走你后走，你就赢定了；如果你先走我后走，我就赢定了。这是因为，这个棋局的特征值为 0 ，双方能够走的步数相同，当然谁后走谁就赢定了。真正有趣的事情出现了。考虑下面的棋局：它的特征值应该是多少呢？容易看出，它的特征值是一个正数，因为不管谁

4、先走，显然我都能赢。同时，它的特征值也应该比 1 小，因为只有一个 要比 赢得更爽一些。事实上，单看 黑方确实无论如何都会输，但在某些场合下， 后面的这个 能让黑方喘上一口气。比如下面这个棋局：如果我先走，显然你必胜无疑。如果你先走呢？先走的人获胜的难度更大，你可要好好想想策略。你可以拿走那个单独成行的 ，但当我拿走 之后，你就得眼睁睁地看着自己剩下的那个 被一并收走。此时，你或许会意识到，你本来还能多走一步的，可惜这一步被浪费掉了。因此，你更好的做法就是，一上来先拿走 后面的 。运用这种策略，显然你也会必胜无疑。可见，不管是我先走还是你先走，整个棋局对于你来说都是必胜的，从而有 + = 1

5、0 ，这再次说明了 是一个小于 1 的数。那么， 是否等于 1/2 呢？ 答案是肯定的，考虑下面这个棋局：如果我先走，本质上不同的走法只有一种，并且局面将会立即变成刚才那种你必胜的情形，因而你将必胜。如果是你先走呢？拿走那个单独成行的 会让你提前锁定败局，更好的选择则是像刚才一样，先拿走某个 后面的 ，为自己多赢得一步。现在，石子只剩下了 、 、 这么三行。那么，我应该拿走哪一个 呢？拿走那个单独成行的 会让局面再次变回刚才那种你必胜的情形，更好的选择则是拿走后面有 的 ，这样我便能让你损失一步。掌握了这个技巧后，我就能做到必胜了。综上所述，整个棋局是一个谁后走谁就赢定了的局面。于是 + +

6、= 0，也就是 + 1 = 0 ，可以解得 等于 1/2 。也就是说，在 中，我将以半步的优势获胜。对应地， 就等于 -1/2 ，此时你将以半步的优势获胜。注意，目前并没有任何理论告诉我们，这么加减是合理的。不过我们却发现，这么加减出来的结果真的是对的。比如说， + + + = 1/2 + 1/2 + 1/2 1 = 1/2，而棋局对于我来说真的就是必胜的局面！这背后一定有一个更深层次的原因：棋局之间的加减和数与数之间的加减一定存在着某些共通的地方。也就是说，为了解释“为什么棋局的加法和数的加法如此之像”，我们需要证明，两者具有完全相同的代数结构。我们需要建立一个从棋局到实数的映射法则，然后说

7、明全体棋局（或者全体棋局的一部分）与全体实数（或者全体实数的一部分）是同构的。正如 Poincar 所说，诗歌的艺术在于给相同的东西取不同的名字，数学的艺术在于给不同的东西取相同的名字。两个看似毫不相关的东西竟然是同构的，这在数学中是最令人激动的事情之一。（二）熟悉而又陌生的算术为了说明棋局就是算术，我们首先要定义，什么是算术。我们需要站在系统之外，对算术的本质做一个描述。算术，就是对一些数做加减乘除的运算。这似乎对我们完全没有帮助什么是数，什么是加减乘除？其实，数，就是一些具有大小关系的元素，这些元素可以按照它们的大小关系串成一根链条。这意味着，首先，任意两个数都是可以比较大小的，并且对于两

8、个不同的数 x 和 y 来说， x 要么大于 y ，要么小于 y 。然后，大小关系必须具有传递性，如果 x 小于 y ， y 又小于 z ，那么 x 一定小于 z 。形式化地说，我们要求元素之间存在某种暂且记作 的关系，使得它们满足：1. 完全性：对于任意的 x 和 y ，x y 和 y x 当中至少有一个成立。2. 反对称性：对于任意的 x 和 y ，如果 x y 和 y x 同时成立，那么 x 和 y 一定是同一个元素。（今后我们用符号 x = y 表示 x 和 y 是同一个元素，注意这个新符号和 的区别：前者是一个真实的符号，它用来表达“是同一个元素”这个概念；后者则是我们假想的一种抽象

9、符号，它不见得有什么具体的意义。）3. 传递性：对于任意的 x 、 y 和 z ，如果 x y 和 y z 同时成立，那么一定有 x z。这样的话，所有的元素都被 穿成了一条绳子。我们就说，这些元素构成了一个“全序关系”。我们还需要元素之间的“加法”和“乘法”满足一系列的性质：1. 对加法封闭：对于任意的 x 和 y ， x + y 也仍然是某一个元素2. 对乘法封闭：对于任意的 x 和 y ， x y 也仍然是某一个元素3. 加法交换律：对于任意的 x 和 y ， x + y = y + x4. 乘法交换律：对于任意的 x 和 y ， x y = y x5. 加法结合律：对于任意的 x 、

10、y 和 z ， (x + y) + z = x + (y + z)6. 乘法结合律：对于任意的 x 、 y 和 z ， (x y) z = x (y z)7. 乘法对加法的分配律：对于任意的 x 、 y 和 z ， x (y + z) = x y + x z8. 存在加法单位：存在某一个特殊的元素，通常记作 0 ，使得对于任意的 x ，都有 x + 0 = x9. 存在乘法单位：存在某一个特殊的元素，通常记作 1 ，使得对于任意的 x ，都有 x 1 = x10. 存在加法逆元：对于任意的 x ，总能找到某一个特殊的元素，通常记作 -x ，使得 x + (-x) = 011. 存在乘法逆元：对

11、于任意不为 0 的 x ，总能找到某一个特殊的元素，通常记作 x-1，使得 x x-1= 112. 对于任意的 x 、 y 和 z ，如果 x y ，那么一定有 x + z y + z13. 对于任意的 x 、 y ，如果 0 x 和 0 y 同时成立，那么一定有 0 x y有几点需要注意。我们虽然只说了加法单位满足 x + 0 等于 x ，但其实由于加法交换律， 0 + x 也等于 x 。乘法单位也是如此。我们说“存在加法单位”，而没说“存在唯一的加法单位”，这是因为加法单位最多只能有一个，如果存在，必定唯一。假如 a 和 b 是两个加法单位的话，你会发现因为 a 是加法单位，所以 a +

12、b 等于 b ，又因为 b 是加法单位，所以 a + b 等于 a ，因而 a = b 。我们说“存在加法逆元”，而没说“存在唯一的加法逆元”，也是因为同一个元素的加法逆元最多只能有一个，如果存在，必定唯一。假设 a 有两个加法逆元 b 和 c ，那么就有 b = b + 0 = b + (a + c) = (b + a) + c = 0 + c = c ，因此 b 其实就是 c 。乘法单位和乘法逆元也是如此。这基本上刻画出了作为一个算术系统所有需要满足的性质。第 4 条和第 5 条告诉了我们，加法和乘法并没有那么玄妙，它们不过是从元素对到元素的映射。第 6 条到第 10 条列举了加法和乘法的

13、基本性质。第 11 条和第 12 条定义了 0 和 1 这两个特殊的数。第 13 条中出现了“加法逆元”一词，不过“相反数”一词或许会更亲切一些。第 14 条中出现了“乘法逆元”一词，不过“倒数”一词或许也会更亲切一些。第 13 条和第 14 条实际上定义了减法和除法。减去 x ，就相当于加上 -x ；除以 x ，就相当于乘以 x-1。这两条性质保证了，我们可以自由地做减法，我们可以自由地做除法，得到的数也仍然是一个合法的元素，不会出现不够减、不允许减、不够除、不允许除的情况（除以 0 除外）。因为，每一个元素都有相反数，每一个非 0 元素都有倒数。等等，这些性质就能刻画算术系统了？似乎漏掉了

14、不少其他关键的性质吧。比如， 0 乘以任何数都等于 0 ，这条性质哪儿去了？其实，剩下的没有写出的性质，包括 (-1) x = -x 、 0 1 、 0 x x 等等，都是已有性质的推论。我们可以从已有性质出发，完全不关心它们的实际意义，抽象地证明出算术系统应该具有的其他性质。例如，为了证明 0 x = 0 ，只需要注意到：0 x = (0 + 0) x = 0 x + 0 x两边同时加上 0 x 的加法逆元，等式仍然成立（这是因为，如果 a = b ，那么加法运算将会把 a + c 和 b + c 映射到同一个数）：0 x + (- 0 x) = (0 x + 0 x) + (- 0 x)0

15、 = 0 x + (0 x + (- 0 x)0 = 0 x + 00 = 0 x同时满足第 4 条到第 14 条的话，这些元素就构成了一个“域”。如果还满足第 15 条和第 16 条（当然还有第 1 条到第 3 条），这就是一个“有序域”。最小的有序域是有理数域。如果把上面所说的元素想成是全体有理数，把小于等于、加法和乘法解读为我们平常所说的小于等于、加法和乘法，那么整个系统满足上面所有 16 条性质。实数域则是一个更“大”的有序域，而有理数域只是它的其中一个“子有序域”。当然，还有一些有序域，它里面的元素根本不是常规意义上的数，它们之间的大小关系、加法乘法也根本不是常规意义上的大小关系和加

16、法乘法。不过，人们已经证明了，任何一个有序域里一定都包含有一个子有序域，它和有理数域同构它里面的一切都和有理数一样，只是各个元素的名字不一样罢了。也就是说，在任何一个有序域中，我们都可以从加法单位和乘法单位出发，把全部的或者部分的、本来有可能并不是数的元素看成是一个个的数，得到一个与有理数等价的系统：加法单位就是 0 ，乘法单位就是 1 ，等于 1 + 1 的那个元素就是 2 ， 等于 2 + 1 的那个元素就是 3 ， 2 的加法逆元就是 -2 ， 2 的乘法逆元就是 1/2 ，等等，而且这些元素确实是不同的元素，它们之间的小于等于、加法乘法的运算结果也确实符合有理数之间的运算结果。正因为这

17、样，我们才说，这 16 个有序域条件比较完整地描述了算术系统的要素，足以刻画算术系统了。这里，我们突然有了一个非常激动人心的问题：一个有序域有没有可能比实数域更大（实数域只和它的某个子有序域同构）？有理数域已经封闭了，但加进去一系列新的元素之后，我们有可能得到一个封闭的、更大的实数域；那么，能否在实数域里面也加进去一些新的元素，让实数域进一步扩张成某个更大的有序域？不不不，答案没有“复数域”那么简单复数域不是有序域，因为它不是有序的。也就是说，我们无法为所有复数安排 关系，使得它能满足有序域的全部条件。在这个比实数域更大的有序域中，我们不但能继续加减乘除，还要能继续做大小比较，每一个新的数和每

18、一个原有的实数之间都有一个确定的大小关系。直观上，这似乎是不大可能的，因为实数已经把那根“线”填满了。（三）外星人的数学对算术结构的形式化，让我想起了一些更折磨人的哲学问题：我们的数学体系为什么是这样的？一个文明的数学体系一定是这个样子的吗？比方说，如果人类没有视觉这种感官，我们还会创立几何这门学科吗？同时，人类是否会因为缺乏某种独特的感官，而没能建立起一个更加神奇的数学分支？同样地，我们总会认为，自然数是最自然的概念，是每一种文明都不可避免会遇到的概念。是这样吗？会不会有某一种外星文明，他们也有一套自己的算术系统，虽然也有加减，虽然也有乘除，虽然跟我们正在使用的算术系统是同构的，但其直观意义

19、和表示方法都跟我们完全不同。或许，在我们这里很难表达的数，在他们那里看来几乎是平凡的；或许，在我们这里很直观很自然的数，在他们的体系里却需要异常复杂的记号来表示。作为一个科幻迷，我甚至马上想到了，这应该是一个绝佳的科幻素材：数学家发现了地外生命的某种全新的数学系统，并且一步一步尝试去解读它。为此，数学家们必须抛弃任何已有的假设，忘掉什么是自然数，什么是零，什么是加减，什么是乘除，从一片空白开始，尝试理解外星算术系统，逐渐搭建起外星数学的大厦。你一生的故事的数学版，多么激动人心的一件事情啊！这样的小说已经有了。你猜谁写的？ Donald Knuth ！第一次听说这个时，第一反应除了膜拜还是膜拜：

20、 Knuth 简直是太牛了，他竟然写过一本小说！这本 100 多页的小说叫做 Surreal Numbers （中译研究之美，电子工业出版社 2012 年 1 月出版，顺便吐槽中译名），中文意思大致就是“超现实的数”。我打算直接把它叫做“超实数”正如“实数”就是“现实的数”一样，“超实数”也就是“超现实的数”了（其实，不得不说的是，“超实数”这个译名有一个很大的弊端：它可能会与另一个叫做 hyperreal numbers 的概念发生混淆）。小说的副标题则是 How Two Ex-Students Turned on to Pure Mathematics and Found Total Ha

21、ppiness 。小说讲述了 Alice 和 Bill ，一对年轻男女，逃到一个漂亮的孤岛上“寻找自我”。他们在岛上发现了一块古老的石板，石板上用希伯来语写着一些数学公理。然后，我们将跟随 Alice 和 Bill 的思路，逐渐探索这些公理的意义，期间会走不少的弯路，历经一些失败的尝试，到最后终于成功恢复出了一个完整的算术系统。根据 Wikipedia 的描述，一个全新的数学概念竟然首先出自于一本小说，这是极罕见的例子。在下面的讨论中，时刻记住：我们在学习外星数学。我们不能有任何先入为主的概念。请忘记“数”的概念，忘记“小于等于”的概念。下面所说的“数”是某种全新的物体，它可能与我们熟知的数有

22、某种对应的关系，也可能与我们熟知的数没有任何关系。“小于等于”也是一种全新的概念，这四个字整个儿是一个新词，它不是由“小于”和“等于”合成的。它的意思有可能和我们的小于等于相吻合，也有可能和我们的小于等于不吻合，甚至有可能根本就没有什么合理的“意思”。“大于等于”只是一个与“小于等于”对称的说法。如果 x 小于等于 y ，我们就说 y 大于等于 x 。偶尔我们会用 代替“小于等于”，用 代替“大于等于”，不过也请假装这些符号对你来说是完全陌生的。石板上的公理只有两个。1. 每个数都是用两个（由已有的数构成的）集合表示的，其中左边集合里不存在这样的数，它大于等于右边集合里的某个数。假如 a 、

23、b 、 c 、 d 、 e 都是已经构造出来的数，并且从 a 、 b 里任取一个数，从 c 、 d 、 e 里任取一个数，前者都不会大于等于后者，那么把 a 、 b 放入左边的集合，把 c 、 d 、 e 放入右边的集合，我们就能得到一个新的数，比如 f 。我们把它记作 f = a, b | c, d, e 。2. 一个数小于等于另一个数，当且仅当前者的左集合里不存在大于等于后者的数，并且后者的右集合里不存在小于等于前者的数。比如，如果 x = a, b | c ， y = d | e ，那么 x 小于等于 y ，当且仅当 a 、 b 都不大于等于 y ，并且 e 不小于等于 x 。可以看出，

24、所有的数，包括它们之间的 、 关系，都是递归地表达出来的。不过，我们每次都需要用已有的数来定义新的数，那我们从什么地方开始呢？答案是，我们从空集开始。左集合和右集合都为空，记作 | ，这是我们能够得到的第一个数。再次提醒，这个数或许能被等价地理解为我们世界中的某个数，或许不能。我们暂时不做这些假设。我们把这个数记作 。也就是说， = | 。容易看出， ，因为 的左集合里确实没有哪个数大于等于 ，并且 的右集合里确实没有哪个数小于等于 （事实上 的左集合里和右集合里根本就没有数）。既然 ，反过来看，也可以说成是 了。在接下来的过程中时刻记住， 既小于等于自己，又大于等于自己。接下来，我们可以构造

25、两个新的数 | 和 | ，不妨把它们俩分别叫做 和 。注意， | 是不合法的，它违反了公理 1 ：左集合里的数不能大于等于右集合里的数。可以验证， ，而 。另外， 也是小于等于 的，不过请注意，这并不是根据“小于等于”的传递性推出的，而是根据“小于等于”的定义直接验证的。我们还不知道“小于等于”满足传递性。事实上，我们还不知道“小于等于”有什么直观意义。x 小于等于 y 当且仅当 x 的左集合里不存在大于等于 y 的数，并且 y 的右集合里不存在小于等于 x 的数 = | ， = | 小于等于 ，或者说 大于等于 = | ， = | 小于等于 ， 或者说 大于等于 = | ， = | 小于等于

26、 ， 或者说 大于等于 接下来，我们完全不理会 背后有何直观意义，而是纯粹利用刚才的两个公理来证明，刚才看到的传递现象其实并不是巧合。换句话说，在这个神秘的算术系统中，如果 x y ，并且 y z ，那么 x z 。证明的基本方法是数学归纳法。我们对三元组 (x, y, z) 施加归纳。假设传递性对于更早产生的三元组都是成立的。根据定义，如果 x y ，那么对于 x 的左集合中的任意一个元素 xL来说， y xL都不成立。这立即表明， z xL是绝对不可能发生的，因为我们已经有了 y z ，如果还有 z xL的话，根据归纳假设，就会有 y xL，矛盾。于是我们知道了， x 的左集合里不存在大于

27、等于 z 的元素。用类似的方法可以推出，不可能出现 zR x 的情况，其中 zR是 z 的右集合中的任意一个元素。理由和刚才相仿：如果 x y 和 zR x 同时成立，由归纳假设就会得到 zR y ，这与 y z 相矛盾。于是我们知道了， z 的右集合里不可能出现小于等于 x 的数。综合上述两条便有 x z 。由于超实数所具有的递归本质，在研究超实数的性质时，最基本的方法就是数学归纳法。为了证明某个结论对任意一个数 x 都成立，我们通常会假设这个结论对所有可能的 xL和 xR都已经成立了；类似地，为了证明某个结论对任意一个二元组 (x, y) 都成立，我们通常会假设这个结论对所有可能的 (xL

28、, y) 、 (xR, y) 、 (x, yL) 、 (x, yR) 都已经成立了。让我们来做几个练习吧。首先，让我们试着用数学归纳法来证明，对于任意一个数 x 都有：1. x xL，其中 xL是 x 的左集合中的任意一个元素2. x xR，其中 xR是 x 的右集合中的任意一个元素3. x x证明过程并不复杂。假设这几条性质对于更早产生的数都成立。为了证明对于任意 xL都有 x xL，我们只需要说明，在 x 的左集合中存在一个大于等于这个 xL的数即可。这样的数是显然存在的，因为由归纳假设， xL xL或者说 xL xL始终成立。证明对于任意 xR都有 x xR的方法也是类似的。好了，既然

29、xL都不大于等于 x ，并且 xR都不小于等于 x ，就说明 x x 了。我们不妨把这三个结论分别叫做补充性质 1 、补充性质 2 和补充性质 3 。我们今后会反复用到这三个补充性质。有人或许会说：x xL，岂不意味着 x xL吗？为什么要说得那么麻烦呢？别急，别急，我们目前还不知道 x y 能否推出 x y 呢。不过，不管怎么说， x xL还真是成立的。我们可以证明这一点，基本思路仍然是数学归纳法。为了证明对于任意 xL都有 x xL，我们只需要说明，这个 xL的左集合里不存在大于等于 x 的数，并且 x 的右集合里不存在小于等于这个 xL的数。根据公理 1 的规定，后者显然是成立的。前者的

30、正确性则不太容易看出来：根据归纳假设，这个 xL大于等于它的左集合里的所有元素，如果这个 xL的左集合里存在大于等于 x 的数，由传递性便可推出 xL x ，与刚才的补充性质 1 矛盾。类似地，补充性质 2 也有一个推论，即对于任意 xR都有 x xR。证明方法几乎完全相同： x xR的意思就是 x 的左集合里不存在大于等于 xR的数，并且 xR的右集合里不存在小于等于 x 的数，两者可以分别由公理 1 和归纳假设推出。补充性质 1 和补充性质 2 拥有这样的推论，这使我们开始猜测：会不会在任何情况下，由 x y 都能推出 x y 呢？的确是这样，而且证明过程很简单。 x y 意味着某个 xL

31、大于等于 y ，或者某个 yR小于等于 x 。如果有某个 xL大于等于 y ，但刚才我们证明了 x 大于等于一切 xL，两者结合便有了 x y ；如果有某个 yR小于等于 x ，但刚才我们证明了 y 小于等于一切 yR，两者结合也能推出 x y 。所以，不管是哪种情况， x y 都是成立的。或许有人会无比兴奋地说：这个结论太有用了，之前很多别扭的说法这下都能大大简化了。例如，公理 1 原本说的是，一个数是合法的，当且仅当它的左集合里的每一个数都不大于等于右集合里的每一个数。现在，我们是不是就能把它重新叙述为，一个数是合法的，当且仅当它的左集合里的每一个数都小于等于右集合里的每一个数？且慢！我们

32、目前只知道 x y 可以推出 x y ，但并不知道 x y 能否反过来推出 x y ，因而也就不知道 x y 和 x y 是否是完全等价的说法。对已有的数进行试验，你会觉得 x y 似乎真的能够推出 x y 。之前我们验证过 、 和 ，你会心安地发现，它们反过来真的都不成立。x 小于等于 y 当且仅当 x 的左集合里不存在大于等于 y 的数，并且 y 的右集合里不存在小于等于 x 的数 = | ， = | 不小于等于 ，或者说 不大于等于 = | ， = | 不小于等于 ，或者说 不大于等于 = | ， = | 不小于等于 ，或者说 不大于等于 但是，如果再多生成一些数，问题就出来了。考虑这个

33、数 | ，由于 确实不大于等于 ，因此这个数是合法的。把这个数叫做 。现在，考虑 和 的大小关系：x 小于等于 y 当且仅当 x 的左集合里不存在大于等于 y 的数，并且 y 的右集合里不存在小于等于 x 的数 = | ， = | 小于等于 ，或者说 大于等于 = | ， = | 小于等于 ，或者说 大于等于 结果， 和 同时成立。这说明，虽然 x y 可以推出 x y ，但是 x y 不能推出 x y ，两者并不是等价的。换言之， x y 和 y x 不可能都不成立，但却有可能同时成立。现在，让我们来回顾一下“小于等于”这个关系所满足的性质。它满足传递性，即 x y 和 y z 可以推出 x

34、 z 。它满足完全性，即 x y 和 y x 至少有一个成立。但是，它不满足反对称性。反对称性的意思是，如果 x y 并且 y x ，那么 x 和 y 必然是同一个元素。然而，我们刚才已经看到了， = | 和 = | 互相之间都具有 关系，但它们并不是同一个元素。我们刚才反复强调，这里的“小于等于”是一个全新的概念，不要把它想象成我们熟知的那个小于等于；现在看来，这是一个无比正确的决定这里的“小于等于”就是不能看成是我们熟知的那个小于等于。这里的“小于等于”不满足反对称性，但我们熟知的那个小于等于却得满足这一点。先别管它。我们继续。在 Knuth 的小说中， Alice 和 Bill 又发现了

35、一块新的石板，石板上定义了一种叫做“加法”的二元运算，用符号 + 表示。也请暂时不要和大家熟知的加法联系在一起。定义 x + y 的结果是一个新的数：它的左集合是由 x 的左集合的所有元素分别加 y ，以及 x 分别加上 y 的左集合的所有元素构成的；它的右集合是由 x 的右集合的所有元素分别加 y ，以及 x 分别加上 y 的右集合的所有元素构成的。如果把 x 的左集合和右集合分别记作 L(x) 和 R(x) ，把 y 的左集合和右集合分别记作 L(y) 和 R(y) ，那么 x + y 的左集合 L 和右集合 R 分别是L = u + y | u L(x) x + v | v L(y) R

36、 = u + y | u R(x) x + v | v R(y) 例如，若 x = a, b | c ， y = d, e, f | g, h ，那么 x + y 就是 a + y, b + y, x + d, x + e, x + f | c + y, x + g, x + h 。显然，加法也是递归地定义出来的。在研究加法所具备的性质之前，我们必须要先做一件事情：证明如此加出来的数一定是满足公理 1 的，换句话说加出来的一定都是合法的数。这个证明是很有必要的，它直接关系到加法运算的封闭性。然而，这件事情却很容易被人忽略。 Knuth 的书中有一段情节我非常喜欢，讲的就是 Alice 和 Bi

37、ll 突然意识到自己忘了做这件事情。在第 12 章灾难的开头， Alice 说：“一小时前我醒来，发现我们昨天的证明有一个很大很大的漏洞，就是我们忘了证明 x + y 是一个数了。”听了这话之后， Bill 说：“开玩笑吧，这是两个数之和，当然是一个数咯！等等，我想想哦，我们还要检查它是否满足公理 1 。”接下来的 11 页则都是 Alice 和 Bill 对这个问题的探究，可见证明这件事还真不容易。这里，我们略去证明。这么定义加法，效果如何呢？还是用我们刚才的那些数来做试验： = | 、 = | 、 = | 。容易看出： + = ， + = | + = | = ， + = + | = | =

38、 。利用数学归纳法不难证明，事实上， 加上任意一个数 x 都仍然等于 x 。如果 x = a, b | c ，那么 + x 就等于 + a, + b | + c ，根据归纳假设，这就是 a, b | c 。根据同样的道理，任意一个数 x 加上 也都仍然等于 x 。如果 x = a, b | c ，那么 x + 就等于 a + , b + | c + ，根据归纳假设，这就是 a, b | c 。也就是说，假如我们这里所说的“加法”真的符合我们现实意义中的加法的话， = | 其实就应该是那个 0 ！在我们给出 + x = x 始终成立的结论后，立即又说 x + = x 也是始终成立的，这并不是废话

39、，因为我们并不知道这里的加法是否满足交换律。那么，这里的加法是否满足交换律呢？让我们试着比较一下 + 和 + 的结果，来做一番探究吧。由于任何数加上 都不变，并且 加上任何数也都不变，因而： + = | + | = + | + = | = + = | + | = + | + = | = 这样看来，这里的加法似乎是满足交换律的。再次利用数学归纳法，我们可以很快得出，这里的加法就是满足交换律的。若 x = a, b | c ， y = d, e, f | g, h ，那么 x + y 就是 a + y, b + y, x + d, x + e, x + f | c + y, x + g, x +

40、h ，而 y + x 就是 d + x, e + x, f + x, y + a, y + b | g + x, h + x, y + c ，根据归纳假设，两个数内部的组成元素是完全一致的。同样是利用数学归纳法，我们还可以得出，这里的加法也是满足结合律的。 (x + y) + z 的左集合，归根结底是由以下三类数组成： (xL+ y) + z 、 (x + yL) + z 、 (x + y) + zL。而 x + (y + z) 的左集合，则是由以下三类数组成： xL+ (y + z) 、 x + (yL+ z) 、 x + (y + zL) 。根据归纳假设，你会发现， (x + y) + z

41、 的左集合和 x + (y + z) 的左集合本质上是一样的。类似地， (x + y) + z 的右集合和 x + (y + z) 的右集合本质上也是一样的，因而 (x + y) + z = x + (y + z) 始终成立。这里的加法还满足有序域条件列表中的第 15 条，即 x y 可推出 x + z y + z 。事实上，我们会证明一个更强的结论： x y 当且仅当 x + z y + z ，两者互相之间都是可推导的。事实上，我们会证明一组比这还要强的结论：1. 若 x y ，并且 z w ，则 x + z y + w2. 若 x + z y + w ，但是 z w ，则 x y就像之前证

42、明那三个补充性质一样，我们会把这两个结论捆绑到一块儿，共同施加数学归纳法。首先，我们来证明结论 1 ，即已知 x y 和 z w 可推出 x + z y + w 。根据加法的定义， x + z 的左集合由所有可能的 xL+ z 和 x + zL组成， y + w 的右集合由所有可能的 yR+ w 和 y + wR组成。别忘了，一个数小于等于另一个数，当且仅当前者的左集合里不存在大于等于后者的数，并且后者的右集合里不存在小于等于前者的数。因此，如果 x + z y + w 不成立，这就意味着 xL+ z y + w 、 x + zL y + w 、 yR+ w x + z 、 y + wR x

43、+ z 这四种情况当中至少会有一种出现。结果你会发现，这四个式子中的任何一个式子都会引出矛盾。例如，在第一个式子当中， xL+ z y + w ，但我们有 z w ，根据结论 2 的归纳假设便有 xL y 。但是我们还有 y x ，由传递性便得到 xL x ，这与之前的补充性质 1 矛盾。类似地，从后面三个式子出发，可以分别得出 zL z 、 yR y 和 wR w ，这都与之补充性质相矛盾。接下来，让我们看看结论 2 ，即已知 x + z y + w 和 z w 可推出 x y 。如果 x y 不成立，这就意味着 xL y 和 yR x 这两种情况当中至少会有一种出现。结果你会发现，这两个式

44、子中的任何一个式子都会引出矛盾。例如，在第一个式子当中， xL y ，但我们有 z w ，根据结论 1 的归纳假设便有 xL+ z y + w ，这与已知的 x + z y + w 矛盾。类似地，从第二个式子出发，可以得出 yR+ w x + z ，这也与已知的 x + z y + w 矛盾。让我们来回顾一下，这里定义的加法和我们熟知的那个加法究竟有多少差距。这里定义的加法满足加法交换律、加法结合律。这里定义的加法还满足 x y x + z y + z 。这里定义的加法甚至存在加法单位。我们刚刚引入加法时就发现了， = | 就是加法单位，任何数加上它的结果都不变。不过，我们目前还不知道的是，是

45、否每个元素都存在加法逆元？换句话说，是否对于每一个数，我们都能找出一个相应的数，使得两者相加等于那个加法单位？结果你会发现，这是根本不可能的。除非两个加数都是 ，否则根据加法的定义，两数之和的左右集合不可能都是空的，自然也就不可能等于加法单位 了。此时，又该轮到谜一般的石板登场了。 Alice 和 Bill 发现，石板上还写有 x 的“逆元”的定义。递归地定义 x 的“逆元”为，将 x 的左右集合颠倒，并把集合里的每个数都变为“逆元”所得的新数。如果把 x 的左右集合分别记作 L(x) 和 R(x) ，把 x 的“逆元”记作 -x ，那么 -x 的左右集合就应该是：L = -u | u R(x) R = -u | u L(x) 因此，如果 x = a, b | c ，那么 -x 就等于 -c | -a, -b 。可以证明，一个合法的数的“逆元”一定是满足公理 1 的，换句话说，一个合法的数的“逆元”一定也是合法的数。这里略去证明。容易看出， 的“