Funcțiile Psi ale lui Buchholz

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 16 ianuarie 2020; verificarea necesită 1 editare .

Funcțiile psi Buchholz sunt o ierarhie de funcții ordinale de colaps introdusă de matematicianul german Wilfried Buchholz în 1986. [1] Aceste funcții sunt o versiune simplificată a funcțiilor Feferman , dar au totuși aceeași putere. Mai târziu această abordare a fost extinsă de matematicienii germani G. Jäger [2] și K. Schütte [3] . $\psi _{\nu }(\alpha )$ $\theta$

Definiție

Buchholz și-a definit funcțiile după cum urmează:

{\begin{aligned}C_{\nu }^{0}(\alpha )={}&\Omega _{\nu },\\[6pt]C_{\nu }^{n+1} (\alpha )={}&C_{\nu }^{n}(\alpha )\cup \{\gamma \mid P(\gamma )\subseteq C_{\nu }^{n}(\alpha )\} \\&{}\cup \{\psi _{\mu }(\xi )\mid \xi \in \alpha \cap C_{\nu }^{n}(\alpha )\wedge \xi \in C_ {\mu }(\xi )\wedge \mu \leq \omega \},\\[6pt]C_{\nu }(\alpha )={}&\bigcup _{n<\omega }C_{\nu }^{n}(\alpha ),\\\psi _{\nu }(\alpha )={}&\min\{\gamma \mid \gamma \not \in C_{\nu }(\alpha ) \},\end{aliniat}}

Unde

\omega

este cel mai mic ordinal transfinit

\Omega _{\nu }={\begin{cases}1{\text{ if }}\nu =0\\{\text{număr cardinal }}\aleph _{\nu }{\text { dacă }}\nu >0\end{cases}}

{\displaystyle P(\gamma )=\{\gamma _{1},\ldots,\gamma _{k}\))

este mulțimea numerelor principale aditiv sub forma astfel încât și și , unde este clasa tuturor ordinalelor.

\omega ^{\xi )

\gamma =\gamma _{1}+\cdots +\gamma _{k)

\gamma _{1}\geq \cdots \geq \gamma _{k)

\gamma _{1},\ldots,\gamma _{k}\in P=\{\omega ^{\xi }|\xi \in \operatorname {On} \}=\{\alpha \ în \operatorname {On} |0<\alpha \wedge \forall \xi ,\eta <\alpha (\xi +\eta <\alpha )\}

activat

Notă: literele grecești înseamnă ordinale peste tot .

Limita acestei notații este ordinalul Takeuchi-Feferman-Buchholz . $\psi _{0}(\varepsilon _{\Omega _{\omega}+1})$

Proprietăți

Buchholz a arătat următoarele proprietăți ale acestor funcții:

$\psi _{\nu }(0)=\Omega _{\nu },$ în special, $\psi _{0}(0)=1,$
$\psi _{\nu }(\alpha )\in P,$
$\psi _{\nu }(\alpha +1)={\begin{cases}\min\{\gamma \in P:\psi _{\nu }(\alpha )<\gamma \}{ \text{ if }}\alpha \in C_{\nu }(\alpha )\\\psi _{\nu }(\alpha ){\text{ if }}\alpha \notin C_{\nu }(\ alfa )\end{cazuri}},$
$\Omega _{\nu }\leq \psi _{\nu }(\alpha )<\Omega _{\nu +1)$
$\psi _{0}(\alpha )=\omega ^{\alpha }{\text{if }}\alpha <\varepsilon _{0},$
$\psi _{\nu }(\alpha )=\omega ^{\Omega _{\nu }+\alpha }{\text{ if ))\alpha </varepsilon _{\Omega _{\nu }+1}{\text{ și }}\nu \neq 0,$
$\theta (\varepsilon _{\Omega _{\nu }+1},0)=\psi _{0}(\varepsilon _{\Omega _{\nu }+1}) {\text{ pentru }}0<\nu \leq \omega .$

Secvențe fundamentale și forma normală pentru funcțiile Buchholz

Forma normală

Forma normală pentru zero este 0. Dacă este un ordinal diferit de zero, atunci forma normală pentru este , unde și , unde fiecare ordinal este de asemenea scris în formă normală. $\alfa$ $\alfa$ $\alpha =\psi _{\nu _{1}}(\beta _{1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\ psi _{\nu _{k}}(\beta _{k})$ $\nu _{i}\leq \omega,k\in \mathbb {N} _{>0},\beta _{i}\in C_{\nu _{i))(\beta _{ i})$ $\psi _{\nu _{1}}(\beta _{1})\geq \psi _{\nu _{2}}(\beta _{2})\geq \cdots \geq \ psi _{\nu _{k}}(\beta _{k})$ $\beta _{i}$

Secvențe fundamentale

Secvența fundamentală pentru un ordinal limită cu cofinalitate este o secvență transfinită strict crescătoare cu lungime și limită , unde este al- lea element al acestei secvențe, adică . $\alfa$ $\operatorname {cof} (\alpha )=\beta$ $(\alpha [\eta])_{\eta <\beta )$ $\beta$ $\alfa$ $\alpha [\eta ]$ $\eta$ ${\displaystyle \alpha =\sup\{\alpha [\eta ]|\eta <\operatorname {cof} (\alpha )\))$

Pentru ordinale limită , scrise în formă normală, secvențele fundamentale sunt definite după cum urmează: $\alfa$

Dacă , unde , atunci și , $\alpha =\psi _{\nu _{1}}(\beta _{1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\ psi _{\nu _{k}}(\beta _{k})$ $k\geq 2$ $\operatorname {cof} (\alpha )=\operatorname {cof} (\psi _{\nu _{k))(\beta _{k}))$ $\alpha [\eta ]=\psi _{\nu _{1))(\beta _{1})+\cdots +\psi _{\nu _{k-1))(\beta _ {k-1})+(\psi _{\nu _{k))(\beta _{k})[\eta ])$
Dacă , atunci și , $\alpha =\psi _{\omega }(0)$ $\operatorname {cof} (\alpha )=\omega$ $\alpha [\eta ]=\psi _{\eta }(0)$
Dacă , atunci și , $\alpha =\psi _{\nu +1}(0)$ $\operatorname {cof} (\alpha )=\Omega _{\nu +1)$ $\alpha [\eta ]=\Omega _{\nu +1}[\eta ]=\eta$
Dacă , atunci și (rețineți că: ), $\alpha =\psi _{\nu }(\beta +1)$ $\operatorname {cof} (\alpha )=\omega$ $\alpha [\eta ]=\psi _{\nu }(\beta )\cdot \eta$ ${\displaystyle \psi _{\nu }(0)=\Omega _{\nu ))$
Dacă și , atunci și , $\alpha =\psi _{\nu }(\beta)$ $\operatorname {cof} (\beta)\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu <\nu \)$ $\operatorname {cof} (\alpha )=\operatorname {cof} (\beta)$ $\alpha [\eta ]=\psi _{\nu }(\beta [\eta ])$
Dacă și , atunci și , unde . $\alpha =\psi _{\nu }(\beta)$ ${\displaystyle \operatorname {cof} (\beta)\in \{\Omega _{\mu +1}\mid \mu \geq \nu \))$ $\operatorname {cof} (\alpha )=\omega$ $\alpha [\eta ]=\psi _{\nu }(\beta [\gamma [\eta ]])$ $\left\{{\begin{array}{lcr}\gamma [0]=\Omega _{\mu }\\\gamma [\eta +1]=\psi _{\mu }(\beta [\gamma [\eta ]])\\\end{array}}\right.$

O explicație a principiilor notației

Deoarece Buchholz lucrează în sistemul Zermelo-Fraenkel , fiecare ordinal este egal cu mulțimea tuturor ordinalelor mai mici, . Condiția înseamnă că mulțimea conține toate ordinalele mai mici decât sau cu alte cuvinte . $\alfa$ $\alpha =\{\beta \mid \beta <\alpha \)$ $C_{\nu }^{0}(\alpha )=\Omega _{\nu }$ $C_{\nu }^{0}(\alpha )$ $\Omega_\nu$ $C_{\nu }^{0}(\alpha )=\{\beta \mid \beta <\Omega _{\nu }\)$

Condiția înseamnă că setul conține: $C_{\nu }^{n+1}(\alpha )=C_{\nu }^{n}(\alpha )\cup \{\gamma \mid P(\gamma)\subseteq C_{\ nu }^{n}(\alpha )\}\cup \{\psi _{\mu }(\xi )\mid \xi \in \alpha \cap C_{\nu }^{n}(\alpha ) \wedge \mu \leq \omega \}$ $C_{\nu }^{n+1}(\alpha )$

toate ordinalele din setul anterior , $C_{\nu }^{n}(\alpha )$

toate ordinalele care pot fi obținute prin însumarea suplimentară a ordinalelor principale din mulțimea anterioară , $C_{\nu }^{n}(\alpha )$

toate ordinalele care pot fi obținute prin utilizarea ordinalelor (mai mici decât ) din setul anterior ca argumente ale funcțiilor , unde . $\alfa$ $C_{\nu }^{n}(\alpha )$ $\psi _{\mu )$ $\mu \leq \omega$

Prin urmare, această condiție poate fi rescrisă după cum urmează:

C_{\nu }^{n+1}(\alpha )=\{\beta +\gamma ,\psi _{\mu }(\eta )\mid \beta ,\gamma ,\eta \in C_{\nu }^{n}(\alpha )\wedge \eta <\alpha \wedge \mu \leq \omega \}.

Astfel, unirea tuturor mulțimilor cu , adică , este mulțimea tuturor ordinalelor care pot fi formate din ordinale prin funcțiile + (adunare) și , unde și . $C_{\nu }^{n}(\alpha )$ $n<\omega$ $C_{\nu }(\alpha )=\bigcup _{n<\omega}C_{\nu }^{n}(\alpha )$ $<\aleph _{\nu }$ $\psi _{\mu }(\eta )$ $\mu \leq \omega$ $\eta <\alpha$

Atunci este cel mai mic ordinal care nu aparține acestui set. ${\displaystyle \psi _{\nu }(\alpha )=\min\{\gamma \mid \gamma \nu \in C_{\nu }(\alpha )\))$

Exemple

Luați în considerare următoarele exemple:

C_{0}^{0}(\alpha )=\{0\}=\{\beta \mid \beta <1\},

C_{0}(0)=\{0\}

(deoarece nu există valori ale funcției pentru și 0 + 0 = 0).

{\displaystyle \psi _{\nu ))

\eta <0

Apoi . $\psi _{0}(0)=1$

$C_{0}(1)$ conține toate sumele posibile de numere naturale. Prin urmare, este primul ordinal transfinit, care este mai mare decât toate numerele naturale prin definiție. $\psi _{0}(0)=1$ $\psi _{0}(1)=\omega$

$C_{0}(2)$ conţine toate sumele lor posibile. Prin urmare, . $\psi _{0}(0)=1,\psi _{0}(1)=\omega$ $\psi _{0}(2)=\omega ^{2)$

Dacă , atunci și . $\alpha =\omega$ $C_{0}(\alpha )=\{0,\psi (0)=1,\ldots,\psi (1)=\omega,\ldots,\psi (2)=\omega ^{2 },\ldots ,\psi (3)=\omega ^{3},\ldots \}$ $\psi _{0}(\omega )=\omega ^{\omega )$

Dacă , atunci și este cel mai mic număr epsilon , adică primul punct fix . $\alpha =\Omega$ ${\displaystyle C_{0}(\alpha )=\{0,\psi (0)=1,\ldots,\psi (1)=\omega,\ldots,\psi (\omega)=\omega ^{ \omega },\ldots ,\psi (\omega ^{\omega })=\omega ^{\omega ^{\omega )),\ldots \))$ $\psi _{0}(\Omega )=\varepsilon _{0)$ $\alpha =\omega ^{\alpha }$

Dacă , atunci și . $\alpha =\Omega +1$ $C_{0}(\alpha )=\{0,1,\ldots,\psi _{0}(\Omega)=\varepsilon _{0},\ldots,\varepsilon _{0}+\ varepsilon _{0},\ldots ,\psi _{1}(0)=\Omega ,\ldots \}$ $\psi _{0}(\Omega +1)=\varepsilon _{0}\omega =\omega ^{\varepsilon _{0}+1)$

$\psi _{0}(\Omega 2)=\varepsilon _{1)$ este al doilea număr epsilon ,

\psi _{0}(\Omega ^{2})=\varepsilon _{\varepsilon _{\cdots }}=\zeta _{0}

, adică primul punct fix ,

\alpha =\varepsilon _{\alpha }

$\varphi (\alpha,1+\beta)=\psi _{0}(\Omega ^{\alpha }\beta)$ , unde denotă funcția Veblen , $\varphi$

$\psi _{0}(\Omega ^{\Omega})=\Gamma _{0}=\varphi (1,0,0)=\theta (\Omega,0)$ , unde denotă funcția Feferman și denotă ordinalul Feferman-Schütte $\theta$ $\Gamma_0$

\psi _{0}(\Omega ^{\Omega ^{2)))=\varphi (1,0,0,0)

– Ackermann ordinal ,

\psi _{0}(\Omega ^{\Omega ^{\omega )))

– Ordinal Veblen mic ,

\psi _{0}(\Omega ^{\Omega ^{\Omega )))

– Great Veblen ordinal ,

\psi _{0}(\Omega \uparrow \uparrow \omega)=\psi _{0}(\varepsilon _{\Omega +1})=\theta (\varepsilon _{\Omega +1} ,0).

Acum să vedem cum funcționează funcția : $\psi_{1}$

C_{1}^{0}(0)=\{\beta \mid \beta <\Omega _{1}\}=\{0,\psi (0)=1,2,\ldots , 10^{100},\ldots ,\psi _{0}(1)=\omega ,\ldots ,\psi _{0}(\Omega )=\varepsilon _{0},\ldots ,\psi _{ 0}(\Omega ^{\Omega })=\Gamma _{0},\ldots ,\psi (\Omega ^{\Omega ^{\Omega }+\Omega ^{2))),\ldots \}

, adică conține toate ordinalele numărabile. Prin urmare, conține toate sumele posibile ale tuturor ordinalelor numărabile și este primul ordinal nenumărabil care este mai mare decât toate ordinalele numărabile prin definiție, adică cel mai mic ordinal cu cardinalitate .

C_{1}(0)

\psi _{1}(0)=\Omega _{1)

\aleph_1

Dacă , atunci și . $\alpha=1$ $C_{1}(\alpha )=\{0,\ldots,\psi _{0}(0)=\omega,\ldots,\psi _{1}(0)=\Omega,\ldots ,\Omega +\omega ,\ldots ,\Omega +\Omega ,\ldots \}$ $\psi _{1}(1)=\Omega \omega =\omega ^{\Omega +1)$

\psi _{1}(2)=\Omega \omega ^{2}=\omega ^{\Omega +2},

\psi _{1}(\psi _{1}(0))=\psi _{1}(\Omega )=\Omega ^{2}=\omega ^{\Omega +\Omega},

\psi _{1}(\psi _{1}(\psi _{1}(0)))=\omega ^{\Omega +\omega ^{\Omega +\Omega ))=\omega ^{\Omega \cdot \Omega }=(\omega ^{\Omega })^{\Omega }=\Omega ^{\Omega },

\psi _{1}^{4}(0)=\Omega ^{\Omega ^{\Omega )),

\psi _{1}^{k+1}(0)=\Omega \uparrow \uparrow k

, unde este un număr natural, ,

k

k\geq 2

\psi _{1}(\Omega _{2})=\psi _{1}^{\omega }(0)=\Omega \uparrow \uparrow \omega =\varepsilon _{\Omega +1 }.

Pentru acest caz, setul conține funcții cu toate argumentele mai mici decât , adică argumente precum $\psi (\psi _{2}(0))=\psi (\Omega _{2})$ $C_{0}(\Omega _{2})$ $\psi_{0}$ $\Omega _{2)$ $0,\psi _{1}(0),\psi _{1}(\psi _{1}(0)),\psi _{1}^{3}(0),\ldots, \psi _{1}^{\omega }(0)$

și apoi

\psi _{0}(\Omega _{2})=\psi _{0}(\psi _{1}(\Omega _{2}))=\psi _{0}(\varepsilon _{\Omega +1}).

În general:

\psi _{0}(\Omega _{\nu +1})=\psi _{0}(\psi _{\nu }(\Omega _{\nu +1}))=\psi _{0}(\varepsilon _{\Omega _{\nu }+1})=\theta (\varepsilon _{\Omega _{\nu }+1},0).

Note

↑ Buchholz, W. A New System of Proof-Theoretic Ordinal Functions (nedefinite) // Annals of Pure and Applied Logic. - T. 32 .
↑ Jäger, G. -ordinale inaccesibile, funcții de colaps și un sistem de notație recursiv // Arhiv f. matematica. Logica și Grundlagenf. : jurnal. - 1984. - Vol. 24 , nr. 1 . - P. 49-62 . $\rho$
↑ Buchholz, W.; Schütte, K. Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der -Separation und Bar-Induktion (germană) // Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. clasa: magazin. — 1983. $\Pi _{2}^{1)$

Link -uri

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