WikiSort.ru - Не сортированное

В математике функции Веблена — это иерархия нормальных функций, строго возрастающих от ординала к ординалу, предложенная Освальдом Вебленом в 1908 году. Если φ₀ — это какая-либо нормальная функция, тогда для любого ненулевого ординала α, функция φ_α перечисляет общие неподвижные точки всех φ_β для β<α. Все эти функции нормальные.

Иерархия Веблена

В частном случае, когда φ₀(α)=ω^α это семейство функций называется иерархией Веблена. Например, ${\displaystyle \varphi _{1}(\alpha )=\varepsilon _{\alpha }}$ , ${\displaystyle \varphi _{2}(\alpha )=\zeta _{\alpha }}$ , ${\displaystyle \varphi _{3}(\alpha )=\eta _{\alpha }}$ . В связи с иерархией Веблена применяется вариация нормальной формы Кантора — любой ненулевой ординал α может быть уникально записан как ${\displaystyle \alpha =\varphi _{\beta _{1}}(\gamma _{1})+\varphi _{\beta _{2}}(\gamma _{2})+\cdots +\varphi _{\beta _{k}}(\gamma _{k})}$ , где k>0 — некое натуральное число, ${\displaystyle \varphi _{\beta _{m}}(\gamma _{m})\geq \varphi _{\beta _{m+1}}(\gamma _{m+1})}$ и ${\displaystyle \gamma _{m}<\varphi _{\beta _{m}}(\gamma _{m})}$ . Таким образом фундаментальная последовательность для любого ненулевого ординала α может быть определена из выражения ${\displaystyle \alpha [n]=\varphi _{\beta _{1}}(\gamma _{1})+\cdots +\varphi _{\beta _{k-1}}(\gamma _{k-1})+(\varphi _{\beta _{k}}(\gamma _{k})[n])}$ с учетом следующих правил

1) если ${\displaystyle \beta =0}$ тогда ${\displaystyle \varphi _{0}(\gamma +1)[n]=\omega ^{\gamma }\cdot n}$

поскольку ${\displaystyle \varphi _{0}(0)=1}$ и ${\displaystyle \varphi _{0}(\gamma )=\omega ^{\gamma }}$

2) если ${\displaystyle \gamma =0}$ тогда ${\displaystyle \varphi _{\beta +1}(0)[0]=0}$

и ${\displaystyle \varphi _{\beta +1}(0)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(0)[n])}$

то есть ${\displaystyle \varphi _{\beta +1}(0)[n]=\varphi _{\beta }^{n}(0)}$

3) если ${\displaystyle \gamma }$ предельный ординал, тогда ${\displaystyle \varphi _{\beta }(\gamma )[n]=\varphi _{\beta }(\gamma [n])}$

4) если ${\displaystyle \beta }$ предельный ординал, тогда ${\displaystyle \varphi _{\beta }(0)[n]=\varphi _{\beta [n]}(0)}$

и ${\displaystyle \varphi _{\beta }(\gamma +1)[n]=\varphi _{\beta [n]}(\varphi _{\beta }(\gamma )+1)}$

5) иначе ${\displaystyle \varphi _{\beta +1}(\gamma +1)[0]=\varphi _{\beta +1}(\gamma )+1}$

и ${\displaystyle \varphi _{\beta +1}(\gamma +1)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(\gamma +1)[n])}$

то есть ${\displaystyle \varphi _{\beta +1}(\gamma +1)[n]=\varphi _{\beta }^{n}(\varphi _{\beta +1}(\gamma )+1)}$

Примеры

применение правила 2	применение правила 5
${\displaystyle \varphi _{1}(0)[0]=\varepsilon _{0}[0]=0}$	${\displaystyle \varphi _{1}(1)[0]=\varphi _{1}(0)+1=\varepsilon _{0}+1=\varepsilon _{1}[0]}$
${\displaystyle \varphi _{1}(0)[1]=\varphi _{0}(\varphi _{1}(0)[0])=\varphi _{0}(0)=\omega ^{0}=1}$	${\displaystyle \varphi _{1}(1)[1]=\varphi _{0}(\varphi _{1}(1)[0])=\varepsilon _{1}[1]=\omega ^{\varepsilon _{0}+1}}$
${\displaystyle \varphi _{1}(0)[2]=\varphi _{0}(\varphi _{1}(0)[1])=\omega ^{1}=\omega }$	${\displaystyle \varphi _{1}(1)[2]=\varphi _{0}(\varphi _{1}(1)[1])=\varepsilon _{1}[2]=\omega ^{\omega ^{\varepsilon _{0}+1}}}$
${\displaystyle \varphi _{1}(0)[3]=\varphi _{0}(\varphi _{1}(0)[2])=\omega ^{\omega }}$	${\displaystyle \varphi _{1}(1)[3]=\varphi _{0}(\varphi _{1}(1)[2])=\varepsilon _{1}[3]=\omega ^{\omega ^{\omega ^{\varepsilon _{0}+1}}}}$
${\displaystyle \varphi _{1}(0)[4]=\varphi _{0}(\varphi _{1}(0)[3])=\omega ^{\omega ^{\omega }}}$	${\displaystyle \varphi _{1}(1)[4]=\varphi _{0}(\varphi _{1}(1)[3])=\varepsilon _{1}[4]=\omega ^{\omega ^{\omega ^{\omega ^{\varepsilon _{0}+1}}}}}$
${\displaystyle \varphi _{2}(0)[4]=\varphi _{1}(\varphi _{1}(\varphi _{1}(\varphi _{1}(0))))=\varepsilon _{\varepsilon _{\varepsilon _{\varepsilon _{0}}}}=\zeta _{0}[4]}$	${\displaystyle \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]}$
${\displaystyle \varphi _{3}(0)[4]=\varphi _{2}(\varphi _{2}(\varphi _{2}(\varphi _{2}(0))))=\zeta _{\zeta _{\zeta _{\zeta _{0}}}}=\eta _{0}[4]}$	${\displaystyle \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]}$

${\displaystyle \varphi _{0}(3)[n]=\omega ^{2}\cdot n}$ (Правило 1)

${\displaystyle \varphi _{0}(\varphi _{0}(1))[n]=\varphi _{0}(\varphi _{0}(1)[n])=\omega ^{\omega [n]}=\omega ^{n}}$ (Правила 1 и 3)

${\displaystyle \varphi _{1}(\omega )[n]=\varphi _{1}(\omega [n])=\varphi _{1}(n)=\varepsilon _{n}}$ (Правило 3)

${\displaystyle \varphi _{1}(\varphi _{1}(0))[n]=\varphi _{1}(\varphi _{1}(0)[n])=\varphi _{1}(\varepsilon _{0}[n])=\varepsilon _{\omega \uparrow \uparrow (n-1)}}$ (Правило 3)

${\displaystyle \varphi _{\varphi _{0}(1)}(0)[n]=\varphi _{\omega }(0)[n]=\varphi _{\omega [n]}(0)=\varphi _{n}(0)}$ (Правила 1 и 4)

${\displaystyle \varphi _{\varphi _{1}(0)}(0)[3]=\varphi _{\varepsilon _{0}}(0)[3]=\varphi _{\varepsilon _{0}[3]}(0)=\varphi _{\omega ^{\omega }}(0)}$ (Правило 4)

Соответствующие примеры для быстрорастущей иерархии

${\displaystyle f_{\varphi _{1}(0)}(4)=f_{\varphi _{1}(0)[4]}(4)=f_{\omega ^{\omega ^{\omega }}}(4)}$

${\displaystyle f_{\varphi _{1}(1)}(3)=f_{\varphi _{1}(1)[3]}(3)=f_{\omega ^{\omega ^{\omega ^{\varepsilon _{0}+1}}}}(3)}$

Ссылки

• Hilbert Levitz, Transfinite Ordinals and Their Notations: For The Uninitiated, expository article (8 pages, in PostScript)
• Pohlers, Wolfram (1989), Proof theory, vol. 1407, Lecture Notes in Mathematics, Berlin: Springer-Verlag, ISBN 3-540-51842-8 
• Schütte, Kurt (1977), Proof theory, vol. 225, Grundlehren der Mathematischen Wissenschaften, Berlin-New York: Springer-Verlag, с. xii+299, ISBN 3-540-07911-4 
• Takeuti, Gaisi (1987), Proof theory, vol. 81 (Second ed.), Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland Publishing Co., ISBN 0-444-87943-9 
• Smorynski, C. (1982), "The varieties of arboreal experience", Math. Intelligencer Т. 4 (4): 182–189, DOI 10.1007/BF03023553  contains an informal description of the Veblen hierarchy.
• Veblen, Oswald (1908), "Continuous Increasing Functions of Finite and Transfinite Ordinals", Transactions of the American Mathematical Society Т. 9 (3): 280–292, DOI 10.2307/1988605 
• Miller, Larry W. (1976), "Normal Functions and Constructive Ordinal Notations", The Journal of Symbolic Logic Т. 41 (2): 439–459, DOI 10.2307/2272243