Goodstein定理
http://bbs.oursci.org/newreply.php?postid=31376
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
Goodstein定理——歌德尔不完全定理在皮亚诺公理系统中的一个例子
作者：冷饭
时间：2005-01-05 18:45
从非常非常粗糙的角度讲，歌德尔证明他的不完全定理的方法，就是构造了一个类似“本命题不可被证明”这样一个命题。当然这个陈述是很不严格的，因为现在逻辑中禁止在命题中提到“本命题”这样的玩意，另外，“证明”不是一个在皮亚诺算术系统中定义了的概念。歌德尔证明中的主要思想之一，就是如何解决后一个难点。这个就不具体说了。
在歌德尔不完全定理被证明时，大多数数学家并不太担心自己会实际上碰到这样的既真但又不可被证明的命题，因为这样的命题似乎都是一些很怪的绕来绕去的人造玩意，在数学中被实际研究的问题，应该不会是这样的。现在大多数数学家应该还是这个心态，比如说研究歌德巴赫猜想的很少会去怀疑这个命题会不会是在集合论公理体系下解决不了的。
但是有一些看起来很自然的命题，已经被证明是不能在某些公理体系下证明的。在这里我介绍其中最早被发现的这样的定理之一：Goodstein定理。
任取一个自然数n，比方说266，我们把它写成以2为底的幂次的和，其实就是转成2进制：
266 = 2^8+2^3+2
现在右边还有比2大的数字比如说8啊3啊，就进一步转换变成
266 = 2^2^3 + 2^(2+1)+2
还有一个3，继续写成
266 = 2^2^(2+1) + 2^(2+1)+2
可以知道，无论什么自然数都可以唯一地写成这样的形式。同样地，如果不是以2为底而是以其他大于2的自然数为底，也可以做同样的事情。
现在我要把刚才那个式子的右边中的所有2都改写成3，那就成了
3^3^(3+1) + 3^(3+1)+3
再减去一个小小的1，就成了
3^3^(3+1) + 3^(3+1)+2
这就是现在这个数以3为底的这种展开。
现在把这个式子的右边中的所有3都改写成4，那就成了
4^4^(4+1) + 4^(4+1)+2
再减去一个小小的1，就成了
4^4^(4+1) + 4^(4+1)+1
这就是现在这个数以4为底的这种展开。
现在把这个式子的右边中的所有4都改写成5，那就成了
5^5^(5+1) + 5^(5+1)+1
再减去一个小小的1，就成了
5^5^(5+1) + 5^(5+1)
这就是现在这个数以5为底的这种展开。
现在把这个式子的右边中的所有5都改写成6，那就成了
6^6^(6+1) + 6^(6+1)
再减去一个小小的1，就成了
6^6^(6+1) + 6^(6+1) - 1
这可不是现在这个数以6为底的这种展开，因为有一个-1。所以展开来，它就是：
6^6^(6+1) + 5*6^6 + 5*6^5 + 5*6^4 + 5*6^3 + 5*6^2 + 5*6 + 5
这就是现在这个数以6为底的这种展开。
现在把这个式子的右边中的所有6都改写成7，那就成了
7^7^(7+1) + 5*7^7 + 5*7^5 + 5*7^4 + 5*7^3 + 5*7^2 + 5*7 + 5
减去一个小小的1，就成了
7^7^(7+1) + 5*7^7 + 5*7^5 + 5*7^4 + 5*7^3 + 5*7^2 + 5*7 + 4
这就是现在这个数以7为底的这种展开。
……
这么我们可以一直继续下去，数字似乎变得越来越大，增大的速度也越来越快，比方上面以7为底的那个数字要比7^7^8大，而7^7^8如果要用十进制写出来，需要用四百八十多万位数字，要印成了书都成煌煌巨著了。因为底数增加1，原来的数字就会增加很多，减去一个小小的1根本是九牛拔一毛无所谓。
但是，但是，Goodstein定理说，对任意的自然数n，当然266也包括在内，如果我们一直重复这个过程，我们最后总会到达0！
让我们来验证一下：对于n=0,1,2,3，都没什么好说的，很快掉到0。
n=4，第一排数字是步数，也就是现在是以几为底的表示了，第三排是那个式子，第二排是式子用十进制表示出来的值。
2 4 2^2
3 26 2*3^2 + 2*3 + 2
4 41 2*4^2 + 2*4 + 1
5 60 2*5^2 + 2*5
6 83 2*6^2 + 6 + 5
7 109 2*7^2 + 7 + 4
8 139 2*8^2 + 8 + 3
9 173 2*9^2 + 9 + 2
10 211 2*10^2 + 10 + 1
11 253 2*11^2 + 11
12 299 2*12^2 + 11
13 348 2*13^2 + 10
: : :
23 1058 2^23^2
24 1151 24^2 + 23*24 + 23
25 1222 25^2 + 23*25 + 22
: : :
47 3290 47^2 + 23*47
48 3407 48^2 + 22*48 + 47
: : :
95 11115 95^2 + 22*95
96 11327 96^2 + 21*96 + 95
: : :
注意到从第三步开始有个大项2*3^2，这个项中只有“3”这个地方以后会大起来，其他的一直保持不变，直到第24步的时候，这个项没有了，大项换成了 24^2，然后这一项里也就“24”这地方会变。然后这样下去大约要4亿多步以后，跟在这个平方项后面的那些杂碎都完蛋了，它成了孤家寡人，然后减一个小小的一，这个平方项就不见了。然后再这么下去，大约要再过10^121步，它才变成了0。
通过验证4，我们可以看见一个图景。就象我们看着倒记时的数字式电子跑表的时候，秒位上的数字滴答得很快，一秒秒减下来，等到0秒，再过1秒的时候，分位上的数字减1，可是秒位上的又变成59了，然后又是60秒后，分位上的数字也成0了，再过1秒，小时位上数字减1，分位和秒位上都又成99了。不过慢是慢，迟早会通通变0的。仔细观察刚才关于4的序列，我们发现Goodstein定理的序列中，也有一个类似的钟，只是它的每“分钟”，都要值许多许多“秒钟”，每“小时”要值许多许多“秒钟”，以至于我们感到这个钟不走了，甚至不是倒记时，而是向前走的！
“它的每‘分钟’，都要值许多许多‘秒钟’，每‘小时’要值许多许多‘分钟’”
不仅如此，它的每‘分钟’要值多少‘秒钟’不是固定的，越晚走掉的每一“分钟”，值的“秒钟”，要比前面的“分钟”要多得多，就好比在那个电子秒表里，第一次秒数走到0再过1秒时，分数减1，秒数变59，而第二次秒数走到0再过1秒时，分数减1，秒数却变成1000，第三次秒数走到0再过1秒时，分数减 1，秒数变成10000……（Goodstein序列中这个秒数增加的速度要比这个快得多）。同样，“小时”对“分钟”也是一样。而且还可以有“小时”以上的级别，象“天”“月”“年”。这样，如果你老是注意着“秒数”，就很容易觉得它越来越大，这倒数记时怎么也数不到0。
验证从5开始的序列……这个就算了吧。
Goodstein定理的叙述完全可以在皮亚诺公理系统中进行，它只牵涉到对数字的加减乘的运算，没有必要用到集合论，但是对于它的证明却用到了集合论。在1982年，两位数学家证明了，如果不用集合论，只在皮亚诺公理系统中，是不可能证明此定理的。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
31770- Goodstein定理的证明大纲
作者：bamboo
时间：2005-01-10 15:28
背景知识：
超穷序数
所有集合A都可加以良序，亦即(1)A的任意两个不同元素都可以比较大小及(2)A的任一子集S都有一个最小元素。如果集合A是有限的，良序化后便与某一自然数(在这里的意思包括0)相对应(包括元素大小的顺序)。个别自然数0,1,2,3,…构成有限序数。自然数整体(包括其顺序)是最小的无限序数，记之为ω={0,1,2,3,…}。在自然数之后还有其它无限序数(超穷序数)，例如ω+1={0,1,2,3,…,ω}及ω+2={0,1,2,3,…,ω,ω+1}。如果集合A是无限的，良序化后便与某一超穷序数相对应。当然同一个集合A可以有不同的良序，如果A是无限的，那么不同的良序化后便可能相对应不同的序数。
超穷序数的生成
0,1,2,3,…,ω,ω+1,ω+2,…,ω+ω=ω2,ω2+1,ω2+2,…,ω3,…,ω.ω=ω^2,…,ω^2+ω,…,ω^3,…,ω^ω,…, ω^(ω+1),…,ω^(ω^2),…,ω^(ω^2)+ω^2+ω,…,ω^(ω^2+ω),…,ω^(ω^3),…,ω^(ω^ω)=ω^^3,…, ω^(ω^(ω^ω))=ω^^4,…,ω^^ω=ε0,以及更大的超穷序数。由序数构成的集合按序数大小排列已经是良序化了。
超穷归纳法
我们熟悉的数学归纳法可以用集合论的语言表述为：设S是自然数集合Z的一个子集，如果(1)0是S的元素，及(2)从k是S的元素可推出k+1是S的元素，那么(3)S=Z。数学归纳法是Peano算术系统的公理之一。
对于良序化的集合也有类似的性质：设A是良序化的集合，S是A的一个子集，如果(1)A的最小元素是S的元素，及(2)x是A的元素而从所有在A中比x小的元素是S的元素可推出x也是S的元素，那么(3)S=A。这便是良序集合的超穷归纳法。
易证数学归纳法是超穷归纳法的特殊形式，但从数学归纳法不能推出超穷归纳法，因为数学归纳法不能跨越从有限到无限的鸿沟。
Peano算术系统的协调性(Consistency)
Godel证明了不能仅由Peano算术系统的公理出发证明其本身的协调性。但Gentzen证明了藉助超穷归纳法(只需假设直到ε0成立，不需对更大的序数作任何假设)，可以证明Peano算术系统的协调性。
由序数构成的严格递减序列
因为由序数构成的集合按序数大小排列已经是良序化了，可以运用超穷归纳法
证明，由序数构成的严格递减序列的长度是有限的。(比对：由有理数构成的严格递减序列的长度可以是无限的，但由自然数构成的严格递减序列的长度必然是有限的。)
Goodstein定理的集合论证明大纲：
在Goodstein序列中把所有进制底数(即第一个Goodstein数中的2，第二个Goodstein数中的3，等等)换成ω，把底数以外的数字保留而加以合适的解释(要注意运算的顺序，3ω跟ω3是不同的，前者其实等于ω，后者等于ω+ω+ω)，例如以5为底，2*5^(3*5)+4*5+1便换成(ω^(ω3))2+ω4+1=ω^(ω+ω+ω)+ω^(ω+ω+ω)+ω+ω+ω+ω+1。整个Goodstein序列便换成另一条由序数构成的严格递减序列。因为这种序列的长度是有限的，所以原先的Goodstein序列的长度也是有限的，便推出任一正整数在Goodstein变换下终于会达到0的结论。
Goodstein定理不能由Peano算术系统公理推出的证明思路：
简而言之，就是若从Goodstein定理即「所有Goodstein序列都收敛于0」出发，可以推论出超穷归纳法直到ε0成立。若Goodstein定理能够由Peano算术系统公理推出，根据Gentzen的工作结果，即可证明Peano算术系统本身的协调性，但这与Godel的工作结果相矛盾。因此 Goodstein定理不能由Peano算术系统公理推出。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
但是我有一个疑问，换底之后，递减的过程中出现的“-1”是如何消除的？因为并没有“ω-1”这种东西啊？
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
31838- 项数是固定的
作者：bamboo
时间：2005-01-11 09:31
令G为原Goodstein自然数序列，F为进制底数换成ω后的序数序列。要知道F(k+1)不是由F(k)-1而来，而是由G(k+1)换底而来，因此不会产生ω-1的问题。
以266为例：
G(1) = 266 = 2^2^(2+1) + 2^(2+1)+2
F(1) = ω^ω^(ω+1) + ω^(ω+1)+ω
G(2) = 3^3^(3+1) + 3^(3+1)+2
F(2) = ω^ω^(ω+1) + ω^(ω+1)+2
G(3) = 4^4^(4+1) + 4^(4+1)+1
F(3) = ω^ω^(ω+1) + ω^(ω+1)+1
G(4) = 5^5^(5+1) + 5^(5+1)
F(4) = ω^ω^(ω+1) + ω^(ω+1)
G(5) = 6^6^(6+1) + 5*6^6 + 5*6^5 + 5*6^4 + 5*6^3 + 5*6^2 + 5*6 + 5
F(5) = ω^ω^(ω+1) + (ω^ω)5 + (ω^5)5 + (ω^4)5 + (ω^3)5 + (ω^2)5 + ω5 + 5
G(6) = 7^7^(7+1) + 5*7^7 + 5*7^5 + 5*7^4 + 5*7^3 + 5*7^2 + 5*7 + 4
F(6) = ω^ω^(ω+1) + (ω^ω)5 + (ω^5)5 + (ω^4)5 + (ω^3)5 + (ω^2)5 + ω5 + 4
原G序列收敛到0的项数是固定的，F序列跟G序列一样，也是固定的。
