数学的边界：被证明无法证明的定理.doc

今天我在这里看到了一个神奇的数列以及关于它的两个惊人的结论。这是由Goodstein发现的，这个名字让我不禁想到了1984里那个恰好同名的人。Goodstein数列是这样的：首先选取一个正整数m1, 比如设m1= 18 . 然后对它进行这样一个操作：把它写成2的次幂之和的形式 ( 18 = 24+ 21) , 再把幂数也写成2的次幂的形式：我们把这种写法叫以2为底的遗传记法。这个词是我翻译的，可能不准确，原文叫hereditary base 2 notation.m2是这样生成的：把m1的这种写法中所有的2都换成3，再减1。对于我们的例子，注意到这是个非常大的数，约等于7.631012。现在把m2写成以3为底的遗传记法，再把所有的3都换成4，再减1，就成为了m3。以此类推，mn+1就是把mn写成以n+1为底的遗传记法，再把所有的(n+1)换成(n+2)，再减1.对于m1= 18 ,前几项是这样：看到了前5个数，我们一定会认为这个数列以极快的速度发散到无穷，甚至比指数级或阶乘级还快得多。那么植根于这个数列的Goodstein定理想必就是论证数列的发散速度的。但是，真相大出我的意料：Goodstein定理：对于任何一个初始数，数列总会在有限步内变为0。虽然我们都知道仅看一个数列的前几项就猜测它的收敛性是不可取的，虽然我们也知道像调和级数（1+1/2+1/3+1/4+）这种增加超级慢的级数也发散，虽然我们知道数学中一个又一个的大反例（比如欧拉方阵），但这还是太过出人意料了。这个定理有没有证明？当然有，要不怎么叫定理呢。它的证明其实也不难，用到了序数的知识。大概意思是这样：构造另一个数列称为平行数列（不妨设为Pn），使它的每一项都不小于给定Goodstein数列的对应项，然后再证明这个平行数列最后等于0。具体的方法是对于一个Goodstein数列mn , 把它的第n项写成以n+1为底的遗传记法，再把每个n+1替换成最小的无限序数。注意到有这两个事实：第一，Pn肯定不小于mn，比如.第二，Pn其实是单调递减的。还就上面的例子来说，在原数列中把换成了，对平行数列没有影响，因为还是它本身。但是“减1”这个操作却确确实实地对平行数列产生了影响，因为把4换成5-1这个操作在平行数列中可就是把换成了4。清晰一点来看，就是下面这样(还是这个例子)：nmnPn3 4 又由于序数是良序的，一个单调递减的Pn必然最后减小到0.注：以上仅仅是证明的一个Sketch，详细证明请见Wikipedia。是不是觉得有点不爽？一个全是自然数的数列，想证明它的性质居然用到了序数和选择公理（当然我指的是良序定理）！有数学家开始探索有没有简单的方法证明这个定理。但是，这些探索给出了一个爆炸性的定理：定理：Goodstein定理在Peano公理系统下是不可证的。这是由Laurie Kirby和 Jeff Paris在1982年发现的。这个定理恰恰就是1931年Gdel的不完备性定理的一个例子！哥德尔的不完备性定理说，一组公理如果足够强到能够蕴含Peano公理，也就是能进行基本的算术，那么这个系统是不完备的。也就是说肯定有至少一个关于算术的问题是Peano公理既不能证明为真，也不能证明为假的。Gdel本人给出了一个这样的命题，但明显是故意构造的，类似于“这个命题不可证明”这种自我指涉的命题，本质上