细看《研究之美》(本人书评,原载于豆瓣)

2013年2月9日

在第 5 章接近尾声的地方,两位主人公带着胜利的喜悦,一举推导出了好几个定理。前面所述的定理 T3(此处 T 表示定理 theorem,下同)就是自反性。T2 是 X.L <= x 且 x <= x.R,前面用自反性已证得。再进一步就得到 T4 即两个数不可能在异次元空间。T5 和 T6 是两条加强了的传递律——这两条可以从第 4 章的传递律 T1 和本章的 T4 共同得出。

“Alice,今天我看到了你的另一面。你可真是打破“女性不宜搞数学”的神话了啊。”

“怎么了嘛,谢谢你哟,我的骑士小嘴真甜!”

这个翻译嘛,实在是让人砰然心动……

好,继续,第 6 章。首先,由前一章的研究结果,我们可以把第 3 日的 20 个数里面的 7 个拿出来排列一下。它们分别是:([]|[-1]) < -1 < ([-1]|[0]) < 0 < ([0]|[1]) < 1 < ([1]|[])。注意 1、0 和 -1 只是简写,它们实际还是由两个集合构成的。剩下一些别的数,但是由 Alice 的推导(也包括之前的第 4 章里谈到的,X.L 中最大元素和 X.R 中的最小元素是具代表性的这段话,书中第 31 到 33 页),我们可以得到:([-1]|[]) ([]|[1]) ([-1]|[1]) 这三个具代表性的数。其中 ([-1]|[1]) 经讨论已与 0 相似。

先回头看看 Alice 的推导是怎样进行的:她用到了 x,YL 和 YR 三者,它们之间满足一定的关系(详请见书)。然后得到的结论是 x 与 z 相似(T7)。再回头来看第 4 章,第 4 章那个只是讲了一小半,是说对于两个数 x 和 y,如果 max(y.L) 与 max(x.L) 相似,min(y.R) 与 min(x.R) 相似,那么这两个数相似。并且当时还没有得到证明。而第 6 章这里的结论则明显加强了:对于 x 和 YL、YR,如果 YL < x < YR,则 z = (YL union X.L | YR union X.R) 相似于 x。其中不要求 max(X.L) .=. max(YL) (此处 .=. 表示“相似于”,下同)。那么她是如何证明的呢?首先,要让 z <= x,则必须 1. YL union X.L 中没有一个大于等于 x;2. X.R 中没有一个小于等于 z。对于 1,YL 是可以保证的,X.L 可由 T3(自反性)得出:因为 x <= x,因此 X.L !>= x,即 X.L < x。对于 2,由于 z 的自反性,z <= z 成立,能得到 z.R = YR union X.R !<= z,从而 X.R !<= z。类似地,我们可以对称地证明 x <= z,从而得到 x .=. z。

之后,为了把剩下的数放进去,两位主人公反复应用 T7,发现 ([-1]|[]) 和 ([]|[1]) 都相似于 0。这样一来,就前述 7 个数最具有代表性了。

然后,他们猜想如果前 n 天的数是 x[1], x[2], …, x[m – 1], x[m],那么第 n + 1 天的数就是 ([]|[x[1]]), ([x[1]]|[x[2]]), …, ([x[m – 1]], [x[m]]), ([x[m]]|[])。我们先来看看前 3 天的对不对:第一天 1 个,第二天 2 个(1 + 1 = 2),前二天共 3 个,第三天 4 个(总共 7 个)。的确满足规律。那么如何证明呢?

首先,由第 4 章 Alice 的结论,数的左集和右集都只要选其中的一个代表即可(左集选最大的,右集选最小的)。因此下一天的数只可能是 ([x[i]]|[x[j]])、([]|[x[i]])、([x[i]]|[]) 这三种形式之一,而且由于 Conway 的数的定义规则 1,以及前面的数的顺序关系,i < j 必须成立。因此,他们开始了证明。思路也是反证法。

Bill 首先提出了一种特殊情况,就是 ([x[i-1]]|[x[i+1]])。对于这个数,Alice 会怎么办呢?她发现这个很容易解决:把它和 x[i] 比较吧,由于 X[i].L !>= x[i-1],且 X[i].R !<= x[i+1],根据 T7,把它们加到 ([x[i-1]]|[x[i+1]]) 的左右两边去之后,与这个数是相似的,即 ([x[i-1]] union X[i].L|[x[i+1]] union X[i].R) .=. ([x[i-1]]|[x[i+1]])。然后呢,另一方面,x[i-1] < x < x[i+1]。因此,把 x[i-1] 和 x[i+1] 加到 x 的两边之后的数根据 T7 也相似于 x,而这个数正是前面与 ([x[i-1]]|[x[i+1]]) 相似的那个数,根据传递性,它也相似于 x。

Bill 再次提出了另一种可能性:([x[i-1]]|[x[j+1]]),其中 j > i。这下 Alice 一时给问住了。此时,Bill 却有了想法:在 x[i], x[i+1], …, x[j-1], x[j] 这些数里面,只要找到一个数 xea 它的左集小于等于 x[i-1] 或左集为空,右集大于等于 x[j+1] 或右集为空,即可根据 T7 推出 xea 相似于 ([x[i-1]]|[x[j+1]])(提示:对任意一个数 x,X.L < x 且 x < X.R,这是由 Conway 规则 2 和 T3 推出来的,因此 x[i-1] < ([x[i-1]]|[x[j+1]]) 且 ([x[i-1]]|[x[j+1]]) < x[j+1];然后把 xea.L 和 xea.R 分别附加到 ([x[i-1]]|[x[j+1]]) 之左右集,即可根据 T7 推导)。Bill 发现在 x[i] .. x[j] 之中必有一个数是在最早的日子里产生的,这个数的左集必小于 x[i] 且小于等于 x[i-1],右集必大于 x[j] 且大于等于 x[j+1],因此它就是相似于 ([x[i-1]]|[x[j+1]]) 的那个数,于是 ([x[i-1]]|[x[j+1]]) 也可以被代表掉了。

接下来考虑边缘情况。说到边缘情况,做过编程的人晓得,有时候是比较搞的。对于不做编程的人来说,这是什么概念呢,就是好比你用资源管理器往 U 盘上拷文件,把一个文件夹的文件全都拷过去,U 盘空间不是很够,拷到某一个文件时,空间不够了,报了个错误消息之后就停止了。这时候你要去确认哪个文件是拷贝成功的最后一个文件,以及哪些文件没有被拷。编程里面的边缘情况也是类似,就是遍历一个数组或别的什么有范围的东西时,在边界上如何处理的问题。这里我们书中的边缘情况是这样的:([]|[x[j+1]]) 和 ([x[i-1]]|[])。Bill 觉得这也是小菜一碟,不就是 x[1] .. x[j] 之中最早被创造的数和 x[i] .. x[m] 之中最早被创造的数嘛。前者的左集是空集;后者的右集是空集。

Alice 还担心如果在 x[i] .. x[j] 这样的数中有多个数是“最早创造的”。Bill 想了一想就明白了:这个情况是不可能发生的,因为这样的多个数互相之间将相似,而这与当初我们的假设相矛盾。这个理论能理解,但是乍想有些奇怪,为什么在相邻的一段数里面不可能有两个数是最早创造的呢?如果你有兴趣的话,看一下书中第 81 页的那些数字的诞生模式就明白为什么了——每两个同日诞生的数之间看上去总是存在一个更早日诞生的数,有点类似二叉树的结构。:-P

当 Bill 正为此洋洋自得时,风中忽然传过来一句话:“胡说八道。想想无限集合再说。”——这风太神了,还能传话……这像是打雷一样,很快就下雨了,貌似已经进入了季风时节。猜想这个无限集合在后面的部分会有用,但是现在先放一下吧。

进入了第 7 章后,两位主人公开始寻找 Conway 岩石的余下部分,以求得对 Conway 理论的更多理解。找到之后,两位开始感慨起大学时候的教育问题了。到底是因为当时太不投入了,才导致上课打瞌睡,还是因为老师的原因?如何才能培养出有创造力的学生?这段位于第 67 页到第 71 页的讨论,非常耐人寻味。

第 8 章,两人开始根据岩石上的内容来研究加法。首先,Alice 解读出 Conway 的话的含义:两个数 x 和 y 相加,就是 ((x.L + y) union (y.L + x)|(x.R + y) union (y.R + x))。然后,Bill 着手计算他的第一个加法式子:1 + 1。这是在有了全部第三日数字的基础之上进行的。我们来看看第三日有哪些数字了:-a,-1,-b,0,b,1,a。其中 a 是 ([1]|[]),b 是 ([0]|[1]),等等。

1 + 1 的计算,新的左集是 1 的左集中的每个元素加上 1,新的右集是 1 的右集中的每个元素加上 1。新的右集显然是空集。新的左集是什么呢?1 的左集是 [0],那么新的左集就是 [1 + 0]。进一步计算 1 + 0,它的左集是 [0],右集是空集,那么它就是 1。此前 Conway 岩石上也讲过,任何数加 0,其和还是原来这个数,果不虚言。于是 1 + 1 就是左集为 [1],右集为空集的这个数。它就是 a。

Bill 进一步假定,a 就是 2;Alice 笑称这是最长的 1 + 1 = 2 的证明。不过作为读者的我读到这里倒有个疑问,为什么能把 Conway 的加法和实数的加法相对应呢?万一这个加法有点什么特殊的性质怎么办?且看 Bill 和 Alice 之后的讨论,有没有任何不符合实数加法的现象出现。暂且认为到目前为止,Conway 加法和实数加法是一致的。

Alice 算了个 1 + 2,得到 ([2]|[]),它是第四日的数,Bill 把它叫做 3。那么 b 是几呢?Bill 猜想它是 1/2。如果这种加法与实数加法真的相对应的话,那么自然地,b + b 将会等于 1。看看 b + b 到底等于多少:左集是 [b],右集是 [b + 1]。那么 [b + 1] 又是多少?左集是 [1, b],可以简化为 [1],因为 b < 1 的缘故。右集是 [1 + 1]。也就是说 [b + 1] 就是 [([1]|[2])]。这个数一定大于 1 而小于 2,而 [b] 则是大于 0 而小于 1。在一个大于 0 而小于 1 和一个大于 1 而小于 2 的数之间的那个数是什么?根据前面的那个理论,应该是之间的创造日最早的数,就是 1。所以 b + b 就是 1,那么 b 应该就是 1/2。

第 9 章,Bill 得到的第三天的所有数是:-2,-1,-1/2,0,1/2,1,2。其中 2 是正推的,1/2 是从 0、1 和 2 反推得到的。第四天的所有的非负数是:0,1/4,1/2,3/4,1,3/2,2,3。其中 3/2 可以从它自已加自己,位于 2 以上而得出;3/4 可以从它自己加自己,位于 1 与 2 之间而得出。第五天得到的所有非负数是:0,1/8,1/4,3/8,1/2,5/8,3/4,7/8,1,5/4,3/2,7/4,2,5/2,3,4。但是,Bill 发现这里面的某些数有点“异样”:7/4,它可以和它自己相加,然后是一个位于 3 和 4 之间的数,但是这个数在第五天还不存在。它实际上是 7/2,但需要提前“发现”。

主人公们先是用形式化的语言证明了 T8,就是之前第 8 章已经讲过的一个特性的扩展。有了前面的基础,这个证明应该不难看懂。

Alice 说第 5 日的数“一点不假”——但是是为什么呢?Bill 发现为了计算这些数,必须“预先发现”某些后面日子里才会出现的数,比如 7/4。但是 Bill 对这个模式很有信心。为了证明它,Alice 首先提出了一个设想:第四日所有的正数加了 1 以后的数在第五日里都存在,并且就是第五日最大的那些数。试试看加 1 会怎么样吧。x + 1 = ((X.L + 1) union [x]|X.R + 1)。首先可以说明这些数在新的一日都存在(我现在还不敢说“证明”,因为加法的特性都还没完全被证明出来)。

我是这样想的:假设对第 i 日的 x,要想说明 x + 1 是第 i + 1 日的数。那么假设对第 i – 1 日的数 y,y + 1 是第 i 日的数成立,存在 y.L + 1 >= y,若 Y.R 不为空,存在 y + 1 >= y.R,而 x + 1 = ((X.L + 1) union [x]|X.R + 1),进一步相似于 ([x.L + 1]|[x.R + 1])(因为 x.L + 1 >= x)或相似于 ([x.L + 1]|[]),那么由于 x.L + 1 和 x.R + 1 都是第 i 日的数,它肯定是第 i + 1 日的数。

但是反方向上如果要说明第 i + 1 日里大于 1 的数都是第 i 日里的正数加 1 而得,也就是不存在某个大于 1 的数 x,它不是前一天的正数加 1 的结果。这个我想了好一会儿:从规律看,第 2 日所有正数有 1 个,大于 1 的数有 0 个,第 3 日所有正数 3 个(等于 2 ^ (n – 1) – 1),大于 1 的数 1 个,第 4 日所有正数 7 个,大于 1 的数 3 个(等于 2 ^ (n – 2) – 1),而且第 n + 1 天的大于 1 的数的个数等于第 n 天的正数个数,其余的正数个数是 2 ^ (n – 2),而这个可以通过前面第 6 章讲的每日的不同的数的个数得到:第 n 日有 2 ^ n – 1 个数,包括正数、负数和 0,那么正数必然是 2 ^ (n – 1) – 1 个。这样一来,结论就得到了说明。

回到书上第 91 页,对于小于 1 的数怎么办?很简单,把它们做个自相加,结果必然小于 2,比如 ([x.L]|[x.R]) 这样的数,其中 x.L 和 x.R 是前一天相邻的数,这两者之间的距离也是有规律的,对于第 3 天的小于 1 的 x,这距离是 1,第 4 天是 1/2,而 1 和 2 之间的数,其之间的间距也是有规律的,由于都是前一天 0 和 1 之间的数加 1 而得,因此是前一天 0 到 1 之间的数的间距。因此不难想到,对于 x + x,假设前一天的 0 到 1 之间的间距是 y,x + x 的范围就被限制在 x.L + x.L 和 x.R + x.R 之间了,而这两者之间的间距是 2y,而 1 到 2 之间的数的间距是 y,x.L + x.L 和 x.R + x.R 之间(不含两端)创造日最早的数就是那个位于两者正中间的数,因此小于 1 的数也很容易地能被确定了。

Bill 接下来证明了 x + 0 .=. x。这个证明比较简单易懂。但是 Alice 的吹毛求疵精神也让我们看到了 Knuth 教授笔下的人物形象生动有趣,活泼可爱。

接下来还有一长段路要走,让我们慢慢品味。

留下您的评论