我們說一個(gè)函數(shù)f(x)的增長率高于g(x)，意思是存在無窮多個(gè)點(diǎn)y，令f(y)>g(y)，我們希望得到一個(gè)盡可能快的函數(shù)f(x)，于是便構(gòu)建了一個(gè)從序數(shù)(ON)到自然數(shù)(N)的映射f:ON→N通過輸入ON中的序數(shù)，我們能夠輸出一個(gè)很大的自然數(shù)，最常用的就是FGH(快速增長層級(jí))，定義如下： f?(x)=x+1 f_β+(x)=f^x_β(x) f_α(x)=f_α[x](x)如果α是極限序數(shù) f^x(y)意思是把一個(gè)函數(shù)f嵌套x次，最里層是f(y)，定義為： f^1(x)=f(x) f^β+(x)=f(f^β(x)) 比如f^3(2)=f(f(f(2))) 除此之外，我們還有別的GH(共同點(diǎn)是它們都是f:ON→N的映射)： SGH(緩慢增長層級(jí))： g?(x)=x g_β+(x)=g_β(x)+ g_α(x)=g_α[x](x) 如未特別說明，以后α均表示極限序數(shù) HH(翻譯為哈代層級(jí))： H?(x)=x H_β+(x)=H_β(x+) H_α(x)=H_α[x](x) MGH(中速增長層級(jí))： m?(x)=x m_β+(x)=m_β(m_β(x)) m_α(x)=m_α[x](x) 然后是基本列的選取，如果你仔細(xì)觀察不難發(fā)現(xiàn)，基本列的選取是所有GH最重要的內(nèi)容，不然的話這就單純只是f:N→N的映射了 基本列是這樣一個(gè)概念： 給定一個(gè)極限序數(shù)α，我們選取一個(gè)序列{γ_n}(大數(shù)中我們希望γ_ω=α，即基本列的長度只能為ω) 滿足： 對(duì)任意n<ω，均有γ_n<α 并且我們?nèi)ˇ胈n(對(duì)任意n<ω)的并集就能得到α 我們用α[n]來表示這樣的相對(duì)于α的γ_n 我們這樣選取基本列： ω[n]=n ω+ω[n]=ω+(ω[n])=ω+n ω*ω[n]=ω*(ω[n])=ω*n (ε0=ω^^ω)[n]=ω^^(ω[n])=ω^^n 大致規(guī)律是遇到ω就把它換成n，當(dāng)然它有更嚴(yán)格的定義，這里能理解就行 這樣，來舉幾個(gè)實(shí)際的例子： f_ω(x)=f_ω[x](x)=f_x(x) f_ω*2(x)=f_ω*2[x](x)=f_ω+x(x) 這里需要注意一點(diǎn) f_x+1(x)≠f_ω+1(x) f_x+1(x+1)只是f_ω(x+1)而已 然后說prss，翻譯過來叫初等序列 初等序列是一個(gè)由標(biāo)準(zhǔn)自然數(shù)組成的序列 形如：(1,2,3) (1,2,2) (1,2,3,4) (1,1,4,5,1,4)都是它的標(biāo)準(zhǔn)項(xiàng) 它的展開是這樣： 給定一個(gè)式子，我們找到它末尾的自然數(shù)，如果是1，那么(x,1)=(x)+1 (1)=1 (1,1)=(1)+1=2 (1,1,1)=(1,1)+1=3(值得一提的，這里選用的是SGH，所以按照這樣它的增長率是g_ε0) 特別地： 如果末尾大于1，稱其末尾為x x以自身為起點(diǎn)，從右至左找到第一個(gè)y令y＜x 此時(shí)我們規(guī)定一個(gè)序列Sk=(y,…,a)，其中a是x的前一個(gè)數(shù)字，即Sk是原序列中以y開頭x結(jié)尾(包含y但不包含x)的序列，然后刪除x，將Sk在原本x的位置復(fù)制n次(n為底數(shù)，即你輸入的自然數(shù)) 我們把這樣的y叫做x的父元素。 比如規(guī)定底數(shù)為3 對(duì)(1,2)，2的父元是1，Sk=1 (1,2)=(1,1,1,1)(末尾復(fù)制3次Sk) (1,2,3,4,3)，3父元為2，Sk=2,3,4 (1,2,3,4,3)=(1,2,3,4,2,3,4,2,3,4,2,3,4) prss的極限形式為(1,2,3,4,5…,n)[n](n為底數(shù)) 增長率是ε0 你可以選擇換個(gè)殼，修改一下末尾為1情況下的定義，令它的增長率變成H_ε0/m_ε0/f_ε0，特別地，序數(shù)中有一個(gè)特殊的概念—不動(dòng)點(diǎn) 稱x是一個(gè)函數(shù)f(x)的不動(dòng)點(diǎn)，當(dāng)且僅當(dāng)f(x)=x 比如我們規(guī)定一個(gè)f:ON→ON的映射： f(0)=ω f(β+)=f(β)+ω f(α)=U β∈α f(β) 第一個(gè)不動(dòng)點(diǎn)是ω^ω，并且存在關(guān)于f的任意大的不動(dòng)點(diǎn)(這個(gè)證明是顯然的) 一般地，我們用α→f(α)來表示f(α)=α的不動(dòng)點(diǎn)(沒特別說明通常指第一個(gè)) 仔細(xì)觀察我們還能發(fā)現(xiàn)一個(gè)定理： 任何高階不動(dòng)點(diǎn)同時(shí)也是低階不動(dòng)點(diǎn) 此外只需要注意，序數(shù)運(yùn)算中，在“左”的運(yùn)算不保持良序 1+ω=ω 2*ω=ω 2^ω=ω 我們會(huì)稱這種情況為發(fā)生了序數(shù)吸收 即“大的和小的放在一起運(yùn)算，小的被大的吸收了” 不會(huì)產(chǎn)生這樣現(xiàn)象的式子叫康托范式