Home > Math Discoveries, Mathematics > 一个不可证的定理-从一个数列说起

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


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

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

为计算数列中的第二项m_2,我们首先把m_1写成二进制形式,即m_1=\sum a_i2^i。接着把所有的指数项写成它们的二进制表示,接着把所有指数项的指数项写成它们的二进制表示,依此类推。因此m_1的相应形式是m_1=18=2^4+2^1=2^{2^2}+2^{2^0}。接下来,我们把所有2替换成3,并将得到的结果再减1。在这个例子中,m_2=3^{3^3}+3^{3^0}-1。显然m_2是一个非常大的数,大约7.63 \times 10^{12}

接着,用同样的方式得到其它数。为得到m_n,我们将m_{n-1}用n进制形式表示,再将所有n替换成n+1,再将最后的结果减一。

这样我们得到:

m_1=2^{2^2}+2^{2^0}=18

m_2=3^{3^3}+3^{3^0}-1=3^{3^3}+2^{3^0}\approx 7.63 \times 10^{12}

m_3=4^{4^4}+2^{4^0}-1=4^{4^4}+4^0\approx 1.34\times 10^{154}

m_4=5^{5^5}+5^0-1=5^{5^5}\approx 1.91\times 10^{2184}

m_5=6^{6^6}-1\approx 2.66\times 10^{36305}

为得到m_6,我们必须将m_5写成六进制表达形式。首先注意到

m_5=6^{6^6}-1=5\cdot 6^{6^6-1}+5\cdot 6^{6^6-2}+\ldots+5\cdot 6^1+5\cdot 6^0

但这还不是最终我们想要的形式,我们还要把所有指数项进一步展开。然后,我们把所有的6替换成7,再将得到的结果减1。不难想像最终我们将得到一个异常巨大的数。

对于这个数列(称为Goodstein数列),有两个十分深刻的定理:

定理(Goodstein定理). 存在一个k使m_k=0.

也就是说,尽管这个数列看起来会飞快地增长直至无穷大,仍旧会最终变为零并终止。这个定理的证明非常复杂,用到了序数定理。

通过上面的数列的例子我们可以看出写出前几项(或者甚至前几百万项)以决定这个数列的收敛性是相当不可取的……但实际上存在某个数字开头的数列,很快就结束到0。比如,若以m_1=3=2^1+1开始,则有

m_2=3^1+1-1=3^1=3

m_3=4^1-1=3

m_4=3-1=2

m_5=2-1=1

m_6=1-1=0

那么对于m_1=4呢?请看下表(或这里

Hereditary notation Value
22 4
 3^3 - 1 = 2 \cdot 3^2 + 2 \cdot 3 + 2 26
 2 \cdot 4^2 + 2 \cdot 4 + 1 41
 2 \cdot 5^2 + 2 \cdot 5 60
 2 \cdot 6^2 + 2 \cdot 6 - 1 = 2 \cdot 6^2 + 6 + 5 83
 2 \cdot 7^2 + 7 + 4 109
 \vdots  \vdots
 2 \cdot 11^2 + 11 253
 2 \cdot 12^2 + 12 - 1 = 2 \cdot 12^2 + 11 299
 \vdots  \vdots

它将继续增长,直至在3\times 2^{402653209}进制下,到达最大值3\times 2^{402653209}-1,然后再经过3\times 2^{402653209}步变为零!

更令人称奇的是,在1982年,Laurie Kirby和 Jeff Paris证明了下面的定理:

定理. Goodstein定理在皮阿诺算术公理下是不可证的。

也就是说,这正是哥德尔在1931年所描述的第一不完备性定理中的不可证的定理!

根据哥德尔不完备性定理,若有一个公理足以表示所有基本算术(比如由皮阿诺公理所导出),那么它一定是不完备的。也就是说,一定存在一个有关算术的命题,不能由这组公理所证明。在他的证明中哥德尔给出了一个正确但不可证的命题。但它相当难理解,更像是一个刻意构造的矛盾,而不是一个数学上的命题。

第一个让数学家们满意的命题由Paris和Harrington给出(和拉姆赛数有关)。接着在1982年有了上面的Goodstein定理不可证的结论。此外Laurie Kirby和 Jeff Paris还给出了另外一个例子,被称为“赫拉克勒斯大战九头蛇”(很喜感的名字),这与一种特定的树结构的增长有关。

About these ads
  1. No comments yet.
  1. March 10, 2012 at 6:56 pm | #1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: