一个不可证的定理-从一个数列说起

我在这里看到了这个有趣的数列及由其引出的一些奇特的结论。

首先，选取任意一个正整数，将之作为数列中的第一个数。比如，假设我们选取。

为计算数列中的第二项，我们首先把写成二进制形式，即。接着把所有的指数项写成它们的二进制表示，接着把所有指数项的指数项写成它们的二进制表示，依此类推。因此的相应形式是。接下来，我们把所有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还给出了另外一个例子，被称为“赫拉克勒斯大战九头蛇”（很喜感的名字），这与一种特定的树结构的增长有关。