进一步研究《研究之美》

范德蛙
2012-01-21 看过
自 25 页始,讨论向更高的层次进发。其结论的通用性越发上升。第 25 页“如果成立的话,那我就会将 (Y, phi) (此处 phi 表示空集)称为“正”数”,之后又发现此中 Y 必须满足其中至少一个元素大于或相似于 0,只要满足了这个条件,它就成被称为“正”数。

在第 31 页,主人公 Bill 发现了 19 个(后经 Alice 指出是 20 个)基于 -1, 0, 1 产生的超实数。然后,当他们想继续产生后面的超实数时,遇到了一个问题,就是将会产生出很多的(可能超过 400 个)的超实数。由于这样产生的超实数太多了,他们开始寻找简化的途径。首先 Alice 发现了 X(L) 和 X(R) 在小于或相似于(<=)这个运算符下面的意义,可以用 X(L) 中的最“大”的那个数和 X(R) 中最“小”的那个数来代表。

这个什么意思呢,比如对两个超实数 x 和 y,要判断 x <= y 是否成立,从书中 Conway 法则 2(即称为规则 (2),见书中第 7 页)出发,等价于 (not any X(L) >= y) and (not any Y(R) <= x)。通过上述讨论的简化法则,我们只要判断 (not max(X(L)) >= y) and (not min(Y(R)) <= x) 即可。比如,要判断 0 <= 1,and 的左边是真因为 X(L) 是空集,而右边也是真因为 Y(R) 是空集。反之要判断 1 <= 0,and 的左边是假因为 max(X(L)) 就是 0,0 >= 0 成立,这样右边虽然是真,但是整个表达式仍是假。

通过这种简化,前面发现了的 20 个超实数,可以被简化为 10 个“代表”。

接下来,第 33 页到第 37 页,主人公开始怀疑起了此小于并相似于的概念与一般数字的小于等于的概念之间是否并不如想象的那样。而此关系最容易想象的一种情形就是传递性。对于通常实数集的小于等于运算,它有自反性和传递性(对称性也成立,即 x <= y <=> y >= x;它已隐含在 Conway 的定义之中)。自反性是指 x <= x 成立。传递性是指命题“若 x <= y,y <= z,则 x <= z”成立。现在我们要证明的是传递性的成立。

Bill 认为如果直接证明,感觉会比较困难,不如用反证法的思路,即通过假设结论不成立,看看是否会导出矛盾。于是假设 x <= y,y <= z,并且 x > z(此处我用大于号表示小于或相似于的相反情况)。需要让第三个式子成立,就必须有 X(L) 集中的某个 x(L) >= z,或者 Z(R) 集中的某个 z(R) <= x。

然后,这样一来,又得到新的三个坏数组合(两种情况取其中至少一种):y <= z,z <= x(L),但是 y > x(L),或者 z(R) <= x,x <= y,但是 z(R) > y。而且有趣的是,这两种情况又可以递归应用,把两种情况中的三个数算作前面的 x y z 再次应用。

这样一来,反倒解决了问题:由于可以无限递归下去,每次递归又将其中一个数的左集或右集中的数提取出来,而 x y z 三个数都只有有限的复杂度,因此递归到一定程度后,提取出的数的复杂度将降到左集和右集都是空集的程度,也就是 0。再向下递归,只可能将非 0 的两个数继续递归,直到那两个数也依次变 0 为止。而 0 <= 0, 0 <= 0 且 0 <= 0 是肯定成立的,因此与原先的假设矛盾。于是原命题得证。书中第 37 页更明确地指出,抽出的数的创造日——可以表示为第 n 日——一定比它组成的那个数的创造日要靠前,从而递归下去也会得到期待的结论。

第五章,第 41 页。首先两人开始讨论是否有这样的两个数,它们互相“视而不见”,仿佛是在异次元空间似的。说到异次元空间,不知您的体会是什么,反正对我来说,直接就想到了脍炙人口的《圣斗士星矢》。记得有好几次有圣斗士进入了异次元空间。我因为好奇,忍不住看了下英文原文,原来原文只是简单的 in another dimension or something,顿时觉得译者的这个翻译或许真的是从圣斗士里面得到的启发,实在太有意思了。现代社会上流行的宅男宅女,这种分类太抽象,具体地来说,我以前大学里吧,周末经常宅在家里,经常玩电脑,但是却很少上网,一周上个一两次吧。这样一来,可能就跟其他宅的人身处不同的空间了。记得有同事说,我们上网上得太多要戒网,Robbie(我的网名兼英文名)不是要戒网,是要戒电脑。记得大学毕业以后去文广工作,有十天军训每个应届毕业生必须参加。然后在这十天里面没电脑玩,每天难受得紧……到最后一天回到家,感觉终于熬到头了!

好吧,扯远了。前面说到 y !<= x 并且 x !<= y。之所以用 !<= 而不是 > 是为了突出我们要寻找的特性——无关性。如果 x !<= y,则至少有一个 x.L >= y(还记得女主人上次得出过的结论吗?)。

然后,Knuth 教授笔峰一转,妙笔生花,找一个充分非必要条件来加速证明:一个想象已久的命题:x.L <= x(并且 x <= x.R)。如果这个成立,那么根据之前已经推出的传递律,就有 y <= x,之前的 y !<= x 就不成立,异次元的假说也就被推翻了,Conway 的理论由主人公看起来就更接近完美了。

这里还是用反证法,假设 x.L !<= x,那么以下两者必居其一:1. 某个 x.L.L >= x;2. x.L >= 某个 x.R。(Conway 规则 2)。但是,条件 2 与 Conway 的规则 1 相矛盾。于是只有条件 1 可以继续进行下去。

然后,主人公觉得既然猜想 x.L <= x 成立,但是现在要证伪的是 x.L !<= x,为什么不留一些余地,假设 x.L.L <= x.L 呢?但是,光是假设是不行的,需要实际找到这种情况才能继续进行这个证伪。那么实际是否能找到呢?书中 Alice 说了一句话:“由于 x.L 比 x 先创造出来,我们至少可以假设 x.L.L <= x.L,运用归纳法”。这句话中的“运用归纳法”正是画龙点睛之笔!那天晚上我走在瑞金二路上边走边想,才终于想明白:归纳法,这里的方向是向“下”的,就是把第 n 日的数往第 k 日(k < n)推。这样一来,对于 x 来说,就算 x.L.L !<= x.L,那么可以把老的 x.L.L 看作新的 x.L,把老的 x.L 看作新的 x,代入原来的 x.L !<= x 的式子,继续推,最后,要么到第 1 日,让 x.L 与 x 的假设关系与 0,1,-1 的情形相矛盾而被证伪,要么必然能找到 x.L.L <= x.L,从而在半路上中止。

如果找到了 x.L.L <= x.L,Alice 还想继续往下推,Bill 马上将其阻止。之后,Alice 却意想不到地得到了另一个结果:由于 x.L.L >= x,以及 x.L.L <= x.L,那么 x <= x.L,于是就是不存在 x.L2 >= x.L(其中包含了 x.L2 就是 x.L 本身的情况;x.L2 是 X.L 中的任意元素),这样就是说,自反性对于 x.L 不成立,即 x.L !<= x.L。还记得吗?第 4 章 Alice 和 Bill 证明了传递性,但却没有证明过自反性哦!

然后 x.L !<= x.L 表示存在 x.L.L >= x.L 或者存在 x.L.R <= x.L。如果 x.L.L >= x.L,前面说的是 x.L.L <= x.L,这两个并不矛盾啊——我那天在这个问题上绕了老半天,后来才发现原来答案就在眼前:前面刚讲过 x <= x.L 所推出的命题就是 x.L !<= x.L,Bill 误以为是又回到了 x <= x.L 的情形,但是 Alice 一针见血地指出:x.L <= x.L.L 已经比 x <= x.L 向下一层了,继续向下推一定能推到第 0 日并给出矛盾。

所以 Bill 的一句“漂亮”给出了一个完满的结局。

剩下的情况就是 x.L.R <= x.L 这个分支(因为用的连词是“或者”),而它与 x.L.L >= x.L 是对称的,因此也能导致矛盾。
17 有用
1 没用
研究之美 研究之美 8.4分

查看更多豆瓣高分好书

评论 7条

查看更多回应(7)

研究之美的更多书评

推荐研究之美的豆列

了解更多图书信息

豆瓣
免费下载 iOS / Android 版客户端