Быстрорастущая иерархия

Быстро-растущая иерархия — это семейство быстро растущих функций, индексированных ординалами.

Дефиниция

Быстро-растущая определяется следующими правилами

(1) $f_{0}(n)=n+1$ (в общем случае $f_{0}(n)$ может быть любой растущей функцией),

(2) $f_{\alpha +1}(n)=f_{\alpha }^{n}(n)=\underbrace {f(f(\cdots (f(f(} _{n\quad f's}n))\cdots ))$,

(3) $f_{\alpha }(n)=f_{\alpha [n]}(n)$ если $\alpha$ предельный ординал,

где $\alpha [n]$ n-ый элемент фундаментальной последовательности, установленной для некого предельного ординала $\alpha$.

Существуют различные версии быстро-растущей иерархии, однако наиболее известной является иерархия Вайнера, в которой фундаментальные последовательности для предельных ординалов, записанных в нормальной форме Кантора, определяется следующими правилами

(4) $\omega [n]=n$,

(5) $(\omega ^{\alpha _{1}}+\omega ^{\alpha _{2}}+\cdots +\omega ^{\alpha _{k-1}}+\omega ^{\alpha _{k}})[n]=\omega ^{\alpha _{1}}+\omega ^{\alpha _{2}}+\cdots +\omega ^{\alpha _{k-1}}+\omega ^{\alpha _{k}}[n]$

для $\alpha _{1}\geq \alpha _{2}\geq \cdots \geq \alpha _{k}$,

(6) $\omega ^{\alpha +1}[n]=\omega ^{\alpha }n$,

(7) $\omega ^{\alpha }[n]=\omega ^{\alpha [n]}$ если $\alpha$ предельный ординал,

(8) $\varepsilon _{0}[0]=0$ и $\varepsilon _{0}[n+1]=\omega ^{\varepsilon _{0}[n]}=\omega \uparrow \uparrow n$.

Примеры

$f_{1}(n)=2\times n$,

$f_{2}(n)=2^{n}\times n$

Для функций, индексированных конечными ординалами $\alpha >2$ верно

$f_{m}(n)>2\uparrow ^{m-1}n$,

в частности при n=10

$f_{3}(10)=f_{2}^{10}(10)=\underbrace {10^{10^{10^{\cdots {^{10^{10^{3.489}}}}}}}} _{10\quad {\text{десяток}}}\approx 10\uparrow \uparrow 11$,

$f_{4}(10)=f_{3}^{10}(10)=\left.{\begin{matrix}&&\underbrace {10^{10^{10^{\cdots {^{10^{10^{3.489}}}}}}}} \\&&\underbrace {10^{10^{10^{\cdots {^{10^{10^{3.489}}}}}}}} \\&&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&&\underbrace {10^{10^{10^{\cdots {^{10^{10^{3.489}}}}}}}} \\&&10\quad {\text{десяток}}\end{matrix}}\right\}{\text{10 нижних фигурных скобок}}\approx 10\uparrow \uparrow \uparrow 11$

$f_{m}(10)\approx 10\uparrow ^{m-1}11$.

Таким образом, уже первый трансфинитный ординал $\omega$ соответствует пределу стрелочной нотации Кнута

$f_{\omega }(10)\approx 10\uparrow ^{9}11=10\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 11$.

Знаменитое число Грэма меньше, чем $f_{\omega +1}(64)$.

Стрелочная нотация Конвея имеет предел $\omega ^{2}$

$f_{\omega ^{2}}(n)\approx \underbrace {n\rightarrow n\rightarrow n\cdots \rightarrow n} _{n+1\quad \rightarrow }$.

Предел нотации для линейного массива Бауэрса $\omega ^{\omega }$.

Данная выше дефиниция определяет быстро-растущую иерархию до $\varepsilon _{0}=\omega \uparrow \uparrow n$. Для дальнейшего роста можно использовать функцию Веблена и другие, еще более мощные нотации для ординалов.

См. также

Стрелочная нотация Кнута

Обозначения Конвея

Число Грэма

Порядковое число

Ссылки

• Buchholz, W.; Wainer, S.S (1987). "Provably Computable Functions and the Fast Growing Hierarchy". Logic and Combinatorics, edited by S. Simpson, Contemporary Mathematics, Vol. 65, AMS, 179-198.
• Cichon, E. A.; Wainer, S. S. (1983), "The slow-growing and the Grzegorczyk hierarchies", The Journal of Symbolic Logic, 48 (2): 399—408, doi:10.2307/2273557, ISSN 0022-4812, MR 0704094
• Gallier, Jean H. (1991), "What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory", Ann. Pure Appl. Logic, 53 (3): 199—260, doi:10.1016/0168-0072(91)90022-E, MR 1129778 PDF's: part 1 2 3. (In particular part 3, Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
• Girard, Jean-Yves (1981), "Π¹₂-logic. I. Dilators", Annals of Mathematical Logic, 21 (2): 75—219, doi:10.1016/0003-4843(81)90016-4, ISSN 0003-4843, MR 0656793
• Löb, M.H.; Wainer, S.S. (1970), "Hierarchies of number theoretic functions", Arch. Math. Logik, 13. Correction, Arch. Math. Logik, 14, 1971. Part I doi:10.1007/BF01967649, Part 2 doi:10.1007/BF01973616, Corrections doi:10.1007/BF01991855.
• Prömel, H. J.; Thumser, W.; Voigt, B. "Fast growing functions based on Ramsey theorems", Discrete Mathematics, v.95 n.1-3, p. 341-358, Dec. 1991 doi:10.1016/0012-365X(91)90346-4.
• Wainer, S.S (1989), "Slow Growing Versus Fast Growing". Journal of Symbolic Logic 54(2): 608-614.