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

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

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

Читатель должен быть очень внимателен к тому, что на личном веб-сайте, в видео и блогах пользователей много неправильных "введений", хотя, к сожалению, новички предпочитают именно их. Поскольку математические понятия, такие как ординалы и фундаментальные последовательности, довольно абстрактны и с ними трудно обращаться точным образом, люди склонны давать их интуитивные описания, которые для начинающих выглядят проще и круче, чем точные объяснения. Однако такие "введения" часто содержат серьёзные ошибки, поскольку авторы также изучали их по другим интуитивным описаниям вместо точных определений. Важным моментом является то, что точное описание их на самом деле необходимо для понимания быстрорастущей иерархии. Причина, по которой точные описания выглядят сложными, заключается не в том, что они просто плохо написаны или избыточны, а в том, что понятия на самом деле довольно сложны, хотя такие неправильные "введения" иногда объясняют их как простые понятия.

Определение

Быстрорастущие функции

Быстрорастущая функция состоит из ординальной системы $\mu$ и системы фундаментальной последовательности $S:\mu\cap\textrm{Lim} \rightarrow (\mathbb N\rightarrow\mu)$, где $S(\alpha)(n)$ обозначает $\alpha[n]$, а $\textrm{Lim}$ обозначает класс предельных ординалов. Семантика следующая:

• $f_{0}(n) = n+1$
• $f_{\alpha+1}(n) = f^n_\alpha(n)$, где $f^n$ обозначает итерацию функции
• $f_{\alpha}(n) = f_{\alpha[n]}(n)$, если $\alpha$ — предельный ординал

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

Некоторые авторы вместо этого устанавливают $f_{\alpha+1}(n) = f^{n+1}_\alpha(n)$ для второй строки.

Чтобы быстрорастущая иерархия была полезна гугологам, она также должна удовлетворять свойству, которое для всех $\alpha < \beta < \mu$, $f_\alpha$ в конечном итоге доминирует над $f_\beta$, хотя это не обязательно верно для общей системы фундаментальных последовательностей. Читатель должен быть осторожен, так как многие гугологи не знают этого факта и неявно предполагают это свойство даже тогда, когда в контексте нет доказательств конкретной системы фундаментальной последовательности. Смотрите также Ординал Чёрча-Клини#Быстрорастущая иерархия для ознакомления с распространёнными заблуждениями, связанными с быстрорастущей иерархией.

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

Быстрорастущая иерархия $\{\mathcal{F}_\alpha\}_{\alpha<\mu}$ определяется как Иерархия Гжегорчика. Для каждого ординала $\alpha<\mu$ набор $\mathcal{H}_\alpha$ числовых функций определяется как наименьший класс, удовлетворяющий следующим условиям:

1. Это содержит
   • нулевую константу $0$, обозначаемую как $z: \mathbb{N}^0 \to\mathbb{N}$,
   • функцию-преемника $s(n)=n+1$,
   • проекционную функцию $p_i^m(x_1,\dots,x_m)=x_i$ и
   • быстрорастущую функцию $f_\alpha$.
2. Он закрыт под
   • заменой, $g(f_1,\dots,f_n)$ для $g,f_1,\dots,f_n\in\mathcal{F}_\alpha$ и
   • ограниченной рекурсией, $h(n+1,x_1,\dots,x_n)=f(n,x_1,\dots,x_n,h(n,x_1,\dots,x_n))$, $h(0,x_1,\dots,x_n)=g(x_1,\dots,x_n)$ для $f,g\in\mathcal{F}_\alpha$ и $h(n ,x_1,\dots,x_n)\leq M(n,x_1,\dots,x_n)$ для некоторого $M \in \mathcal{F} _\alpha$

Общий случай, когда $f_0$ — любая возрастающая функция, образует иерархию быстрых итераций.

Системы фундаментальных последовательностей

Смотрите также: Список систем фундаментальных последовательностей

Иерархия Вайнера

Определения быстрорастущей иерархии и выбор фундаментальных систем последовательностей различаются у разных авторов, поэтому в целом проблематично говорить о быстрорастущей иерархии. Однако наиболее известной БРИ является иерархия Вайнера, которая имеет $\mu =\varepsilon _{0}+1$ и систему ФП, определённую следующим образом:

• $\omega[n] = n$
• $\omega^{\alpha+1}[n]=\omega^{\alpha}n$ (где $\omega ^{\alpha }n=\omega ^{\alpha }+\omega ^{\alpha }+\cdots +\omega ^{\alpha }+\omega ^{\alpha }$ с n копиями $\omega^{\alpha}$)
• $\omega^{\alpha}[n]=\omega^{\alpha[n]}$ тогда и только тогда, когда $\alpha$ является предельным ординалом
• $(\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 - 1} \geq \alpha_k$
• $\varepsilon_0[0]=0$ (альтернативно $1$)
• $\varepsilon _{0}[n+1]=\omega ^{\varepsilon _{0}[n]}=\omega \uparrow \uparrow (n-1)$ (альтернативно $\omega \uparrow \uparrow n$)

Например, основная последовательность для $\omega^{\omega}$ — $1,\omega ,\omega ^{2},\omega ^{3},\cdots$. Когда авторы без пояснений говорят о "быстрорастущей иерархии", обычно имеется в виду иерархия Вайнера.

Известно, что функции в иерархии Вайнера вычислимы, поскольку вся система может быть закодирована в ординальной нотации, связанной с итерированной нормальной формой Кантора с дополнительными структурами.

Значения

Ниже приведены некоторые функции в иерархии Вайнера и иерархии Веблена в сравнении с другими гугологическими нотациями. Есть несколько вещей, на которые следует обратить внимание:

• Отношения, обозначенные $f_\alpha(n) > g(n)$, выполняются для достаточно больших $n$, не обязательно всех $n$ (т.е. $f_\alpha$ в конечном итоге доминирует над $g$).
• $m$ указывает на любое положительное целое число.
• $\uparrow$ означает стрелочную нотацию.
• $\textrm{Ack}$ указывает на одноаргументную функцию Аккермана Харви Фридмана $\textrm{Ack} (n)$.
• $\lbrace \rbrace$ означает BAN.
• В этом разделе мы используем несколько систем фундаментальных последовательностей, например, для нормальной формы Кантора и для функции Веблена. Поскольку они явно не указаны, мы не знаем, какие системы подходят для этих результатов. Поэтому будьте осторожны, чтобы вычисления не сработали при попытке применить их к конкретной системе.

$f_{0}(n) = n+1$

$f_1(n) = f_0^n(n) = ( \cdots ((n + 1) + 1) + \cdots + 1) = n + n = 2n$

$f_2(n) = f_1^n(n) = 2(2(\ldots 2(2n))) = 2^n n > 2^n$

$f_3(n) \ge 2^nn((2^{2^nn})\uparrow\uparrow (n-1)) \ge 2\uparrow\uparrow n = n\times(2\uparrow\uparrow n)$

$f_4(n) \ge f_3(n)\uparrow\uparrow\uparrow n \ge 2\uparrow\uparrow\uparrow n$

$f_m(n) \ge f_{m-1}(n)\uparrow^{m-1}n \ge 2\uparrow^{m-1} n$

$f_\omega(n) \ge f_\omega(n-1)\uparrow^{n-1}n \ge 2\uparrow^{n-1} n = \text{Ack}(n)$

$f_{\omega+1}(n) > \lbrace n,n,1,2 \rbrace$

$f_{\omega+2}(n) > \lbrace n,n,2,2 \rbrace$

$f_{\omega+m}(n) > \lbrace n,n,m,2 \rbrace$

$f_{\omega 2}(n) > \lbrace n,n,n,2 \rbrace$

$f_{\omega 3}(n) > \lbrace n,n,n,3 \rbrace$

$f_{\omega m}(n) > \lbrace n,n,n,m \rbrace$

$f_{\omega^{2}} (n) > \lbrace n,n,n,n \rbrace$

$f_{\omega^{3}}(n) > \lbrace n,n,n,n,n \rbrace$

$f_{\omega^{m}}(n) > \lbrace n,m+2 [2] 2 \rbrace$

$f_{\omega^{\omega}}(n) > \lbrace n,n+2 [2] 2 \rbrace > \lbrace n,n [2] 2 \rbrace$

$f_{\omega^{\omega}+1}(n) > \lbrace n,n,2 [2] 2 \rbrace$

$f_{\omega^{\omega}+2}(n) > \lbrace n,n,3 [2] 2 \rbrace$

$f_{\omega^{\omega}+m}(n) > \lbrace n,n,m+1 [2] 2 \rbrace$

$f_{\omega^{\omega}+\omega}(n) > \lbrace n,n,n+1 [2] 2 \rbrace > \lbrace n,n,n [2] 2 \rbrace$

$f_{\omega^{\omega}+\omega+1}(n) > \lbrace n,n,1,2 [2] 2 \rbrace$

$f_{\omega^{\omega}+\omega2}(n) > \lbrace n,n,n,2 [2] 2 \rbrace$

$f_{\omega^{\omega}+\omega^{2}}(n) > \lbrace n,n,n,n [2] 2 \rbrace$

$f_{{\omega^{\omega}}2}(n) > \lbrace n,n [2] 3 \rbrace$

$f_{{\omega^{\omega}}3}(n) > \lbrace n,n [2] 4 \rbrace$

$f_{{\omega^{\omega}}m}(n) > \lbrace n,n [2] m+1 \rbrace$

$f_{\omega^{\omega+1}}(n) > \lbrace n,n [2] n+1 \rbrace > \lbrace n,n [2] n \rbrace$

$f_{\omega^{\omega+2}}(n) > \lbrace n,n [2] n,n \rbrace$

$f_{\omega^{\omega+3}}(n) > \lbrace n,n,n [2] n,n,n \rbrace$

$f_{\omega^{\omega+m}}(n) > \lbrace n,m [2] 1 [2] 2 \rbrace$

$f_{\omega^{\omega2}}(n) > \lbrace n,n [2] 1 [2] 2 \rbrace = \lbrace n,2 [3] 2 \rbrace$

$f_{\omega^{\omega3}}(n) > \lbrace n,n [2] 1 [2] 1 [2] 2 \rbrace = \lbrace n,3 [3] 2 \rbrace$

$f_{\omega^{\omega m}}(n) > \lbrace n,m [3] 2 \rbrace$

$f_{\omega^{\omega^{2}}}(n) > \lbrace n,n [3] 2 \rbrace$

$f_{\omega^{\omega^{3}}}(n) > \lbrace n,n [4] 2 \rbrace$

$f_{\omega^{\omega^{m}}}(n) > \lbrace n,n [m+1] 2 \rbrace$

$f_{\omega^{\omega^{\omega}}}(n) > \lbrace n,n [n+1] 2 \rbrace > \lbrace n,n [1,2] 2 \rbrace$

$f_{^4{\omega}}(n) > \lbrace n,n [1 [2] 2] 2 \rbrace$

$f_{^5{\omega}}(n) > \lbrace n,n [1 [1,2] 2] 2 \rbrace$

$f_{^6{\omega}}(n) > \lbrace n,n [1 [1 [2] 2] 2] 2 \rbrace$

$f_{\varepsilon_{0}}(n) > \lbrace n,n [ [1]] 2 \rbrace$

$f_{\varepsilon_{0}2}(n) > \lbrace n,n [ [1]] 3 \rbrace$

$f_{\varepsilon_{0}m}(n) > \lbrace n,n [ [1]] m+1 \rbrace$

$f_{\varepsilon_{0}\omega}(n) > \lbrace n,n [ [1]] n+1 \rbrace$

$f_{\varepsilon_{0}{\omega^{\omega}}}(n) > \lbrace n,n [ [1]] 1 [2] 2 \rbrace$

$f_{\varepsilon_{0}{\omega^{\omega^{\omega}}}}(n) > \lbrace n,n [ [1]] 1 [1,2] 2 \rbrace$

$f_{\varepsilon_{0}{\omega^{\omega^{\omega^{\omega}}}}}(n) > \lbrace n,n [ [1]] 1 [1 [2] 2] 2 \rbrace$

$f_{\varepsilon_{0}^{2}}(n) > \lbrace n,n [ [1]] 1 [ [1]] 2 \rbrace$

$f_{\varepsilon_{0}^{3}}(n) > \lbrace n,n [ [1]] 1 [ [1]] 1 [ [1]] 2 \rbrace$

$f_{\varepsilon_{0}^{\omega}}(n) > \lbrace n,n [ [2]] 2 \rbrace$

$f_{\varepsilon_{0}^{\omega^{\omega}}}(n) > \lbrace n,n [ [1,2]] 2 \rbrace$

$f_{\varepsilon_{0}^{\omega^{\omega^{\omega}}}}(n) > \lbrace n,n [[1 [2] 2]] 2 \rbrace$

$f_{\varepsilon_{0}^{\varepsilon_{0}}}(n) > \lbrace n,n [[1 [ [1]] 2]] 2 \rbrace$

$f_{\varepsilon_{0}^{\varepsilon_{0}^{\varepsilon_{0}}}}(n) > \lbrace n,n [[1 [ [1]] 1 [ [1]] 2]] 2 \rbrace$

$f_{\varepsilon_{0}^{\varepsilon_0^{\varepsilon_0^{\varepsilon_0}}}}(n) > \lbrace n,n [[1 [[1 [ [1]] 2]] 2]] 2 \rbrace$

$f_{\varepsilon_{1}}(n) > \lbrace n,n [[[1]]] 2 \rbrace$

$f_{\varepsilon_{2}}(n) > \lbrace n,n [[[ [1]]]] 2 \rbrace$

$f_{\varepsilon_{\omega}}(n) > \lbrace n,n [1\backslash1,2] 2 \rbrace$

$f_{\varepsilon_{\omega^{2}}}(n) > \lbrace n,n [1\backslash1,1,2] 2 \rbrace$

$f_{\varepsilon_{\omega^{\omega}}}(n) > \lbrace n,n [1\backslash1 [2] 2] 2 \rbrace$

$f_{\varepsilon_{\omega^{\omega^{\omega}}}}(n) > \lbrace n,n [1\backslash1 [1,2] 2] 2 \rbrace$

$f_{\varepsilon_{\varepsilon_{0}}}(n) > \lbrace n,n [1\backslash1 [ [1]] 2] 2 \rbrace$

$f_{\varepsilon_{\varepsilon_{\varepsilon_{0}}}}(n) > \lbrace n,n [1\backslash1 [1\backslash1 [ [1]] 2] 2] 2 \rbrace$

$f_{\zeta_{0}} (n) > \lbrace n,n [1\backslash1\backslash2] 2 \rbrace$

$f_{\zeta_{0}^{\zeta_{0}}}(n) > \lbrace n,n [1 [1\backslash1\backslash2] 2\backslash1\backslash2] 2 \rbrace$

$f_{\varepsilon_{\zeta_{0}+1}}(n) > \lbrace n,n [1\backslash2\backslash2] 2 \rbrace$

$f_{\varepsilon_{\zeta_{0}+2}}(n) > \lbrace n,n [1\backslash3\backslash2] 2 \rbrace$

$f_{\varepsilon_{\varepsilon_{\zeta_{0}+1}}}(n) > \lbrace n,n [1\backslash1 [1\backslash2\backslash2] 2\backslash2]2 \rbrace$

$f_{\zeta_{1}}(n) > \lbrace n,n [1\backslash1\backslash3] 2 \rbrace$

$f_{\zeta_{2}}(n) > \lbrace n,n [1\backslash1\backslash4] 2 \rbrace$

$f_{\zeta_{\zeta_{0}}}(n) > \lbrace n,n [1\backslash1\backslash1 [1\backslash1\backslash2] 2] 2 \rbrace$

$f_{\eta_{0}}(n) > \lbrace n,n [1\backslash1\backslash1\backslash2] 2 \rbrace$

$f_{\varphi(4,0)}(n) > \lbrace n,n [1\backslash1\backslash1\backslash1\backslash2] 2 \rbrace$

$f_{\varphi(\omega,0)}(n) > \lbrace n,n [1 [2]\backslash2] 2 \rbrace$

$f_{\varphi(\varphi(\omega,0),0)}(n) > \lbrace n,n [1 [1 [1 [2]\backslash2]\backslash2] 2] 2 \rbrace$

$f_{\Gamma_{0}}(n) > \lbrace n,n [1/2] 2 \rbrace$

$f_{\varphi(1,0,0,0)}(n) > \lbrace n,n [1 [1\neg4] 2] 2 \rbrace$

$f_{\vartheta(\Omega^{\omega})}(n) > \lbrace n,n [1 [1\neg1,2] 2] 2 \rbrace$

$f_{\vartheta(\Omega^{\Omega})}(n) > \lbrace n,n [1 [1\neg1\neg2] 2] 2 \rbrace$

$f_{\vartheta(\Omega^{\Omega^{\Omega}})}(n) > \lbrace n,n [1 [1 [1\backslash_33] 2] 2] 2 \rbrace$

$f_{\vartheta(\vartheta_{1}(1))}(n) > \lbrace n,n [1 [1\sim3] 2] 2 \rbrace$

$f_{\vartheta(\vartheta_{1}(2))}(n) > \lbrace n,n [1 [1\sim1\sim2] 2] 2 \rbrace$

$f_{\vartheta(\vartheta_{1}(\omega))}(n) > \lbrace n,n [1 [1 [2/_32] 2] 2] 2 \rbrace$

$f_{\vartheta(\vartheta_{1}(\Omega))}(n) > \lbrace n,n [1 [1 [1/2/_32] 2] 2] 2 \rbrace$

$f_{\vartheta(\Omega_{2})}(n) > \lbrace n,n [1 [1 [1\sim2/_32] 2] 2] 2 \rbrace$

$f_{\vartheta(\Omega_{3})}(n) > \lbrace n,n [1 [1 [1 [1/_32/_42] 2] 2] 2] 2 \rbrace$

$f_{\vartheta(\Omega_{\omega})}(n) > \lbrace n,n [1\bullet2] 2 \rbrace$

$f_{\vartheta(\Omega_{\varepsilon_{0}})}(n) > \lbrace n,n [1 [2/_{1 [1\backslash2] 2}2] 2] 2 \rbrace$

$f_{\vartheta(\Omega_{\Gamma_{0}})}(n) > \lbrace n,n [1 [2/_{1 [1/2] 2}2] 2] 2 \rbrace$

$f_{\vartheta(\Omega_{\vartheta(\Omega_{2})})}(n) > \lbrace n,n [1 [2/_{1 [1 [1 [1\sim2/_32] 2] 2] 2}2] 2] 2 \rbrace$

$f_{\vartheta(\Omega_{\vartheta(\Omega_{3})})}(n) > \lbrace n,n [1 [2/_{1 [1 [1 [1 [1/_32/_42] 2] 2] 2] 2}2] 2] 2 \rbrace$

$f_{\vartheta(\Omega_{\vartheta(\Omega_{\omega})})}(n) > \lbrace n,n [1 [2/_{1 [1\bullet2] 2}2] 2] 2 \rbrace$

$f_{\vartheta(\Omega_{\vartheta(\Omega_{\vartheta(\Omega_{\omega})})})}(n) > \lbrace n,n [1 [2/_{1 [2/_{1 [1\bullet2] 2}2] 2}2] 2] 2 \rbrace$