Veblen-toiminto

Matematiikassa Veblenin funktiot ovat hierarkia normaaleista funktioista , jotka kasvavat tiukasti ordinaalista ordinaalille, jota Oswald Veblen ehdotti vuonna 1908. Jos on mikä tahansa normaali funktio, niin mille tahansa nollasta poikkeavalle järjestysluvulle funktio luettelee kaikkien yhteiset kiinteät pisteet. Kaikki nämä funktiot ovat normaaleja. $\varphi_{0}$ $\alpha$ $\varphi _{\alpha }$ ${\displaystyle \varphi _{\beta ))$ $\beta <\alpha .$

Veblenin hierarkia

Erityistapauksessa , kun tätä funktioperhettä kutsutaan Veblen - hierarkiaksi ; Veblen-hierarkian yhteydessä käytetään Cantor-normaalimuodon muunnelmaa - mikä tahansa nollasta poikkeava järjestysluku voidaan kirjoittaa yksiselitteisesti muotoon, jossa on luonnollinen luku , ja siten minkä tahansa nollasta poikkeavan järjestysluvun perussekvenssi voidaan määrittää lauseke , ottaen huomioon seuraavat säännöt: $\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]$

Jos sitten siksi ja $\beta =0,$ $\varphi _{0}(\gamma +1)[n]=\omega ^{\gamma }\cdot n,$ $\varphi _{0}(0)=1$ $\varphi _{0}(\gamma )=\omega ^{\gamma }.$
Jos sitten ja sitten on $\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).$
Jos on raja-kertaluku , niin $\gamma$ $\varphi _{\beta }(\gamma )[n]=\varphi _{\beta }(\gamma [n]).$
Jos on raja-kertaluku , niin ja $\beeta$ $\varphi _{\beta }(0)[n]=\varphi _{\beta [n]}(0)$ $\varphi _{\beta }(\gamma +1)[n]=\varphi _{\beta [n]}(\varphi _{\beta }(\gamma )+1).$
Muuten siis _ $\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) .$

Esimerkkejä

säännön 2 soveltaminen	säännön 5 soveltaminen
$\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$ (sääntö 1)

$\varphi _{0}(\varphi _{0}(1))[n]=\varphi _{0}(\varphi _{0}(1)[n])=\omega ^{\ omega[n]}=\omega ^{n}$ (Säännöt 1 ja 3)

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

$\varphi _{\varphi _{0}(1)}(0)[n]=\varphi _{\omega }(0)[n]=\varphi _{\omega [n]}(0 )=\varphi _{n}(0)$ (säännöt 1 ja 4)

$\varphi _{\varphi _{1}(0)}(0)[3]=\varphi _{\varepsilon _{0}}(0)[3]=\varphi _{\varepsilon _{ 0}[3]}(0)=\varphi _{\omega ^{\omega }}(0)$ (sääntö 4)

Asiaankuuluvia esimerkkejä nopeasti kasvavalle hierarkialle :

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

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

G-funktio

Funktio Γ luettelee ordinaaleja siten, että pienintä järjestyslukua , jolle tämä ehto täyttyy, kutsutaan Fefermanin ordinaaliksi Sen perussekvenssi määritellään seuraavilla lausekkeilla: $\alpha,$ $\varphi _{\alpha }(0)=\alpha .$ $\alpha,$ $\Gamma _{0}.$

$\Gamma _{0}[0]=0\,$ ja $\Gamma _{0}[n+1]=\varphi _{\Gamma _{0}[n]}(0).$
Totta ja _ ${\displaystyle \Gamma _{\beta +1))$ $\Gamma _{\beta +1}[0]=\Gamma _{\beta }+1$ $\Gamma _{\beta +1}[n+1]=\varphi _{\Gamma _{\beta +1}[n]}(0).$
Jos on raja-kertaluku ja sitten $\beeta$ $\beta <\Gamma _{\beta },$ $\Gamma _{\beta }[n]=\Gamma _{\beta [n]}.$

Yleistys

Veblen-funktio voidaan esittää myös kahden argumentin funktiona. Veblen osoitti, kuinka määritelmä yleistetään antamaan funktio mielivaltaiselle määrälle argumentteja, nimittäin: $\varphi _{\alpha }(\beta )$ $\varphi (\alpha ,\beta )$ $\varphi (\alpha _{n},\alpha _{n-1},...,\alpha _{0})$

$\varphi (\alpha )=\omega ^{\alpha }$ yhden muuttujan tapauksessa
$\varphi (0,\alpha _{n-1},...,\alpha _{0})=\varphi (\alpha _{n-1},...,\alpha _{0 }),$ ja
for on funktio, joka luettelee funktioiden yhteiset kiinteät pisteet kaikille $\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 .$

Esimerkiksi on funktioiden -:s kiinteä piste , nimittäin $\varphi (1,0,\gamma )$ $\gamma$ $\xi \mapsto \varphi (0,\xi ,0)=\varphi (\xi ,0),$ $\Gamma _{\gamma }.$

${\displaystyle \varphi (1,0,0)=\Gamma _{0))$ - Fefermanin järjestysluku.
$\varphi (1,0,0,0)$ - Ackermannin järjestysluku.
Raja on pieni Veblenin järjestysluku. $\varphi (1,0,...,0,0)$

Linkit

Hilbert Levitz, Transfinite Ordinaals and Their Notations: For The Unitiated , selittävä artikkeli (8 sivua, PostScriptissä )
Pohlers, Wolfram (1989), Proof theory , voi. 1407, Lecture Notes in Mathematics, Berlin: Springer-Verlag, ISBN 3-540-51842-8
Schütte, Kurt (1977), Proof theory , voi. 225, Grundlehren der Mathematischen Wissenschaften, Berliini-New York: Springer-Verlag, s. xii+299, ISBN 3-540-07911-4
Takeuti, Gaisi (1987), Proof theory , voi. 81 (2. painos), 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 vol. 4 (4): 182–189 , DOI 10.1007/BF03023553 sisältää epävirallisen kuvauksen Veblen-hierarkiasta.
Veblen, Oswald (1908), Continuous Increasing Functions of Finite and Transfinite Ordinals , Transactions of the American Mathematical Society , osa 9 (3): 280–292 , DOI 10.2307/1988605
Miller, Larry W. (1976), Normal Functions and Constructive Ordinal Notations , The Journal of Symbolic Logic, osa 41 (2): 439–459 , DOI 10.2307/2272243

Isoja lukuja
Numerot	googol Shannonin numero Googolplex Skewesin numero Moserin numero Grahamin numero PUU(3) Rayo numero
Toiminnot	Ackermann-toiminto Veblen-toiminto Buchholzin Psi-funktiot tetration Pentation Hyperoperaattori Nopeasti kasvava hierarkia Hierarkia kasvaa hitaasti Kova hierarkia
Merkinnät	Steinhaus-Moser-merkintä Knuthin nuolen merkintä Conway-nuolen merkintä Massiivinen Bowers-merkintä