Goodstein函数

古德斯坦函数(Goodstein Function)，是由鲁宾•古德斯坦(Reuben Goodstein)构造出的快速增长的函数。

定义

首先需要定义数m的以n为底的遗传记法：

假设我们将一个非负整数m表示为n的幂次之和，然后将这些幂指数本身也表示为类似的幂次和，不断重复这一过程，直到所有的最高次指数都小于n。例如，我们可以将100写作$2^6+2^5+2^2$进一步可以写为$2^{2^2+2}+2^{2^2+1}+2^2$。这种表示方式称为m的以n为底的遗传记法。

Goodstein定义了一个数列$G_k(n)$：

对任意自然数n，都有$G_0(n)=n$

对任意自然数n,k，都有$G_{k+1}(n)$是把$G_k(n)$写成以k+2为底的遗传记法，随后把里面所有的k+2改成k+3，最后再把整个数减一所得到的数。

我们拿100作为例子：

$G_0(100)=100=2^{2^2+2}+2^{2^2+1}+2^2$

$G_1(100)=3^{3^3+3}+3^{3^3+1}+3^3-1=3^{3^3+3}+3^{3^3+1}+3^2\times 2+3\times 2+2=228767924549636$

$G_2(100)=4^{4^4+4}+4^{4^4+1}+4^2\times 2+4\times 2+1\approx 3.486030062\times 10^{156}$

……

这种快速增长的序列称为 Goodstein 序列。令人惊讶的是，对于 n 的所有值，$G_k(n)$ 最终达到峰值、下降并返回零。这个事实被称为古德斯坦定理。更令人惊讶的是，可以证明古德斯坦定理无法用皮亚诺算术来证明。

我们定义古德斯坦函数$G(x)$等于古德斯坦序列$G_k(x)=0$时k的值。它的FGH增长率为${\epsilon }_0$.

例子

我们以较小的x作为例子，来计算一下$G(x)$.为了更加清晰，我们不展示$G_k(n)$ 的具体值，而是展示它的以k+2为底的遗传记法表示。读者可以自行计算取值。

x=1

aaaaa

k	$G_k(x)$以k+2为底的遗传记法表示
0	1
1	0

因此G(1)=1.

x=2

aaaaa

k	$G_k(x)$以k+2为底的遗传记法表示
0	2
1	2
2	1
3	0

因此G(2)=3.

x=3

aaaaa

k	$G_k(x)$以k+2为底的遗传记法表示
0	2+1
1	3
2	3
3	2
4	1
5	0

因此G(3)=5.

从G(4)开始，古德斯坦函数将开始“起飞”

x=4

aaaaa

k	$G_k(x)$以k+2为底的遗传记法表示
0	$2^2$
1	$3^2\times 2+3\times 2+2$
2	$4^2\times 2+4\times 2+1$
3	$5^2\times 2+5\times 2$
4	$6^2\times 2+6+5$
9	$11^2\times 2+11$
10	$12^2\times 2+11$
21	$23^2\times 2$
22	$24^2+24\times 23+23$
45	$47^2+47\times 23$
46	$48^2+48\times 22+47$
93	$95^2+95\times 22$
189	$191^2+191\times 21$
381	$383^2+383\times 20$
402653181=$3\times 2^{27}-3$	$402653183^2$
402653182	$402653184\times 402653183+402653183$
$3\times 2^{402653210}-3$	$3\times 2^{402653210}-1$
$3\times 2^{402653210}-2$	$3\times 2^{402653210}-1$
$3\times 2^{402653211}-3$	0

因此$G(4)=3\times 2^{402653211}-3$

这里它展示了很清晰的“下降”过程。

我们有G(12)大于葛立恒数这个结论。

与 HH 的关系

定义$R_a^{\omega }(n)$为将n表示为以a为底的遗传记法，然后将所有的底数a全部替换为$\omega$所得到的序数。我们可以证明以下结论：

$G(n)=H_{R_2^{\omega }(n)}(3)-3$，其中$H_{\alpha }(n)$是 Hardy 层级。

证明

以下叙述中总是考虑带乘法的康托范式和小于${\epsilon }_0$的序数，希腊字母表示序数，拉丁字母表示正整数。

先证一个引理：$H_{R_a^{\omega }(b+1)}(a)=H_{R_a^{\omega }(b)+1}(a)$，$a$是不小于3的正整数。

引理的证明：以下用$k$表示某个小于$a$的正整数。我们称一个序数$\alpha$是好的，如果它的康托范式中出现的所有正整数全都小于$a$。不难得出，$\alpha$是好的当且仅当它是某个$R_a^{\omega }(b)$的取值。

记$R_a^{\omega }(b+1)=\alpha$。将$H_{\alpha }(a)$进行多次取基本列，使下标为后继序数，得到$H_{\beta }(a)$。那么：

1) $\beta$是好的，不考虑正整数项。

由于$H_{\beta }(a)$的自变量为$a$，取基本列时得到的正整数不超过$a$。那么只要证明产生$\beta$时得到的$a$会在下一步被立即使用即可：

若$\alpha$是后继序数，则$\alpha =\beta$，显然是好的。

若$\alpha$是极限序数，设$\alpha ={\alpha }_0+\gamma \times k$：

1. $\gamma =\omega$，则下一步得到${\alpha }_0+\gamma \times (k-1)+a$，已经是后继了，故结论成立；
2. $\gamma ={\omega }^{\delta +1}$，$\delta$是大于等于1的序数，则下一步得到${\alpha }_0+\gamma \times (k-1)+{\omega }^{\delta }\times a$，下一步取${\omega }^{\delta }\times a$的基本列，故结论成立；
3. $\gamma ={\omega }^{{\gamma }_0+\omega \times k}$，则下一步得到${\alpha }_0+{\omega }^{{\gamma }_0+\omega \times (k-1)+a}$，下一步取${\omega }^{\cdots +a}$的基本列，故结论成立；
4. $\gamma ={\omega }^{{\gamma }_0+\sigma \times k}$，$\sigma$是${\omega }^2$的倍数，则此时等效于对$\sigma$取两次基本列的问题。由于$\sigma <\gamma$，使用序数的递降法知结论成立。

以上对于$\gamma ={\omega }^{\sigma }$中分别讨论了$\sigma =1$，$\sigma$为非1后继序数，$\sigma$为极限序数但不为${\omega }^2$的倍数，$\sigma$为${\omega }^2$的倍数的情况。综上，结论1)得证。

易得$g_{R_a^{\omega }(n)}(a)=n$，其中g是SGH。设$\beta =\theta +1$，则$\theta$是好的。所以，

由于增长层级在取基本列上规则相同，$g_{\alpha }(a)=g_{\beta }(a)$，

$g_{\theta +1}(a)=g_{\beta }(a)=g_{\alpha }(a)=b+1=g_{R_a^{\omega }(b)}(a)+1=g_{R_a^{\omega }(b)+1}(a)$，

$g_{\theta }(a)=g_{R_a^{\omega }(b)}(a)$。

由于$\theta$是好的，遗传记法是唯一的，故$\theta =R_a^{\omega }(b)$。从而$H_{R_a^{\omega }(b+1)}(a)=H_{\alpha }(a)=H_{\beta }(a)=H_{\theta +1}(a)=H_{R_a^{\omega }(b)+1}(a)$。引理得证。

原命题的证明 对于一般的自然数$k$，根据Goodstein序列的定义，有$R_{k+3}^{\omega }(G_{k+1}(n)+1)=R_{k+2}^{\omega }(G_k(n))$。于是，

$H_{R_{k+3}^{\omega }(G_{k+1}(n))}(k+4)=H_{R_{k+3}^{\omega }(G_{k+1}(n))+1}(k+3)$，

使用引理，

$=H_{R_{k+3}^{\omega }(G_{k+1}(n)+1)}(k+3)=H_{R_{k+2}^{\omega }(G_k(n))}(k+3)$。

于是，$H_{R_{k+2}^{\omega }(G_k(n))}(k+3)$是与$k$无关的常数。分别令$k=G(n)$，$k=0$，得到

$G(n)+3=H_0(G(n)+3)=H_{R_{G(n)+2}^{\omega }(0)}(G(n)+3)=H_{R_2^{\omega }(n)}(3)$，从而证明了

$G(n)=H_{R_2^{\omega }(n)}(3)-3$。

枚举

有了刚刚的结论，我们可以快速地求出一些Goodstein函数的值。以下使用FGH，并且利用了结论$H_{{\omega }^{\alpha }}(n)=f_{\alpha }(n)$：

$G(0)=0$

$G(1)=1$

$G(2)=3$

$G(3)=5$

$G(4)=f_3(3)-3$

$G(5)=f_5(4)-3$

$G(6)=f_6(6)-3$

$G(7)=f_8(8)-3$

$G(8)=f_{\omega +1}(3)-3$

$G(9)=f_{\omega +1}(4)-3$

$G(10)=f_{\omega +1}(6)-3$

$G(11)=f_{\omega +1}(8)-3$

$G(12)=f_{\omega +1}(f_3(3))-3$

$G(13)=f_{\omega +1}(f_4(4))-3$

$G(14)=f_{\omega +1}(f_6(6))-3$

$G(15)=f_{\omega +1}(f_8(8))-3$

$G(16)=f_{{\omega }^3}(3)-3$

$G(17)=f_{{\omega }^4}(4)-3$

$G(18)=f_{{\omega }^6}(6)-3$

$G(19)=f_{{\omega }^8}(8)-3$

$G(20)=f_{{\omega }^{\omega }}(f_3(3))-3$

$\cdots$

一般地，我们有

$G(2\uparrow \uparrow n)=f_{\omega \uparrow \uparrow (n-1)}(3)-3$。

据此可以得到，Goodstein函数的增长率为${\epsilon }_0$。