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

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

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

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

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

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

${\displaystyle \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.}$

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

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

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

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

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

${\displaystyle f_{\varepsilon _{0}}(n-1)\leq H_{\varepsilon _{0}}(n)\leq f_{\varepsilon _{0}}(n+1)}$ для всех ${\displaystyle n\geq 1}$.

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

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

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