Иерархия Харди

Иерархия Харди, предложенная английским математиком Годфри Харди в 1904 году, представляет собой семейство функций $(H_{\alpha }:\mathbb{N}\to \mathbb{N}{)}_{\alpha <\mu }$, где $\mu$ – это некий большой счётный ординал, такой, что фундаментальные последовательности присвоены всем предельным ординалам, меньшим чем $\mu$. Иерархия Харди определяется следующим образом:

• $H_0(n)=n$
• $H_{\alpha +1}(n)=H_{\alpha }(n+1)$
• $H_{\alpha }(n)=H_{\alpha [n]}(n)$, если и только если $\alpha$ – предельный ординал,

где $\alpha [n]$ обозначает $n$-й элемент фундаментальной последовательности присвоенной предельному ординалу $\alpha$.

Каждый ненулевой ординал $\alpha <{\epsilon }_0=\min \{\beta |\beta ={\omega }^{\beta }\}$ может быть представлен в уникальной нормальной форме Кантора $\alpha ={\omega }^{{\beta }_1}+{\omega }^{{\beta }_2}+\cdots +{\omega }^{{\beta }_{k-1}}+{\omega }^{{\beta }_k},$ где $\omega$ – первый трансфинитный ординал, $\alpha >{\beta }_1\ge {\beta }_2\ge \cdots \ge {\beta }_{k-1}\ge {\beta }_k$.

Если ${\beta }_k>0$, тогда $\alpha$ – предельный ординал и ему может быть присвоена фундаментальная последовательность следующим образом:

$\alpha [n]={\omega }^{{\beta }_1}+{\omega }^{{\beta }_2}+\cdots +{\omega }^{{\beta }_{k-1}}+\{\begin{array}{c}{\omega }^{\gamma }n\text{, если }{\beta }_k=\gamma +1\\ {\omega }^{{\beta }_k[n]}\text{, если }{\beta }_k\text{ - предельный ординал.}\end{array}$

Если $\alpha ={\epsilon }_0$, тогда $\alpha [0]=0$ и $\alpha [n+1]={\omega }^{\alpha [n]}$.

Используя эту систему фундаментальных последовательностей можно определить иерархию Харди до первого числа эпсилон ${\epsilon }_0$.

Для $\alpha <{\epsilon }_0$ иерархия Харди соотносится с быстрорастущей иерархией согласно равенству

$H_{{\omega }^{\alpha }}(n)=f_{\alpha }(n)$

и при $\alpha ={\epsilon }_0$ иерархия Харди "догоняет" быстрорастущую иерархию, то есть

$f_{{\epsilon }_0}(n-1)\le H_{{\epsilon }_0}(n)\le f_{{\epsilon }_0}(n+1)$ для всех $n\ge 1$.

С более мощными системами фундаментальных последовательностей можно ознакомиться на следующих страницах:

• Функция Веблена
• Пси-функции Бухгольца

Для иерархии Харди также верно равенство $H_{\alpha +\beta }(n)=H_{\alpha }(H_{\beta }(n))$.

См. также

• Быстрорастущая иерархия
• Медленнорастущая иерархия

Ссылки

• Hardy,G.H. A theorem concerning the infinite cardinal numbers. Quarterly Journal of Mathematics (1904) vol.35 pp.87–94