Archive
一个不可证的定理-从一个数列说起
我在这里看到了这个有趣的数列及由其引出的一些奇特的结论。
首先,选取任意一个正整数,将之作为数列中的第一个数。比如,假设我们选取
。
为计算数列中的第二项,我们首先把
写成二进制形式,即
。接着把所有的指数项写成它们的二进制表示,接着把所有指数项的指数项写成它们的二进制表示,依此类推。因此
的相应形式是
。接下来,我们把所有2替换成3,并将得到的结果再减1。在这个例子中,
。显然
是一个非常大的数,大约
。
接着,用同样的方式得到其它数。为得到,我们将
用n进制形式表示,再将所有n替换成n+1,再将最后的结果减一。
这样我们得到:
为得到,我们必须将
写成六进制表达形式。首先注意到
但这还不是最终我们想要的形式,我们还要把所有指数项进一步展开。然后,我们把所有的6替换成7,再将得到的结果减1。不难想像最终我们将得到一个异常巨大的数。
对于这个数列(称为Goodstein数列),有两个十分深刻的定理:
定理(Goodstein定理). 存在一个k使.
也就是说,尽管这个数列看起来会飞快地增长直至无穷大,仍旧会最终变为零并终止。这个定理的证明非常复杂,用到了序数定理。
通过上面的数列的例子我们可以看出写出前几项(或者甚至前几百万项)以决定这个数列的收敛性是相当不可取的……但实际上存在某个数字开头的数列,很快就结束到0。比如,若以开始,则有
那么对于呢?请看下表(或这里)
Hereditary notation | Value |
---|---|
22 | 4 |
![]() |
26 |
![]() |
41 |
![]() |
60 |
![]() |
83 |
![]() |
109 |
![]() |
![]() |
![]() |
253 |
![]() |
299 |
![]() |
![]() |
它将继续增长,直至在进制下,到达最大值
,然后再经过
步变为零!
更令人称奇的是,在1982年,Laurie Kirby和 Jeff Paris证明了下面的定理:
定理. Goodstein定理在皮阿诺算术公理下是不可证的。
也就是说,这正是哥德尔在1931年所描述的第一不完备性定理中的不可证的定理!
根据哥德尔不完备性定理,若有一个公理足以表示所有基本算术(比如由皮阿诺公理所导出),那么它一定是不完备的。也就是说,一定存在一个有关算术的命题,不能由这组公理所证明。在他的证明中哥德尔给出了一个正确但不可证的命题。但它相当难理解,更像是一个刻意构造的矛盾,而不是一个数学上的命题。
第一个让数学家们满意的命题由Paris和Harrington给出(和拉姆赛数有关)。接着在1982年有了上面的Goodstein定理不可证的结论。此外Laurie Kirby和 Jeff Paris还给出了另外一个例子,被称为“赫拉克勒斯大战九头蛇”(很喜感的名字),这与一种特定的树结构的增长有关。