基本列和FGH

在上篇文章里，我们讲了什么是基数和序数。大于等于ω的序数被称为超限序数。超限序数中还有一种特殊的极限序数，它们可以写成一串序数按照相同规律取到无穷时的极限。比如ω就是{1，2，3，4……}的极限，ω×2就是{ω，ω+1，ω+2，ω+3……}的极限，ω²就是{ω，ω×2，ω×3……}的极限，ω^ω就是{ω，ω²，ω³……}的极限，ε₀就是{ω，ω^ω，ω^ω^ω……}的极限。像ω+1，ω+2这种不能写成极限形式的就不是极限序数。括号里面的那一串序数就是对应的极限序数的基本列。 前面我们说过，超限序数的运算是不满足交换律的，也就是说2×ω≠ω×2。我们可以从基本列的角度来看看这是为什么，2×ω的基本列是{2，4，6，8……}，也就是说2×ω是偶数列的极限。显然偶数列的极限和自然数列的极限都应该是ω，所以2×ω=ω≠ω×2。基本列是我们分析序数的一个重要的工具，能写出一个极限序数的基本列才算理解了这个序数的结构。 为了研究那些大到无法用科学计数法表示的大数，我们需要一个强有力的新工具。快速增长层级(FGH)就是这样的一种东西，它用序数去描述那些大数函数的增长率。其实除了FGH之外，还有慢速增长层级(SGH)，中速增长层级(MGH)，哈代(HH)，感兴趣的可以自行了解，我这里就不多赘诉了。它们都是用序数去描述函数增长快慢，其中FGH下增长率每增加1，对函数的增长率提升是最大的。FGH的规则是这样的： f₀(n)=n+1 f₋α+1(n)=f₋α(f₋α(f₋…(f₋α(n)…)))，套娃n层。 其中函数下标代表着该函数的FGH增长率，也就是说f(n)=n+1的FGH增长率为0。再看一下第二条规则，可以试想一下增长率为1的函数是什么样的。容易发现，当我们把f₀(n)=n+1套娃自己层后就得到了f₁(n)=n+n=2×n，这个函数的FGH增长率就是1了。继续把f₁(n)套娃自己n层，我们会得到f₂(n)=(2^n)×n，它的FGH增长率为2。再次把f₂(n)套娃自己n层，我们就得到了f₃(n)，它的FGH增长率为3。 好了，我们发现了加法的增长率为0，乘法运算的增长率为1，乘方运算的增长率为2，重幂运算的增长率为3，把重幂继续套娃就能得到增长率为4的函数，随着运算等级的增加，FGH增长率也会不断增加。那么现在问题来了，如果有一个函数F(n)=n[n]n，即两个n之间进行n级运算(关于运算等级的扩展，我下期具体讲一下高德纳箭头和超运算)，那么这个F(n)的增长率是多少？根据前面的规律，几级运算增长率就是几减一，可是现在的问题是运算等级也变成了自变量。运算等级作为自变量(定义域为所有自然数)，就意味着它可以取到任意大。所以为了衡量这个可以比任意自然数都大的增长率，我们很自然的就想到了之前讲过的超限序数ω。F(n)的FGH增长率就是ω。 现在，我们把F(n)再套娃自己n层，得到 F₁(n)。很明显对于同样的n来说，必然有F₁(n)≥F(n)。所以F₁(n)的增长率必然要大于F(n)的ω，而根据上面FGH的第二条，可以发现F₁(n)的增长率为ω+1。这也从侧面证明了ω+1确实是一个比ω更大的序数。