古德斯坦定理是数理逻辑中的一个关于自然数的叙述,是在 1944 年由鲁本·古德斯坦所证明。其主要是在说明“古德斯坦序列”最终会结束于 0 。柯比和柏丽斯[1] 证明它在皮亚诺算术中是不可证明的(但它可以在一个更强的系统如二阶算术中被证明)。这是继哥德尔不完备定理构造的命题(
)和 1943 年格哈德·根岑直接证明皮亚诺算术中 ε0-induction 不可被证明之后,第三个(对自然数为真的)命题被证明在皮亚诺算术中不可证明。之后的例子是柏丽斯–哈灵顿定理。
劳伦斯·柯比和杰夫·柏丽斯介绍了一个图论中的九头蛇游戏,其行为类似古德斯坦序列:“九头蛇”是一棵有根的树,而序列每一步是砍掉它的一颗头(即树的分支),然后九头蛇则对应地会依据某些规则来增加有限数量的头。柯比和柏丽斯则证明,不管赫拉克勒斯使用何种策略来砍头,九头蛇最终会被斩杀(尽管这个过程可能会非常漫长)。如古德斯坦序列,柯比和柏丽斯证明其在皮亚诺算术中是不可证明的[1]。
以n为基底的瓜瓞式基底表示法
古德斯坦序列是由一种“以n为基底的瓜瓞式表示法”的概念来定义的。这个表示法与平常的 n 进位制表示法很像,但一般的进位表示法无法达到古德斯坦定理的目的。在原本的 n 进位表示法,n 是一个大于 1 的自然数,而任一个自然数 m 则被改写为一些由 n 的幂次的乘积的相加之和:
![{\displaystyle m=a_{k}n^{k}+a_{k-1}n^{k-1}+\cdots +a_{0},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9f92833f63c5c1a225a0ce7ba5f7b78de3b0573)
其中,每个系数 ai 满足0 ≤ ai < n,且ak ≠ 0。如在 2 进位中,
![{\displaystyle 35=32+2+1=2^{5}+2^{1}+2^{0}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/636de9306e9a2756ce3b786b52957948fbd15931)
所以, 35 的二进位是 100011(25 + 2 + 1)。类似地,由 3 进位表示的 100 是 10201:
![{\displaystyle 100=81+18+1=3^{4}+2\cdot 3^{2}+3^{0}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9455987bbea6282db05abdfc682acf4f7150c6a0)
然而需注意的是,这些指数仍非是基于 n 的表述法。如上述表示式中的 25 和 34 。
将一个 n 进位表示转换为瓜瓞式n基底表示法,首先要将每个指数改为 n 基底表示法。然后改写指数中的指数,持续这个动作直到每个数都被改为以 n 为基底表示法。
譬如, 2 进位的 35 为 100011 ,将它改写成以 n 为基底的瓜瓞式表示法为:
![{\displaystyle 35=2^{2^{2}+1}+2+1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d45bb27e6a8ade53205d93ad929128f613a91419)
(5 = 22 + 1.) 。类似的,以3为基底的瓜瓞式表示法的 100 为
![{\displaystyle 100=3^{3+1}+2\cdot 3^{2}+1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac894ad333c59d2bf927ea9e58ad20be047badd2)
古德斯坦序列
古德斯坦序列 G(m) 是一个自然数的序列。第一项为 m 本身。第二项则是先将 m 以 2 为基底得出其的瓜瓞式表示法,再将所有的 2 改为 3,再减去 1。更一般地,第 (n + 1) 项的 G(m)(n + 1) 为:
- 将 G(m)(n) 转为以 n + 1 为基底的瓜瓞式表示法。
- 将所有的 n + 1 改为 n + 2 。
- 减 1。
- 重复这个过程,直到结果为 0 则停止。
前几个古德斯坦序列会很快地终止,如 G(3) 结束于第 6 步:
基底 |
瓜瓞式表示法 |
值 |
注记
|
2 |
![{\displaystyle 2^{1}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e27ce9b5b61362e577679f593180e2f8fdf72a22) |
3 |
以 2 为基底改写 3。
|
3 |
![{\displaystyle 3^{1}+1-1=3^{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3bd6e3985e40469b1dffed112f7e7de5875bcf2a) |
3 |
将 2 改为 3,再减 1。
|
4 |
![{\displaystyle 4^{1}-1=3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a45cdb0bb670dd3b557cedb03a69ee5239a27b25) |
3 |
将 3 改为 4,再减 1。此时已无任何 4 了。
|
5 |
![{\displaystyle 3-1=2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09bdf1ca439ba3f857af8da87f0a53a28648e2c8) |
2 |
没有 4 需要改为 5。单纯减 1。
|
6 |
![{\displaystyle 2-1=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e790a95dd451fdb4c8e2f74f60823807ca50f2b) |
1 |
没有 5 需要改为 6。单纯减 1。
|
7 |
![{\displaystyle 1-1=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6e3a458263e924d197c37a58beae62ade425ddf) |
0 |
没有 6 需要改为 7。单纯减 1。
|
之后的古德斯坦序列则成长到很庞大的数字,如 G(4) A056193 开始如下:
瓜瓞式表示法 |
值
|
![{\displaystyle 2^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/efd7711cd907a2d46557a410fb67fc0d84c52ba3) |
4
|
![{\displaystyle 3^{3}-1=2\cdot 3^{2}+2\cdot 3+2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9ddc5a170223c0d10302fc268afa46bba9e8a32) |
26
|
![{\displaystyle 2\cdot 4^{2}+2\cdot 4+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c368f1b4655bd12e829bd7fec209d1c36b957097) |
41
|
![{\displaystyle 2\cdot 5^{2}+2\cdot 5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f83dd2214160f498cd27305fe8585a52411e8554) |
60
|
![{\displaystyle 2\cdot 6^{2}+2\cdot 6-1=2\cdot 6^{2}+6+5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c79ebf7fc21a9ff62aa2150f2eeec5913d96ece) |
83
|
![{\displaystyle 2\cdot 7^{2}+7+4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ea481d05c5978de457104069208d8da24a8e6bb) |
109
|
![{\displaystyle \vdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8039d9feb6596ae092e5305108722975060c083) |
|
![{\displaystyle 2\cdot 11^{2}+11}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99a7c16646f297034ce8b982f1e13bd8c3b095c7) |
253
|
![{\displaystyle 2\cdot 12^{2}+12-1=2\cdot 12^{2}+11}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50f6cac23558e2acd65c09d28f257b04e7bb39f9) |
299
|
![{\displaystyle \vdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8039d9feb6596ae092e5305108722975060c083) |
|
![{\displaystyle 2\cdot 24^{2}-1=24^{2}+24\cdot 23+23}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50968eeaa463b70fba3c6036929bb45a559f878d) |
1151
|
G(4) 会一直递增,直到基底为
时,会达到最大值
,并在这里停留
步后,然后开始递减。
这个序列到达 0 时,当时的基底为
。(有趣的是,这是个胡道尔数:
。而且,对于所有起始值大于 4 的数,都是如此。[来源请求])
不过,G(4) 仍无法很好地展示古德斯坦序列的项数是如何快速地成长。G(19) 成长更迅速,其开头几项如下:
尽管其成长如此迅速,古德斯坦定理说明了无论起始值为何,每个古德斯坦最终会终止于 0。
证明
古德斯坦定理的证明(需要使用皮亚诺算术以外的技巧)如下:
对于每个给定的古德斯坦序列 G(m) ,我们可以建造一个由序数所组成的平行序列 P(m) ,而且是严格递减和终止。所以G(m) 也必将停止,并且它只在达到 0 时才会终止。
对这个证明的常见的误解在于认 G(m) 达到 0 是“因为”它被 P(m) 所支配。事实是,P(m) 对支配 G(m) 毫无作用。其重点在于: G(m)(k) 存在当且仅当 P(m)(k) 存在。于是,如果 P(m) 终止,则 G(m) 也如此。而 G(m) 只有在到逹 0 时才会终止。
我们可以定义函数 f(x),将 x 改为以k为基底的表示法,并将每个 k 换成第一个无穷序数 ω。
而序列 P(m) 中的每一项 P(m)(n) 则定义为 f(G(m)(n),n+1)。譬如,G(3)(1) = 3 = 21 + 20 和 P(3)(1) = f(21 + 20,2) = ω1 + ω0 = ω + 1 。序数的加法、乘法和指数都是良好定义的。
我们可声明
。在古德斯坦序列中,将 G(m)(n) 改换基底后,将其记为
。明显的,
,现在我们套用 -1 运算后,因为
,所以
。
譬如,
乃
,所以
和
是严格变小。需注意的是,若要计算 f(G(m)(n),n+1) ,我们要先将 G(m)(n) 改为以 n+1 为基底的表示法。所以如
等的表示式,既不会是无意义的也非等同
。
P(m) 是严格递减的。而标准排序运算元 < 在序数上是良基关系,一个无穷的严格递减序列是不可能存在的。换句话说,每个严格递减的序数序列会停止(不可能无限)。但P(m)(n) 是由 G(m)(n) 计算出来的。 G(m)(n) 也必然停止,这意味著它会达到 0 。
虽然这个证明相当简单,但柯比-柏丽斯定理[1] (证明了在皮亚诺算术中不会有古德斯坦定理)则是非常专门且相当困难。它使用了皮亚诺算术中的可数非标准模型。
扩展的古德斯坦定理
假设古德斯坦定理的定义中的“将b改为b+1”的这个动作,将它改为 b+2,那么这个序列会终止吗?
更一般地,让 b1, b2, b3, … 为任意整数列,然后让第 n+1 项的 G(m)(n+1) 变成:
将 G(m)(n) 改为 bn 的表示法,将 bn 改为 bn+1 再减 1 。
我们仍可断言这个序列仍会终止。
扩展的证明则将 P(m)(n) = f(G(m)(n), n) 定义为如下:
将 G(m)(n) 改为 bn 表示法,再将所有的 bn 改为第一个无限序数 ω。
古德斯坦序列中,从G(m)(n)到G(m)(n+1)的换底运算并不会改变 f 的值。
譬如,如果 bn = 4 且 bn+1 = 9,
则
。因此,序数
是
严格大于序数
。
起始点为变量的序列长度函数
古德斯坦函数
定义为由 n 为起始值的古德斯坦序列的长度。因为古德斯坦序列会终止,所以这是一个完全函数。要测定
的快速成长,可由多种借由标准基于序数体系中的函数,如Hardy hierarchy 中的
函数,和 Löb and Wainer 的 高成长体系
函数。
- Kirby and Paris (1982) 证明
有著和
近似的成长速度(等同于
); 更精确地说,对每个
,
控制
,且
控制
。
- (对两个函数
,我们说
控制
是指,如果对于所有足够大的
,都有
。)
![{\displaystyle {\mathcal {G}}(n)=H_{R_{2}^{\omega }(n+1)}(1)-1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fbcc1d05c5be45338ede84ef18f587f0fc75daf)
- 其中
是将 n 改为以 2 为基底的瓜瓞式表示法,并将所有 2 改为 ω 的结果(即古德斯坦定理的证明中所做的事)。
- Caicedo (2007) 证明如果
且有
then
.
一些例子如下:
n
|
|
1
|
|
|
|
|
2
|
2
|
|
|
|
|
4
|
3
|
|
|
|
|
6
|
4
|
|
|
|
|
3·2402653211 − 2 ≈ 6.895080803×10121210694
|
5
|
|
|
|
|
> A(4,4)>
|
6
|
|
|
|
|
> A(6,6)
|
7
|
|
|
|
|
> A(8,8)
|
8
|
|
|
|
|
> A3(3,3) = A(A(61, 61), A(61, 61))
|
|
12
|
|
|
|
|
> fω+1(64) > 葛立恒数
|
|
19
|
|
|
|
|
|
(对于阿克曼函数和葛立恒数的界限,请参考高成长体系。)
可计算函数的应用
古德斯坦定理可用于构造一个全可计算函数,但皮亚诺算术却不能证明它是全函数。图灵机可以有效地列举古德斯坦序列;所以存在一个特殊的图灵机来计算古德斯坦函数。这个图灵机只需列举出 n 的古德斯坦序列,并在遇到 0 时结束,并传回其长度。因为每个古德斯坦序列终将结束,所以这个函数是完全的。但因为皮亚诺算术不能证明古德斯坦序列会终止,皮亚诺算术不能证明这个图灵机计算了一个完全函数。
另见
参考资料
Bibliography
- Goodstein, R., On the restricted ordinal theorem, Journal of Symbolic Logic, 1944, 9 (2): 33–41, JSTOR 2268019, doi:10.2307/2268019 .
- Cichon, E., A Short Proof of Two Recently Discovered Independence Results Using Recursive Theoretic Methods, Proceedings of the American Mathematical Society, 1983, 87 (4): 704–706, JSTOR 2043364, doi:10.2307/2043364 .
- Caicedo, A., Goodstein's function (PDF), Revista Colombiana de Matemáticas, 2007, 41 (2): 381–391 [2019-02-20], (原始内容存档 (PDF)于2011-10-09) .
外部链接