Funcția Veblen

În matematică , funcțiile Veblen sunt o ierarhie de funcții normale care cresc strict de la ordinal la ordinal, propusă de Oswald Veblen în 1908. Dacă este orice funcție normală, atunci pentru orice ordinal diferit de zero funcția enumerează punctele fixe comune ale tuturor pentru Toate aceste funcții sunt normale. $\varphi_{0}$ $\alfa$ $\varphi _{\alpha }$ $\varphi _{\beta }$ $\beta <\alpha .$

Ierarhia lui Veblen

În cazul particular când , această familie de funcții este numită ierarhia Veblen ; În legătură cu ierarhia Veblen, se folosește o variație a formei normale Cantor - orice ordinal diferit de zero poate fi scris în mod unic ca unde este un număr natural și , astfel, secvența fundamentală pentru orice ordinal diferit de zero poate fi determinată din expresie , ținând cont de următoarele reguli: $\varphi _{0}(\alpha )=\omega ^{\alpha }$ $\varphi _{1}(\alpha )=\varepsilon _{\alpha },\,\varphi _{2}(\alpha )=\zeta _{\alpha },\,\varphi _{3 }(\alpha )=\eta _{\alpha }.$ $\alfa$ $\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}).$ $\alfa$ $\alpha [n]=\varphi _{\beta _{1}}(\gamma _{1})+\cdots +\varphi _{\beta _{k-1}}(\gamma _{ k-1})+\varphi _{\beta _{k))(\gamma _{k})[n]$

Dacă atunci pentru că şi $\beta =0,$ $\varphi _{0}(\gamma +1)[n]=\omega ^{\gamma }\cdot n,$ $\varphi _{0}(0)=1$ $\varphi _{0}(\gamma )=\omega ^{\gamma }.$
Dacă atunci și atunci există $\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).$
Dacă este un ordinal limită , atunci $\gamma$ $\varphi _{\beta}(\gamma)[n]=\varphi _{\beta}(\gamma [n]).$
Dacă este un ordinal limită , atunci și $\beta$ $\varphi _{\beta}(0)[n]=\varphi _{\beta [n]}(0)$ $\varphi _{\beta}(\gamma +1)[n]=\varphi _{\beta [n]}(\varphi _{\beta}(\gamma )+1).$
Altfel , adica $\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) .$

Exemple

aplicarea regulii 2	aplicarea regulii 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))$
$\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$ (regula 1)

$\varphi _{0}(\varphi _{0}(1))[n]=\varphi _{0}(\varphi _{0}(1)[n])=\omega ^{\ omega[n]}=\omega ^{n}$ (Regulile 1 și 3)

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

$\varphi _{\varphi _{0}(1)}(0)[n]=\varphi _{\omega}(0)[n]=\varphi _{\omega [n]}(0 )=\varphi _{n}(0)$ (regulile 1 și 4)

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

Exemple relevante pentru o ierarhie în creștere rapidă :

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

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

Funcția G

Funcția Γ enumerează ordinale astfel încât Cel mai mic ordinal pentru care este îndeplinită această condiție se numește ordinal Feferman Secvența fundamentală pentru aceasta este definită de următoarele expresii: $\alpha ,$ $\varphi _{\alpha }(0)=\alpha .$ $\alpha ,$ $\Gamma _{0}.$

$\Gamma _{0}[0]=0\,$ și $\Gamma _{0}[n+1]=\varphi _{\Gamma _{0}[n]}(0).$
Pentru adevărat și $\Gamma _{\beta +1)$ $\Gamma _{\beta +1}[0]=\Gamma _{\beta }+1$ $\Gamma _{\beta +1}[n+1]=\varphi _{\Gamma _{\beta +1}[n]}(0).$
Dacă este un ordinal limită și atunci $\beta$ $\beta <\Gamma _{\beta},$ $\Gamma _{\beta }[n]=\Gamma _{\beta [n]}.$

Generalizare

Funcția Veblen poate fi reprezentată și ca o funcție a două argumente. Veblen a arătat cum să generalizeze definiția pentru a da o funcție pentru un număr arbitrar de argumente, și anume: $\varphi _{\alpha }(\beta )$ $\varphi (\alpha,\beta)$ $\varphi (\alpha _{n},\alpha _{n-1},...,\alpha _{0})$

$\varphi (\alpha )=\omega ^{\alpha }$ pentru cazul unei variabile,
$\varphi (0,\alpha _{n-1},...,\alpha _{0})=\varphi (\alpha _{n-1},...,\alpha _{0} }),$ și
pentru este o funcție care listează puncte fixe comune ale funcțiilor pentru toți $\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 .$

De exemplu, este al -lea punct fix al funcțiilor , și anume $\varphi (1,0,\gamma )$ $\gamma$ $\xi \mapsto \varphi (0,\xi,0)=\varphi (\xi,0),$ $\Gamma _{\gamma }.$

$\varphi (1,0,0)=\Gamma _{0)$ — Ordinalul lui Feferman.
$\varphi (1,0,0,0)$ - Ordinal Ackermann.
Limita pentru este ordinalul Veblen mic. $\varphi (1,0,...,0,0)$

Link -uri

Hilbert Levitz, Ordinalele transfinite și notațiile lor: pentru cei neinițiați , articol expozitiv (8 pagini, în PostScript )
Pohlers, Wolfram (1989), Teoria probei , voi. 1407, Note de curs în matematică, Berlin: Springer-Verlag, ISBN 3-540-51842-8
Schütte, Kurt (1977), Teoria dovezilor , voi. 225, Grundlehren der Mathematischen Wissenschaften, Berlin-New York: Springer-Verlag, p. xii+299, ISBN 3-540-07911-4
Takeuti, Gaisi (1987), Teoria probei , voi. 81 (ed. a doua), Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland Publishing Co., ISBN 0-444-87943-9
Smorynski, C. (1982), Varietățile experienței arboricole , Math. Intelligencer vol. 4 (4): 182–189 , DOI 10.1007/BF03023553 conține o descriere informală a ierarhiei Veblen.
Veblen, Oswald (1908), Continuous Cresing Functions of Finite and Transfinite Ordinals , Tranzacții ale Societății Americane de Matematică vol. 9 (3): 280–292 , DOI 10.2307/1988605
Miller, Larry W. (1976), Funcții normale și notații ordinale constructive , The Journal of Symbolic Logic vol. 41 (2): 439–459 , DOI 10.2307/2272243

Cifre mari
Numerele	googol Numărul Shannon Googlelplex Număr înclinat numărul Moser Numărul Graham TREE(3) Numărul Rayo
Funcții	Funcția Ackermann Funcția Veblen Funcțiile Psi ale lui Buchholz tetrare Pentație Hiperoperator Ierarhie în creștere rapidă Ierarhie în creștere lent Ierarhie Hardy
Notații	Notația Steinhaus-Moser Notație cu săgeată Knuth Notație săgeată Conway Notație masivă Bowers