增长层级

增长层级(Growing Hierarchy,GH)是一种函数族$f:\mathrm{O}\mathrm{r}\mathrm{d}\mathrm{\to }\mathbb{\mathbb{N}}\mathrm{\to }\mathbb{\mathbb{N}}$，对于每个序数$\alpha$，$f_{\alpha }$是一个从自然数到自然数的函数。

不同增长率的函数能和它们建立起大致的对应关系。因此，增长层级常被用于分析函数的增长率。

常用的增长层级有4种，分别为FGH、MGH、HH和SGH。其中最常用的是FGH。

在大数数学中的应用

我们知道，大数数学的目的是造出越来越巨大的自然数。为了这个目标，我们需要构造出增长的越来越快的大数函数。实际上，我们有以下两种办法来做到这件事情，即迭代和对角化：

• 迭代，即对于已有函数$\mathrm{f}\mathrm{(}\mathrm{x}\mathrm{)}$,我们构造出函数$\mathrm{g}\mathrm{(}\mathrm{x}\mathrm{)}$增长速度快于f(x).注意到迭代的方法显然不止一种。比方说，让$\mathrm{g}\mathrm{(}\mathrm{x}\mathrm{)}\mathrm{=}\mathrm{f}\mathrm{(}\mathrm{f}\mathrm{(}\mathrm{f}\mathrm{(}\mathrm{\cdots }\mathrm{(}\mathrm{x}\mathrm{)}\mathrm{\cdots }\mathrm{)}\mathrm{)}\mathrm{)},\mathrm{x}$层。这是一种迭代方法。还可以让$\mathrm{g}\mathrm{(}\mathrm{x}\mathrm{)}\mathrm{=}\mathrm{f}\mathrm{(}\mathrm{x}\mathrm{+}\mathrm{1}\mathrm{)}$等等.
• 对角化，即对于已有的ω个增长速度递增的函数，我们按照增长速度由小到大排序为${\mathrm{f}}_{\mathrm{1}}\mathrm{(}\mathrm{x}\mathrm{)},{\mathrm{f}}_{\mathrm{2}}\mathrm{(}\mathrm{x}\mathrm{)},{\mathrm{f}}_{\mathrm{3}}\mathrm{(}\mathrm{x}\mathrm{)},\mathrm{\cdots }$,我们构造出函数$\mathrm{g}\mathrm{(}\mathrm{x}\mathrm{)}\mathrm{=}{\mathrm{f}}_{\mathrm{x}}\mathrm{(}\mathrm{x}\mathrm{)}$.注意到g(x)的增长速度快于任意的${\mathrm{f}}_{\mathrm{n}}\mathrm{(}\mathrm{x}\mathrm{)}$.

因此，我们只需要从一个最初的函数出发，通过不断地迭代和对角化，就可以得到越来越快的函数.

现在让我们考察序数，会发现，序数存在以下两个性质：

• 对任意序数α，α的后继依然是一个序数且大于α.
• 对ω个递增序数构成的序列S来说，存在一个β是序数且满足β是S的上确界（上界要求大于等于内部所有元素，上确界是最小上界）。或者说，这里的S是β的一条基本列.

因此，我们可以从0出发，通过不断地取后继和取上确界，我们可以得到越来越大的序数.

我们会发现，构造大数函数的方法和序数的性质之间存在某种意义的对应。那么，我们可不可以直接根据序数，生成大数函数呢？答案是可以的。我们需要完成以下三件事：

• 对序数0，它要和一个最基础的函数对应。
• 对一个后继序数α'(α的后继)，我们需要找到α，然后把α对应的函数进行迭代，所得到的新函数就是α'对应的函数。
• 对一个极限序数β，我们需要找到β的基本列，然后把基本列所有元素对应的函数进行对角化，得到的新函数就是β对应的函数。

但注意到这里还有一个问题：一个极限序数的基本列不止一种，那么，我们如何确定应该选取哪一条基本列呢？这个时候就需要序数记号出马了。序数记号为其极限之下的每个序数指定了唯一的标准基本列。

有了序数记号之后，我们就可以放心的运用对应关系，直接把序数转换成大数函数了。把序数转换成大数函数的工具就是增长层级。根据迭代的方法不同，增长层级也有很多种，包含FGH,HH,MGH,SGH等等。

不同增长层级的对比

MGH相比FGH，下标+1的方式仅由“嵌套n(自变量)层”变为“嵌套2层”。因此，MGH的下标每加一次$\omega$,就能将函数嵌套$2^n$层，实现略大于FGH中下标+1的作用。

对于使得$m_{\alpha }(n)=f_{\beta }(n)$的$\alpha$和$\beta$，我们有

$m_{\alpha +n(n\in \omega )}(x)<f_{\beta +1}(x)<m_{\alpha +\omega }(x)<f_{\beta +1}(2^x)$

因而MGH与FGH在${\omega }^{\omega }$处Catching。

HH为“下标+1则自变量+1”，显然有$H_{\alpha }(H_{\beta }(n))=H_{\alpha +\beta }(n)$。

于是当$H_{\alpha }(n)=f_{\beta }(n)$时，

$H_{\alpha +1}(n)=f_{\beta }(n+1)$，$H_{\alpha +\alpha }(n)=f_{\beta }(f_{\beta }(n))$，$H_{\alpha \times \omega }(n)=f_{\beta +1}(n)$

而$H_1(n)=f_0(n)=n+1$。于是我们又有以下推论：

相同基本列下，对于$\beta \le \alpha <{\epsilon }_0$，有$H_{{\omega }^{\alpha }}(n)=f_{\alpha }(n)$，$H_{{\omega }^{\alpha }+{\omega }^{\beta }}(n)=f_{\alpha }(f_{\beta }(n))$

因而HH与FGH在${\epsilon }_0$处Catching。

我们最后再来看SGH，其下标+1仅仅是“函数值+1”，因而SGH的增长十分依赖于序数自身的结构及基本列的选取，所以其增长地较为缓慢，且在较小尺度上和FGH没有明显的对应关系。

SGH与FGH在$\psi ({\mathrm{\Omega }}_{\omega })$处Catching。在这之后，直接分析记号的序数结构与分析增长率变得几乎没有区别。

对照表

\( \begin{array} {  c | c | c  } \rm FGH & \rm MGH & \rm HH & \rm SGH & \rm EXP & -\\ \hline  &  & H_0 & g_\omega & x\\ f_0 & m_0 & H_1 & g_{\omega +1} & x+1\\ f_0(f_0) & m_1 & H_2 & g_{\omega +2} & x+2\\ f_0^4 & m_2 & H_4 & g_{\omega +4} & x+4\\ f_0^8 & m_3 & H_8 & g_{\omega +8} & x+8\\ f_1 & \matrix{\underset{x+2^x}{\color{red}{ m_\omega}}} & H_\omega & g_{\omega \times 2} & 2x \\ f_1(f_0) & {\color{red}{ m_\omega}} & H_{\omega +1} & g_{\omega \times 2 +2} & 2x +2\\ f_1(f_0(f_0)) & {\color{red} {m_\omega}} & H_{\omega +2} & g_{\omega \times 2 +4} & 2x +4\\ f_1(f_1) & {\color{red} {m_\omega}} & H_{\omega \times 2} & g_{\omega \times 4} & 4x\\ f_1(f_1(f_0)) & {\color{red} {m_\omega}} & H_{\omega \times 2 +1} & g_{\omega \times 4 +4} & 4x +4\\ f_1(f_1(f_1)) & {\color{red} {m_\omega}} & H_{\omega \times 3} & g_{\omega \times 8} & 8x\\ f_2 & {\color{green} {m_\omega}} & H_{\omega ^2} & {\color{green}{ g_{\omega^2}\sim g_{\omega^n}}} & x\cdot 2^x\\ f_2(f_1) & {\color{green}{ m_\omega}} & H_{\omega ^2 +\omega} & {\color{green} {g_{\omega^2}\sim g_{\omega^n}}} & x\cdot 2^{2x+1}\\ f_2(f_2) & {\color{green} {m_{\omega +1}}} & H_{\omega ^2 \times 2} & {\color{green} {g_{\omega^\omega}\sim g_{\omega^{\omega^n}}}} & x\cdot 2^{x\cdot (2^x+1)}\\ f_3 & \matrix{\underset{>x\uparrow\uparrow 2^x}{\color{red} {m_{\omega \times 2}}}} & H_{\omega ^3} & \matrix{\underset{x\uparrow\uparrow x}{\color{green} {g_{\varepsilon_0}}  }} & >x\uparrow\uparrow x \\ f_3(f_1) & {\color{red} {m_{\omega \times 2}}} & H_{\omega ^3 +\omega} & \matrix{\underset{>x\uparrow\uparrow 2x-1}{\color{green}{ g_{\varepsilon_1} }}} & >x\uparrow\uparrow 2x \\ f_3(f_2) & {\color{green} {m_{\omega \times 2}}} & H_{\omega ^3 +\omega ^2} & {\color{green} {g_{\varepsilon_\omega} \sim g_{\varepsilon_{\omega^n} }}} & >x\uparrow\uparrow (x\cdot 2^x) \\ f_3(f_3) & \matrix{\underset{>x\uparrow\uparrow x\uparrow\uparrow 2^x}{\color{red} {m_{\omega \times 2 +1}}}} & H_{\omega ^3 \times 2} & {\color{green} {g_{\varepsilon_{\varepsilon_0}} }} & >x\uparrow\uparrow x\uparrow\uparrow x &{\rm tritri}=3\uparrow\uparrow\uparrow3\\ f_3(f_3(f_2)) & {\color{green} {m_{\omega \times 2 +1}}} & H_{\omega ^3 \times 2 +\omega^2} & {\color{green} {g_{\varepsilon_{\varepsilon_\omega }}\sim g_{\varepsilon_{\varepsilon_{\omega^n} }} }} & >x\uparrow\uparrow x\uparrow\uparrow (x\cdot 2^x) \\ f_3(f_3(f_3)) & \matrix{\underset{>x\uparrow\uparrow\uparrow 5}{\color{red} {m_{\omega \times 2 +2}}}} & H_{\omega ^3 \times 3} & {\color{green}{ g_{\varepsilon_{\varepsilon_{\varepsilon_0}}}} } & >x\uparrow\uparrow\uparrow 4 \\ f_4 & \matrix{\underset{>x\uparrow\uparrow\uparrow 2^x}{\color{red} {m_{\omega \times 3}}}} & H_{\omega ^4} & {\color{green} {g_{\zeta_0}} } & >x\uparrow\uparrow\uparrow (x+1)\\ f_4(f_0) & {\color{red} {m_{\omega \times 3}}} & H_{\omega ^4+1} & {\color{green} {g_{\varepsilon_{\zeta_0+1}} }} & >x\uparrow\uparrow\uparrow (x+2) \\ f_4(f_1) & {\color{red} {m_{\omega \times 3}}} & H_{\omega ^4+\omega } & {\color{green}{ g_{\zeta_1}} } & >x\uparrow\uparrow\uparrow 2x \\ f_4(f_2) & {\color{green} {m_{\omega \times 3}}} & H_{\omega ^4+\omega^2 } & {\color{green} {g_{\zeta_\omega }\sim g_{\zeta_{\omega^n} } }} & >x\uparrow\uparrow\uparrow (x\cdot 2^x) \\ f_4(f_3) & {\color{green}{ m_{\omega \times 3}}} & H_{\omega ^4+\omega^3 } & {\color{green} {g_{\zeta_{\varepsilon _0}} } } & >x\uparrow\uparrow\uparrow x\uparrow\uparrow x \\ f_4(f_4) & {\color{red} {m_{\omega \times 3+1}}} & H_{\omega ^4\times 2 } & {\color{green}{ g_{\zeta_{\zeta _0} } }} & >x\uparrow\uparrow\uparrow x\uparrow\uparrow\uparrow x \\ f_5 & {\color{red} {m_{\omega \times 4}}} & H_{\omega ^5 } & {\color{green} {g_{\eta _0} } } & >x\uparrow\uparrow\uparrow\uparrow x & G(1)=3\uparrow^4 3\\ f_5(f_4) & {\color{green} {m_{\omega \times 4}}} & H_{\omega ^5 } & {\color{green} {g_{\eta_{\zeta _0}} } } & >x\uparrow^4 x\uparrow^3 x\\ f_5(f_5) & {\color{red}{ m_{\omega \times 4+1}}} & H_{\omega ^5\times 2 } & {\color{green} {g_{\eta_{\eta _0}}}  } & >x\uparrow^4 x\uparrow^4 x\\ f_6 & {\color{red}{ m_{\omega \times 5}}} & H_{\omega ^6 } & {\color{green} {g_{\varphi(4,0) }}  } & >x\uparrow^5 x\\ f_7 & {\color{red} {m_{\omega \times 6}}} & H_{\omega ^7 } & {\color{green} {g_{\varphi(5,0) }}  } & >x\uparrow^6 x\\ \matrix{\underset{n>2,n\in \mathbb{N} }{f_n}}  & {\color{red} {m_{\omega \times (n-1)}}} & H_{\omega ^n } & {\color{green}{ g_{\varphi(n-2,0) }}  } & >x\uparrow^{n-1} x\\ f_\omega  & \matrix{\underset{>x\uparrow^x x}{\color{red}{ m_{\omega^2}}}} & H_{\omega ^\omega  } & \matrix{\underset{>x\uparrow^x x}{\color{red} {g_{\varphi(\omega ,0) }}} } & >x\uparrow^{x-1} x\\  \end{array} \)