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

Иерархия Харди — определённая иерархия, отображающая ординалы $\alpha$ на набор функций $H_{\alpha}$, сгенерированных из функций Харди $H_\alpha: \mathbb{N} \rightarrow \mathbb{N}$. Для больших ординалов $\alpha$ $H_{\alpha}$ растёт чрезвычайно быстро. Иерархия Харди названа в честь Г. Х. Харди. Иногда она может оказаться более полезной, чем быстрорастущая иерархия; например, её легче связать с числами, получающимися из последовательности Гудштейна, и она лучше подходит для анализа систем последовательностей, таких как матричная система Башику и Y последовательность, чем быстрорастущая иерархия.

Предупреждение

Основная статья: Быстрорастущая Иерархия#Предупреждение
Система фундаментальных последовательностей для предельных ординалов ниже заданного супремума не уникальна, и иерархия Харди сильно зависит от выбора такой системы. В частности, иерархия Харди плохо определена, если конкретный выбор системы фундаментальных последовательностей явно не зафиксирован в контексте. Одна иерархия, иерархия Вайнера, объясняется в статье для быстрорастущей иерархии.

Для фундаментальной иерархии иерархии Вайнера выполняется следующее свойство.

• Для всех $\alpha,\beta < \varepsilon_0$, если нет $\gamma<\alpha$, которое удовлетворяет $\alpha + \beta = \gamma + \beta$, то $H_{\alpha + \beta}(n) = H_{\alpha}(H_{\beta}(n))$
• Для всех $\alpha<\varepsilon_0$, $H_{\omega^\alpha}(n) = f_\alpha(n)$ где $f_\alpha$ - быстрорастущая иерархия.

Это свойство иерархии Вайнера, но иногда его неправильно интерпретируют как свойства для других фундаментальных последовательностей. Например, утверждение о том, что "Когда $\alpha$ является $\varepsilon$-числом, $\alpha = \omega^{\alpha}$ и, следовательно, $H_{\alpha}(n) = H_{\omega^{\alpha}}(n) = f_{\alpha}(n)$" это типичная ошибка.

Определение

Функции Харди определяются следующим образом:

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

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

Функции

Ниже приводится последнее сравнение функций Харди по отношению к неопределённым фундаментальным последовательностям и другим гугологическим нотациям. Обратите внимание, что иерархия Харди плохо определена, когда мы не фиксируем фундаментальные последовательности, и очень быстрорастущая, когда мы их меняем, как мы объяснили в предупреждении. Следовательно, это вычисление не обязательно выполняется для конкретного выбора фундаментальных последовательностей.

$H_0(n) = n$

$H_1(n) = n+1$

$H_2(n) = n+2$

$H_m(n) = n+m$

$H_\omega(n) = 2n$

$H_{\omega+1}(n) = 2(n+1) = 2n+2$

$H_{\omega+2}(n) = 2(n+2) = 2n+4$

$H_{\omega+m}(n) = 2(n+m) = 2n + 2m$

$H_{\omega 2}(n) = 4n$

$H_{(\omega 2)+m}(n) = 4(n+m) = 4n + 4m$

$H_{\omega 3}(n) = 8n$

$H_{(\omega 3)+m}(n) = 8(n+m) = 8n + 8m$

$H_{\omega m}(n) = (2^m)n$

$H_{\omega m+x}(n) = 2^m(n+x) = (2^m)n + (2^m)x$

$H_{\omega^{2}}(n) = 2^n \cdot n$

$H_{\omega^{2}+1}(n) = 2^{n+1} \cdot (n+1)$

$H_{\omega^{2}+2}(n) = 2^{n+2} \cdot (n+2)$

$H_{\omega^{2}+\omega}(n) = 2^{2n} \cdot (2n)$

$H_{\omega^{2}+\omega 2}(n) = 2^{4n} \cdot (4n)$

$H_{(\omega^{2}) 2}(n) = 2^{2^n \cdot n} \cdot (2^n \cdot n)$

$H_{(\omega^{2}) 3}(n) = 2^{2^{2^n \cdot n} \cdot (2^n \cdot n)} \cdot (2^{2^n \cdot n} \cdot (2^n \cdot n))$

$H_{(\omega^{2}) m}(n) = 2^{H_{(\omega^2) m-1}(n)} \cdot (H_{(\omega^2) m-1}(n))$

$H_{\omega^{3}}(n) \approx n \uparrow\uparrow n$

$H_{\omega^{4}}(n) \approx n \uparrow\uparrow\uparrow n$

$H_{\omega^{5}}(n) \approx n \uparrow\uparrow\uparrow\uparrow n$

$H_{\omega^{m}}(n) \approx \{n,n,m-1\}$

$H_{\omega^{\omega}}(n) \approx \{n,n,n-1\}$

$H_{\omega^\omega+1}(n) \approx \{n,n,n\}$

$H_{\omega^{\omega}+2}(n) \approx \{n,n,n+1\}$

$H_{\omega^{\omega}+\omega}(n) \approx \{n,n,2n\}$

$H_{\omega^{\omega}+\omega^{2}}(n) \approx \{n,n,2^n \cdot n\}$

$H_{(\omega^{\omega}) 2}(n) \approx \{n,n,\{n,n,n\}\}$

$H_{(\omega^{\omega}) 3}(n) \approx \{n,n,\{n,n,\{n,n,n\}\}\}$

$H_{\omega^{\omega+1}}(n) \text{ или же } H_{(\omega^{\omega}) \omega}(n) \approx \{n,n,1,2\}$

$H_{\omega^{\omega+2}}(n) \approx \{n,n,2,2\}$

$H_{\omega^{\omega+m}}(n) \approx \{n,n,m,2\}$

$H_{\omega^{\omega 2}}(n) \approx \{n,n,n,2\}$

$H_{\omega^{\omega 2+1}}(n) \approx \{n,n,1,3\}$

$H_{\omega^{\omega 2+2}}(n) \approx \{n,n,2,3\}$

$H_{\omega^{\omega m+2}}(n) \approx \{n,n,m,3\}$

$H_{\omega^{\omega m}}(n) \approx \{n,n,n,m\}$

$H_{\omega^{\omega m+x}}(n) \approx \{n,n,x,m+1\}$

$H_{\omega^{\omega^{2}}}(n) \approx \{n,n,n,n\}$

$H_{\omega^{\omega^{3}}}(n) \approx \{n,n,n,n,n\}$

$H_{\omega^{\omega^{m-2}}}(n) \approx \{n,m (1) 2\} = m \& n$

$H_{\omega^{\omega^{m}}}(n) \approx \{n,m+2 (1) 2\}$

$H_{\omega^{\omega^{\omega}}}(n) \approx \{n,n+2 (1) 2\}$

Историческая справка

Иерархия Харди и функции Харди впервые введены и определены Стэнли С. Уинтером в 1972 году. Иерархия, которую он первоначально определил, была только в рамках $\varepsilon_0$ (это похоже на иерархию Вайнера). Вайнер описал иерархию $\{\mathcal{H}_\beta\}_{\beta<\varepsilon_0}$ как удобное уточнение иерархии Вайнера.

Иерархия была названа в честь Годфри Х. Харди, потому что идея определения функций $h_{\alpha}$ взята из его статьи 1904 года "ТЕОРЕМА, КАСАЮЩАЯСЯ БЕСКОНЕЧНЫХ КАРДИНАЛЬНЫХ ЧИСЕЛ". В статье 1904 года Харди продемонстрировал набор вещественных чисел с мощностью $\aleph_1$, и он показал конструктивные последовательности чисел, параметризованных ординалами до $\aleph_1$, используя идею воспроизведения.

Обратите внимание, что, несмотря на то, что последовательности можно конструировать, необходимы фундаментальные последовательности "всех" счётных ординалов.