不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

古德斯坦定理(Goodstein’s theorem)(2)- 古德斯坦的证明思路

已有 3590 次阅读 2021-12-22 18:07 |个人分类:解读哥德尔不完全性定理|系统分类:科研笔记

古德斯坦定理是由鲁宾·古德斯坦提出的一条关于自然数的命题,即所有古德斯坦序列最终均结束于0


一,m的“继承n进制”表示法


一个自然数m的古德斯坦序列G(m)是一个自然数序列,是通过定义m的继承n进制构造出来的。


mn是自然数,n>1,我们定义m继承n进制如下:


首先把m写成n的幂之和,例如,如果m=266n=2

266=2^8+2^3+2^1


然后把每个指数写成n的幂之和,例如:

266 = 2^2^(2+1)+2^(2+1)+2^1



二,古德斯坦序列


自然数m的古德斯坦序列G(m)是通过m的继承n进制构造出来的:G1(m),G2(m),。。。,


我们现在定义序列G(m)的元素

G(m)的第一个元素G1(m)m写作继承2进制;元素Gn(m)m的继承n进制表示法中的每一个n替换为n+1,然后减去1所得,例如:

G1(266) = 2^2^(2+1) + 2^2+1 + 2 

G2(266) = 3^3^(3+1) + 3^(3 +1) + 2 ~ 10^38 

G3(266) = 4^4^(4+1) + 4^(4+1) + 1 ~ 10^616 

G4(266) = 5^5^(5+1) + 5^(5+1) ~ 10^10000.

。。。


尽管古德斯坦序列常常增长得快得惊人,但古德斯坦定理指出每个古德斯坦序列最终终止于0


比如,G(4)的元素继续增加一段时间,但在底数3*2^402.653.209时,它们达到最大值,在接下来的步骤中停留在那里,然后开始下降。在底数为3*2^402.653.211时达到0

 

二,古德斯坦定理证明思路


古德斯坦定理 对于任何mn > 1,从n开始的m的古德斯坦序列G(m)最终会达到0


古德斯坦用集合论方法证明了这个定理,其证明思路如下:


给定一个古德斯坦序列G(m),我们为之构造一个由序数组成的平行序列,这个平行序列的下界就是G(m)。如果这个平行序列中的项能够降到0,那么G(m)的项最终也必定降到0


这个平行序列的构造方法如下:给定G(m)中的第n项的继承(n+1)进制表示,将其中所有的n+1换成第一个无限序数ω。序数的加法、乘法、乘幂是有标准定义的,所以这样替换的结果是一个序数,并且这个序数不会比原来的项小。由于所有序数在其自然序下构成一个良序集,不存在无穷的单调下降的序数序列,所以这个平行序列一定会终止于0,此时G(m)也为0


古德斯坦定理这个独特的证明需要进一步解读。


参考文献:

https://en.wikipedia.org/wiki/Goodstein%27s_theorem




https://m.sciencenet.cn/blog-2322490-1317724.html

上一篇:古德斯坦定理(Goodstein’s theorem)(1)- 鲁本-古德斯坦
下一篇:批判性思维(Critical thinking)(1)

1 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-28 18:15

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部