增长层级

增长层级(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等等。