Русская Википедия:Функция Веблена
В математике функции Веблена — иерархия нормальных функций, строго возрастающих от ординала к ординалу, предложенная Освальдом Вебленом в 1908 году. Если <math>\varphi_0</math> — это какая-либо нормальная функция, тогда для любого ненулевого ординала <math>\alpha</math> функция <math>\varphi_\alpha</math> перечисляет общие неподвижные точки всех <math>\varphi_\beta</math> для <math>\beta < \alpha.</math> Все эти функции нормальные.
Иерархия Веблена
В частном случае, когда <math>\varphi_0(\alpha)=\omega^\alpha</math>, это семейство функций называется иерархией Веблена; <math>\varphi_1(\alpha)=\varepsilon_{\alpha}, \, \varphi_2(\alpha)=\zeta_{\alpha}, \, \varphi_3(\alpha)=\eta_{\alpha}.</math> В связи с иерархией Веблена применяется вариация нормальной формы Кантора — любой ненулевой ординал <math>\alpha</math> может быть уникально записан как <math>\alpha = \varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k),</math> где <math>k > 0</math> — некое натуральное число, <math>\varphi_{\beta_m}(\gamma_m) \geq \varphi_{\beta_{m+1}}(\gamma_{m+1})</math> и <math>\gamma_m < \varphi_{\beta_m}(\gamma_m).</math> Таким образом, фундаментальная последовательность для любого ненулевого ординала <math>\alpha</math> может быть определена из выражения <math>\alpha [n] = \varphi_{\beta_1}(\gamma_1) + \cdots + \varphi_{\beta_{k-1}}(\gamma_{k-1}) + \varphi_{\beta_k}(\gamma_k) [n]</math> с учётом следующих правил:
- Если <math>\beta=0,</math> тогда <math>\varphi_0(\gamma+1) [n] = \omega^{\gamma} \cdot n,</math> поскольку <math>\varphi_0(0)=1</math> и <math>\varphi_0(\gamma)=\omega^{\gamma}.</math>
- Если <math>\gamma=0,</math> тогда <math>\varphi_{\beta+1}(0) [0] = 0</math> и <math>\varphi_{\beta+1}(0) [n+1] = \varphi_{\beta}(\varphi_{\beta+1}(0) [n]),</math> то есть <math>\varphi_{\beta+1}(0)[n]=\varphi_{\beta}^n(0).</math>
- Если <math>\gamma</math> — предельный ординал, тогда <math>\varphi_{\beta}(\gamma) [n] = \varphi_{\beta}(\gamma [n]).</math>
- Если <math>\beta</math> — предельный ординал, тогда <math>\varphi_{\beta}(0) [n] = \varphi_{\beta [n]}(0)</math> и <math>\varphi_{\beta}(\gamma+1) [n] = \varphi_{\beta [n]}(\varphi_{\beta}(\gamma)+1).</math>
- Иначе <math>\varphi_{\beta+1}(\gamma+1) [0] = \varphi_{\beta+1}(\gamma)+1</math> и <math>\varphi_{\beta+1}(\gamma+1) [n+1] = \varphi_{\beta} (\varphi_{\beta+1}(\gamma+1) [n]),</math> то есть <math>\varphi_{\beta+1}(\gamma+1)[n]=\varphi_{\beta}^n(\varphi_{\beta+1}(\gamma)+1).</math>
Примеры
| применение правила 2 | применение правила 5 |
|---|---|
| <math>\varphi_{1}(0)[0]=\varepsilon_{0} [0] = 0</math> | <math>\varphi_{1}(1)[0]=\varphi_{1}(0)+1=\varepsilon_{0}+1=\varepsilon_{1} [0]</math> |
| <math>\varphi_{1}(0)[1]=\varphi_{0}(\varphi_{1}(0)[0])=\varphi_{0}(0)=\omega^0=1</math> | <math>\varphi_{1}(1)[1]=\varphi_{0}(\varphi_{1}(1)[0])=\varepsilon_{1} [1]=\omega^{\varepsilon_{0}+1}</math> |
| <math>\varphi_{1}(0)[2]=\varphi_{0}(\varphi_{1}(0)[1])=\omega^1=\omega</math> | <math>\varphi_{1}(1)[2]=\varphi_{0}(\varphi_{1}(1)[1])=\varepsilon_{1} [2]=\omega^{\omega^{\varepsilon_{0}+1}}</math> |
| <math>\varphi_{1}(0)[3]=\varphi_{0}(\varphi_{1}(0)[2])=\omega^{\omega}</math> | <math>\varphi_{1}(1)[3]=\varphi_{0}(\varphi_{1}(1)[2])=\varepsilon_{1} [3]=\omega^{\omega^{\omega^{\varepsilon_{0}+1}}}</math> |
| <math>\varphi_{1}(0)[4]=\varphi_{0}(\varphi_{1}(0)[3])=\omega^{\omega^{\omega}}</math> | <math>\varphi_{1}(1)[4]=\varphi_{0}(\varphi_{1}(1)[3])=\varepsilon_{1} [4]=\omega^{\omega^{\omega^{\omega^{\varepsilon_{0}+1}}}}</math> |
| <math>\varphi_{2}(0)[4]=\varphi_{1}(\varphi_{1}(\varphi_{1}(\varphi_{1}(0))))=\varepsilon_{\varepsilon_{\varepsilon_{\varepsilon_0}}}=\zeta_0[4]</math> | <math>\varphi_{2}(1)[4]=\varphi_{1}(\varphi_{1}(\varphi_{1}(\varphi_{1}(\varphi_2 (0)+1))))=\varepsilon_{\varepsilon_{\varepsilon_{\varepsilon_{\zeta_0 +1}}}}=\zeta_1[4]</math> |
| <math>\varphi_{3}(0)[4]=\varphi_{2}(\varphi_{2}(\varphi_{2}(\varphi_{2}(0))))=\zeta_{\zeta_{\zeta_{\zeta_0}}}=\eta_0 [4]</math> | <math>\varphi_{3}(1)[4]=\varphi_{2}(\varphi_{2}(\varphi_{2}(\varphi_{2}(\varphi_3 (0)+1))))=\zeta_{\zeta_{\zeta_{\zeta_{\eta_0 +1}}}}=\eta_1[4]</math> |
<math>\varphi_{0}(3)[n]=\omega^2\cdot n </math> (правило 1)
<math>\varphi_{0}(\varphi_{0}(1))[n]=\varphi_{0}(\varphi_{0}(1)[n])=\omega^{\omega[n]}=\omega^n</math> (Правила 1 и 3)
<math>\varphi_{1}(\omega)[n]=\varphi_{1}(\omega[n])=\varphi_{1}(n)=\varepsilon_n</math> (правило 3)
<math>\varphi_{1}(\varphi_{1}(0))[n]=\varphi_{1}(\varphi_{1}(0)[n])=\varphi_{1}(\varepsilon_0 [n])=\varepsilon_{\omega \uparrow \uparrow (n-1)}</math> (правило 3)
<math>\varphi_{\varphi_0 (1)}(0)[n]=\varphi_{\omega}(0)[n]=\varphi_{\omega [n]}(0)=\varphi_{n}(0)</math> (правила 1 и 4)
<math>\varphi_{\varphi_1 (0)}(0)[3]=\varphi_{\varepsilon_0}(0)[3]=\varphi_{\varepsilon_0[3]}(0)=\varphi_{\omega^{\omega}}(0)</math> (правило 4)
Соответствующие примеры для быстрорастущей иерархии:
<math>f_{\varphi_{1}(0)}(4)=f_{\varphi_{1}(0)[4]}(4)=f_{\omega^{\omega^{\omega}}}(4)</math>
<math>f_{\varphi_{1}(1)}(3)=f_{\varphi_{1}(1)[3]}(3)=f_{\omega^{\omega^{\omega^{\varepsilon_{0}+1}}}}(3)</math>
Г-функция
Функция Γ перечисляет ординалы <math>\alpha,</math> такие что <math>\varphi_\alpha(0) = \alpha.</math> Наименьший ординал <math>\alpha,</math> для которого выполняется это условие, называется Шаблон:Iw <math>\Gamma_0.</math> Фундаментальная последовательность для него определяется следующими выражениями:
- <math>\Gamma_0 [0] = 0 \,</math> и <math>\Gamma_0 [n+1] = \varphi_{\Gamma_0 [n]} (0).</math>
- Для <math>\Gamma_{\beta+1}</math> верно <math>\Gamma_{\beta+1} [0] = \Gamma_{\beta} + 1</math> и <math>\Gamma_{\beta+1} [n+1] = \varphi_{\Gamma_{\beta+1} [n]} (0).</math>
- Если <math>\beta</math> — предельный ординал и <math>\beta < \Gamma_{\beta},</math> тогда <math>\Gamma_{\beta} [n] = \Gamma_{\beta [n]}.</math>
Обобщение
Функция Веблена <math>\varphi_\alpha(\beta)</math> также может быть представлена в виде функции <math>\varphi(\alpha,\beta)</math> двух аргументов. Веблен показал, как обобщить определение для того, чтобы получить функцию <math>\varphi(\alpha_n,\alpha_{n-1},...,\alpha_0)</math> для произвольного числа аргументов, а именно:
- <math>\varphi(\alpha) = \omega^\alpha</math> для случая одной переменной,
- <math>\varphi(0,\alpha_{n-1},...,\alpha_0)=\varphi(\alpha_{n-1},...,\alpha_0),</math> и
- для <math>\alpha>0, \, \gamma\mapsto\varphi(\alpha_n,...,\alpha_{i+1},\alpha,0,...,0,\gamma)</math> — это функция, перечисляющая общие неподвижные точки функций <math>\xi\mapsto\varphi(\alpha_n,...,\alpha_{i+1},\beta,\xi,0,...,0)</math> для всех <math>\beta<\alpha.</math>
Например, <math>\varphi(1,0,\gamma)</math> — это <math>\gamma</math>-я неподвижная точка функций <math>\xi\mapsto\varphi(0,\xi,0)=\varphi(\xi,0),</math> а именно <math>\Gamma_\gamma.</math>
- <math>\varphi(1,0,0)=\Gamma_0</math> — ординал Фефермана.
- <math>\varphi(1,0,0,0)</math> — ординал Аккермана.
- Предел для <math>\varphi(1,0,...,0,0)</math> — малый ординал Веблена.
Ссылки
- Hilbert Levitz, Transfinite Ordinals and Their Notations: For The Uninitiated, expository article (8 pages, in PostScript)
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation contains an informal description of the Veblen hierarchy.
- Шаблон:Citation
- Шаблон:Citation
