Funkce Veblen

V matematice jsou Veblenovy funkce hierarchií normálních funkcí , které se striktně zvyšují od řadové k řadové, kterou navrhl Oswald Veblen v roce 1908. Jestliže je nějaká normální funkce, pak pro libovolnou nenulovou ordinální hodnotu funkce vyjmenovává společné pevné body všech pro Všechny tyto funkce jsou normální. $\varphi_{0}$ $\alpha$ $\varphi _{\alpha }$ ${\displaystyle \varphi _{\beta ))$ $\beta <\alpha .$

Hierarchie Veblen

V konkrétním případě, kdy se tato rodina funkcí nazývá Veblenova hierarchie ; V souvislosti s Veblenovou hierarchií se používá variace Cantorovy normální formy - libovolnou nenulovou ordinální hodnotu lze jednoznačně zapsat jako kde je přirozené číslo , a tak základní posloupnost pro jakoukoli nenulovou ordinální hodnotu lze určit z výraz s přihlédnutím k následujícím pravidlům: $\varphi _{0}(\alpha )=\omega ^{\alpha }$ $\varphi _{1}(\alpha )=\varepsilon _{\alpha },\,\varphi _{2}(\alpha )=\zeta _{\alpha },\,\varphi _{3 }(\alpha )=\eta _{\alpha }.$ $\alpha$ $\alpha =\varphi _{\beta _{1}}(\gamma _{1})+\varphi _{\beta _{2}}(\gamma _{2})+\cdots +\ varphi _{\beta _{k}}(\gamma _{k}),$ $k>0$ $\varphi _{\beta _{m))(\gamma _{m})\geq \varphi _{\beta _{m+1))(\gamma _{m+1})$ $\gamma _{m}<\varphi _{\beta _{m))(\gamma _{m}).$ $\alpha$ $\alpha [n]=\varphi _{\beta _{1}}(\gamma _{1})+\cdots +\varphi _{\beta _{k-1}}(\gamma _{ k-1})+\varphi _{\beta _{k))(\gamma _{k})[n]$

Pokud pak proto a $\beta =0,$ $\varphi _{0}(\gamma +1)[n]=\omega ^{\gamma }\cdot n,$ $\varphi _{0}(0)=1$ $\varphi _{0}(\gamma )=\omega ^{\gamma }.$
Pokud tehdy a tehdy existuje $\gamma =0,$ $\varphi _{\beta +1}(0)[0]=0$ $\varphi _{\beta +1}(0)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(0)[n]),$ $\varphi _{\beta +1}(0)[n]=\varphi _{\beta }^{n}(0).$
Jestliže je limita ordinální , pak $\gamma$ $\varphi _{\beta }(\gamma )[n]=\varphi _{\beta }(\gamma [n]).$
Jestliže je limita ordinální , potom a $\beta$ $\varphi _{\beta }(0)[n]=\varphi _{\beta [n]}(0)$ $\varphi _{\beta }(\gamma +1)[n]=\varphi _{\beta [n]}(\varphi _{\beta }(\gamma )+1).$
Jinak , tzn $\varphi _{\beta +1}(\gamma +1)[0]=\varphi _{\beta +1}(\gamma )+1$ $\varphi _{\beta +1}(\gamma +1)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(\gamma +1)[n] ),$ $\varphi _{\beta +1}(\gamma +1)[n]=\varphi _{\beta }^{n}(\varphi _{\beta +1}(\gamma )+1) .$

Příklady

použití pravidla 2	použití pravidla 5
$\varphi _{1}(0)[0]=\varepsilon _{0}[0]=0$	$\varphi _{1}(1)[0]=\varphi _{1}(0)+1=\varepsilon _{0}+1=\varepsilon _{1}[0]$
$\varphi _{1}(0)[1]=\varphi _{0}(\varphi _{1}(0)[0])=\varphi _{0}(0)=\omega ^ {0}=1$	$\varphi _{1}(1)[1]=\varphi _{0}(\varphi _{1}(1)[0])=\varepsilon _{1}[1]=\omega ^ {\varepsilon _{0}+1}$
$\varphi _{1}(0)[2]=\varphi _{0}(\varphi _{1}(0)[1])=\omega ^{1}=\omega$	$\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))))$
$\varphi _{1}(0)[4]=\varphi _{0}(\varphi _{1}(0)[3])=\omega ^{\omega ^{\omega ))$	$\varphi _{1}(1)[4]=\varphi _{0}(\varphi _{1}(1)[3])=\varepsilon _{1}[4]=\omega ^ {\omega ^{\omega ^{\omega ^{\varepsilon _{0}+1))))$
$\varphi _{2}(0)[4]=\varphi _{1}(\varphi _{1}(\varphi _{1}(\varphi _{1}(0))))= \varepsilon _{\varepsilon _{\varepsilon _{\varepsilon _{0))))=\zeta _{0}[4]$	$\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]$
$\varphi _{3}(0)[4]=\varphi _{2}(\varphi _{2}(\varphi _{2}(\varphi _{2}(0))))= \zeta _{\zeta _{\zeta _{\zeta _{0))))=\eta _{0}[4]$	$\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]$

$\varphi _{0}(3)[n]=\omega ^{2}\cdot n$ (pravidlo 1)

$\varphi _{0}(\varphi _{0}(1))[n]=\varphi _{0}(\varphi _{0}(1)[n])=\omega ^{\ omega[n]}=\omega ^{n}$ (Pravidla 1 a 3)

${\displaystyle \varphi _{1}(\omega )[n]=\varphi _{1}(\omega [n])=\varphi _{1}(n)=\varepsilon _{n))$ (pravidlo 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)))$ (pravidlo 3)

$\varphi _{\varphi _{0}(1)}(0)[n]=\varphi _{\omega }(0)[n]=\varphi _{\omega [n]}(0 )=\varphi _{n}(0)$ (pravidla 1 a 4)

$\varphi _{\varphi _{1}(0)}(0)[3]=\varphi _{\varepsilon _{0}}(0)[3]=\varphi _{\varepsilon _{ 0}[3]}(0)=\varphi _{\omega ^{\omega }}(0)$ (pravidlo 4)

Relevantní příklady pro rychle rostoucí hierarchii :

$f_{\varphi _{1}(0)}(4)=f_{\varphi _{1}(0)[4]}(4)=f_{\omega ^{\omega ^{\omega }}}(čtyři)$

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

G-funkce

Funkce Γ vyjmenovává ordinály tak, že nejmenší ordinála , pro kterou je tato podmínka splněna, se nazývá Fefermanova ordinála Základní posloupnost pro ni je definována následujícími výrazy: $\alpha ,$ $\varphi _{\alpha }(0)=\alpha .$ $\alpha ,$ $\Gamma _{0}.$

$\Gamma _{0}[0]=0\,$ a $\Gamma _{0}[n+1]=\varphi _{\Gamma _{0}[n]}(0).$
Za pravdivé a ${\displaystyle \Gamma _{\beta +1))$ $\Gamma _{\beta +1}[0]=\Gamma _{\beta }+1$ $\Gamma _{\beta +1}[n+1]=\varphi _{\Gamma _{\beta +1}[n]}(0).$
If je limita ordinální a potom $\beta$ $\beta <\Gamma _{\beta },$ $\Gamma _{\beta }[n]=\Gamma _{\beta [n]}.$

Generalizace

Funkci Veblen lze také reprezentovat jako funkci dvou argumentů. Veblen ukázal, jak zobecnit definici, aby poskytla funkci pro libovolný počet argumentů, konkrétně: $\varphi _{\alpha } (\beta )$ $\varphi (\alpha ,\beta )$ $\varphi (\alpha _{n},\alpha _{n-1},...,\alpha _{0})$

$\varphi (\alpha )=\omega ^{\alpha }$ pro případ jedné proměnné,
$\varphi (0,\alpha _{n-1},...,\alpha _{0})=\varphi (\alpha _{n-1},...,\alpha _{0 }),$ a
for je funkce vypisující společné pevné body funkcí pro všechny $\alpha >0,\,\gamma \mapsto \varphi (\alpha _{n},...,\alpha _{i+1},\alpha ,0,...,0,\gamma )$ $\xi \mapsto \varphi (\alpha _{n},...,\alpha _{i+1},\beta ,\xi ,0,...,0)$ $\beta <\alpha .$

Například je -tý pevný bod funkcí , jmenovitě $\varphi (1,0,\gamma )$ $\gamma$ $\xi \mapsto \varphi (0,\xi ,0)=\varphi (\xi ,0),$ $\Gamma _{\gamma }.$

${\displaystyle \varphi (1,0,0)=\Gamma _{0))$ — Fefermanův ordinál.
$\varphi (1,0,0,0)$ - Ackermannův ordinál.
Limit pro je malá Veblenova ordinála. $\varphi (1,0,...,0,0)$

Odkazy

Hilbert Levitz, Transfinite Ordinals and Their Notations: For The Unitiated , výkladový článek (8 stránek, v PostScriptu )
Pohlers, Wolfram (1989), Teorie důkazu , sv. 1407, Poznámky k přednáškám z matematiky, Berlín: Springer-Verlag, ISBN 3-540-51842-8
Schütte, Kurt (1977), Teorie důkazu , sv. 225, Grundlehren der Mathematischen Wissenschaften, Berlín-New York: Springer-Verlag, s. xii+299, ISBN 3-540-07911-4
Takeuti, Gaisi (1987), Teorie důkazu , sv. 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 variety of arboreal experience , Math. Intelligencer vol. 4 (4): 182–189 , DOI 10.1007/BF03023553 obsahuje neformální popis Veblenovy hierarchie.
Veblen, Oswald (1908), Continuous Rostoucí funkce konečných a transfinitních ordinálů , Transactions of the American Mathematical Society vol. 9 (3): 280–292 , DOI 10.2307/1988605
Miller, Larry W. (1976), Normal Functions and Constructive Ordinal Notations , The Journal of Symbolic Logic vol. 41 (2): 439–459 , DOI 10.2307/2272243

Velká čísla
Čísla	googol Shannonovo číslo Googolplex Skewes číslo Moserovo číslo Grahamovo číslo STROM(3) Rayo číslo
Funkce	Ackermannova funkce Funkce Veblen Psi funkce Buchholze tetování Pentace Hyperoperátor Rychle rostoucí hierarchie Pomalu rostoucí hierarchie Hardyho hierarchie
Notace	Steinhaus-Moserova notace Knuthova šipková notace Notace Conwayovy šipky Masivní Bowers Notace