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

Иерархия Харди, предложенная английским математиком Годфри Харди в 1904 году, представляет собой семейство функций $(H_{\alpha }:\mathbb {N} \rightarrow \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 <\varepsilon _{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}\geq \beta _{2}\geq \cdots \geq \beta _{k-1}\geq \beta _{k}$.

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

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

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

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

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

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

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

$f_{\varepsilon _{0}}(n-1)\leq H_{\varepsilon _{0}}(n)\leq f_{\varepsilon _{0}}(n+1)$ для всех $n\geq 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