Veblen funktion

I matematik er Veblen-funktioner et hierarki af normale funktioner, der strengt stiger fra ordinal til ordinal, foreslået af Oswald Veblen i 1908. Hvis det er en normal funktion, så opregner funktionen for enhver ordinal ikke-nul de fælles fikspunkter for alle for Alle disse funktioner er normale. $\varphi_{0}$ $\alfa$ $\varphi _{\alpha }$ ${\displaystyle \varphi _{\beta ))$ $\beta <\alpha .$

Hierarki af Veblen

I det særlige tilfælde, når , kaldes denne familie af funktioner for Veblen-hierarkiet ; I forbindelse med Veblen-hierarkiet bruges en variation af Cantor-normalformen - enhver ordinal, der ikke er nul , kan entydigt skrives som hvor er et naturligt tal , og således kan den grundlæggende rækkefølge for enhver ordinal, der ikke er nul , bestemmes ud fra udtryk under hensyntagen til følgende regler: $\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]$

Hvis så fordi og $\beta =0,$ $\varphi _{0}(\gamma +1)[n]=\omega ^{\gamma }\cdot n,$ $\varphi _{0}(0)=1$ $\varphi _{0}(\gamma )=\omega ^{\gamma }.$
Hvis der da og så er der $\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).$
Hvis er en grænseordinal , så $\gamma$ $\varphi _{\beta }(\gamma )[n]=\varphi _{\beta }(\gamma [n]).$
Hvis er en grænseordinal , så og $\beta$ $\varphi _{\beta }(0)[n]=\varphi _{\beta [n]}(0)$ $\varphi _{\beta }(\gamma +1)[n]=\varphi _{\beta [n]}(\varphi _{\beta }(\gamma )+1).$
Ellers altså _ $\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) .$

Eksempler

anvendelse af regel 2	anvendelse af regel 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$ (regel 1)

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

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

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

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

Relevante eksempler for et hurtigt voksende hierarki :

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

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

G-funktion

Funktionen Γ opregner ordinaler således, at Den mindste ordinal , for hvilken denne betingelse er opfyldt, kaldes Feferman ordinal Grundsekvensen for den er defineret af følgende udtryk: $\alfa,$ $\varphi _{\alpha }(0)=\alpha .$ $\alfa,$ $\Gamma _{0}.$

$\Gamma _{0}[0]=0\,$ og $\Gamma _{0}[n+1]=\varphi _{\Gamma _{0}[n]}(0).$
For sandt og ${\displaystyle \Gamma _{\beta +1))$ $\Gamma _{\beta +1}[0]=\Gamma _{\beta }+1$ $\Gamma _{\beta +1}[n+1]=\varphi _{\Gamma _{\beta +1}[n]}(0).$
Hvis er en grænseordinal og derefter $\beta$ $\beta <\Gamma _{\beta },$ $\Gamma _{\beta }[n]=\Gamma _{\beta [n]}.$

Generalisering

Veblen-funktionen kan også repræsenteres som en funktion af to argumenter. Veblen viste, hvordan man generaliserer definitionen for at give en funktion for et vilkårligt antal argumenter, nemlig: $\varphi _{\alpha }(\beta )$ $\varphi (\alpha ,\beta )$ $\varphi (\alpha _{n},\alpha _{n-1},...,\alpha _{0})$

$\varphi (\alpha )=\omega ^{\alpha }$ for én variabel,
$\varphi (0,\alpha _{n-1},...,\alpha _{0})=\varphi (\alpha _{n-1},...,\alpha _{0 }),$ og
for er en funktion, der viser fælles faste punkter for funktioner for alle $\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 .$

For eksempel er det - . fikspunkt for funktionerne , nemlig $\varphi (1,0,\gamma )$ $\gamma$ $\xi \mapsto \varphi (0,\xi ,0)=\varphi (\xi ,0),$ $\Gamma _{\gamma }.$

${\displaystyle \varphi (1,0,0)=\Gamma _{0))$ — Fefermans ordinal.
$\varphi (1,0,0,0)$ - Ackermann ordinal.
Grænsen for er den lille veblenske ordinal. $\varphi (1,0,...,0,0)$

Links

Hilbert Levitz, Transfinite Ordinals and Their Notations: For The Uninitiated , forklarende artikel (8 sider, i 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 , bd. 225, Grundlehren der Mathematischen Wissenschaften, Berlin-New York: Springer-Verlag, s. xii+299, ISBN 3-540-07911-4
Takeuti, Gaisi (1987), Proof theory , vol. 81 (anden udgave), 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 indeholder en uformel beskrivelse af Veblen-hierarkiet.
Veblen, Oswald (1908), Continuous Increasing Functions of Finite and Transfinite Ordinals , Transactions of the American Mathematical Society bind 9 (3): 280–292 , DOI 10.2307/1988605
Miller, Larry W. (1976), Normal Functions and Constructive Ordinal Notations , The Journal of Symbolic Logic bind 41 (2): 439–459 , DOI 10.2307/2272243

Store tal
Tal	google Shannon nummer Googolplex Skæv nummer Moser nummer Graham nummer TRÆ(3) Rayo nummer
Funktioner	Ackermann funktion Veblen funktion Psi-funktioner af Buchholz tetration Pentation Hyperoperator Hurtigt voksende hierarki Langsomt voksende hierarki Hardy hierarki
Notationer	Steinhaus-Moser notation Knuth pil notation Conway pil notation Massiv Bowers-notation