Psi-funktioner af Buchholz

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 16. januar 2020; verifikation kræver 1 redigering .

Buchholz psi-funktioner er et hierarki af ordinale kollapsende funktioner introduceret af den tyske matematiker Wilfried Buchholz i 1986. [1] Disse funktioner er en forenklet version af Feferman-funktionerne , men har stadig den samme kraft. Senere blev denne tilgang udvidet af de tyske matematikere G. Jäger [2] og K. Schütte [3] . $\psi _{\nu}(\alpha )$ $\theta$

Definition

Buchholz definerede sine funktioner som følger:

{\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 )\} \\&{}\kop \{\psi _{\mu}(\xi )\midt \xi \in \alpha \cap C_{\nu }^{n}(\alpha )\kile \xi \i C_ {\mu }(\xi )\kile \mu \leq \omega \},\\[6pt]C_{\nu}(\alpha )={}&\bigcup _{n<\omega }C_{\nu }^{n}(\alpha ),\\\psi _{\nu}(\alpha )={}&\min\{\gamma \mid \gamma \ikke \i C_{\nu}(\alpha ) \},\end{aligned}}

hvor

\omega

er den mindste transfinite ordinal

\Omega _{\nu }={\begin{cases}1{\text{ if }}\nu =0\\{\text{kardinalnummer }}\aleph _{\nu }{\text { hvis }}\nu >0\end{cases}}

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

er sættet af additivt hovedtal i formen sådan, at og og , hvor er klassen af alle ordinaler.

{\displaystyle \omega ^{\xi ))

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

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

\gamma _{1},\ldots ,\gamma _{k}\in P=\{\omega ^{\xi}|\xi \i \operatornavn {On} \}=\{\alpha \ i \operatørnavn {Til} |0<\alpha \wedge \forall \xi ,\eta <\alpha (\xi +\eta <\alpha )\}

Til

Bemærk: Græske bogstaver betyder ordenstal overalt .

Grænsen for denne notation er Takeuchi-Feferman-Buchholz ordinal . $\psi _{0}(\varepsilon _{\Omega _{\omega }+1})$

Egenskaber

Buchholz viste følgende egenskaber ved disse funktioner:

$\psi _{\nu}(0)=\Omega _{\nu},$ i særdeleshed, $\psi _{0}(0)=1,$
$\psi _{\nu}(\alpha )\i 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}(\ alpha )\end{cases}},$
${\displaystyle \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{ og }}\nu \neq 0,$
$\theta (\varepsilon _{\Omega _{\nu }+1},0)=\psi _{0}(\varepsilon _{\Omega _{\nu}+1}){\text{ for }}0<\nu \leq \omega .$

Fundamentale sekvenser og normalformen for Buchholz-funktioner

Normal form

Normalformen for nul er 0. Hvis er en ordinal, der ikke er nul, så er normalformen for , hvor og , hvor hver ordinal også er skrevet på normalform. $\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 _{ jeg})$ $\psi _{\nu _{1}}(\beta _{1})\geq \psi _{\nu _{2}}(\beta _{2})\geq \cdots \geq \ psi _{\nu _{k}}(\beta _{k})$ ${\displaystyle \beta _{i))$

Grundlæggende sekvenser

Den grundlæggende sekvens for en grænseordinal med kofinalitet er en strengt stigende transfinit sekvens med længde og grænse , hvor er det th element i denne sekvens, det vil sige . $\alfa$ $\operatørnavn {cof} (\alpha )=\beta$ ${\displaystyle (\alpha [\eta ])_{\eta <\beta ))$ $\beta$ $\alfa$ $\alpha [\eta ]$ $\eta$ ${\displaystyle \alpha =\sup\{\alpha [\eta ]|\eta <\operatørnavn {cof} (\alpha )\))$

For grænseordtaler , skrevet i normal form, er de grundlæggende sekvenser defineret som følger: $\alfa$

Hvis , hvor , så og , $\alpha =\psi _{\nu _{1}}(\beta _{1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\ psi _{\nu _{k}}(\beta _{k})$ $k\geq 2$ $\operatørnavn {cof} (\alpha )=\operatørnavn {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 ])$
Hvis , så og , $\alpha =\psi _{\omega }(0)$ $\operatørnavn {cof} (\alpha )=\omega$ $\alpha [\eta ]=\psi _{\eta }(0)$
Hvis , så og , $\alpha =\psi _{\nu +1}(0)$ ${\displaystyle \operatørnavn {cof} (\alpha )=\Omega _{\nu +1))$ $\alpha [\eta ]=\Omega _{\nu +1}[\eta ]=\eta$
Hvis , så og (bemærk at: ), $\alpha =\psi _{\nu}(\beta +1)$ $\operatørnavn {cof} (\alpha )=\omega$ $\alpha [\eta ]=\psi _{\nu }(\beta )\cdot \eta$ ${\displaystyle \psi _{\nu }(0)=\Omega _{\nu ))$
Hvis og , så og , $\alpha =\psi _{\nu}(\beta)$ ${\displaystyle \operatorname {cof} (\beta )\i \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu <\nu \))$ $\operatørnavn {cof} (\alpha )=\operatørnavn {cof} (\beta )$ $\alpha [\eta ]=\psi _{\nu }(\beta [\eta ])$
Hvis og , så og , hvor . $\alpha =\psi _{\nu}(\beta)$ ${\displaystyle \operatørnavn {cof} (\beta )\i \{\Omega _{\mu +1}\mid \mu \geq \nu \))$ $\operatørnavn {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.$

En forklaring af principperne for notation

Da Buchholz arbejder i Zermelo-Fraenkel-systemet , er hver ordinal lig med sættet af alle mindre ordinaler, . Betingelsen betyder, at sættet indeholder alle ordtal mindre end eller med andre ord . $\alfa$ ${\displaystyle \alpha =\{\beta \mid \beta <\alpha \))$ $C_{\nu }^{0}(\alpha )=\Omega _{\nu }$ $C_{\nu}^{0}(\alpha )$ $\Omega_\nu$ ${\displaystyle C_{\nu }^{0}(\alpha )=\{\beta \mid \beta <\Omega _{\nu}\))$

Betingelsen betyder, at sættet indeholder: $C_{\nu}^{n+1}(\alpha )=C_{\nu}^{n}(\alpha )\cup \{\gamma \mid P(\gamma )\subseteq C_{\ nu }^{n}(\alpha )\}\kop \{\psi _{\mu}(\xi )\mid \xi \in \alpha \cap C_{\nu }^{n}(\alpha ) \wedge \mu \leq \omega \}$ $C_{\nu}^{n+1}(\alpha )$

alle ordenstal fra det forrige sæt , $C_{\nu }^{n}(\alpha )$

alle ordinaler, der kan opnås ved additivt at summere hovedordtaler fra det foregående sæt , $C_{\nu }^{n}(\alpha )$

alle ordinaler, der kan opnås ved at bruge ordinaler (mindre end ) fra det foregående sæt som argumenter for funktioner , hvor . $\alfa$ $C_{\nu }^{n}(\alpha )$ ${\displaystyle \psi _{\mu ))$ $\mu \leq \omega$

Derfor kan denne betingelse omskrives som følger:

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 \}.

Således er foreningen af alle mængder med , det vil sige , er mængden af alle ordinaler, der kan dannes ud fra ordinaler ved funktionerne + (addition) og , hvor og . $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$

Så er den mindste ordinal, der ikke hører til dette sæt. ${\displaystyle \psi _{\nu}(\alpha )=\min\{\gamma \mid \gamma \ikke \i C_{\nu}(\alpha )\))$

Eksempler

Overvej følgende eksempler:

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

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

(da der ikke er nogen funktionsværdier for , og 0 + 0 = 0).

{\displaystyle \psi _{\nu))

\eta <0

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

$C_{0}(1)$ indeholder alle mulige summer af naturlige tal. Derfor er den første transfinite ordinal, som er større end alle naturlige tal per definition. $\psi _{0}(0)=1$ $\psi _{0}(1)=\omega$

$C_{0}(2)$ indeholder alle deres mulige beløb. Derfor ,. $\psi _{0}(0)=1,\psi _{0}(1)=\omega$ ${\displaystyle \psi _{0}(2)=\omega ^{2))$

Hvis , så og . $\alpha =\omega$ $C_{0}(\alpha )=\{0,\psi (0)=1,\ldots ,\psi (1)=\omega ,\ldots ,\psi (2)=\omega ^{2 },\ldots ,\psi (3)=\omega ^{3},\ldots \}$ ${\displaystyle \psi _{0}(\omega )=\omega ^{\omega ))$

Hvis , så og er det mindste tal epsilon , det vil sige det første faste punkt . $\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 \))$ ${\displaystyle \psi _{0}(\Omega )=\varepsilon _{0))$ ${\displaystyle \alpha =\omega ^{\alpha ))$

Hvis , så og . $\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 \}$ ${\displaystyle \psi _{0}(\Omega +1)=\varepsilon _{0}\omega =\omega ^{\varepsilon _{0}+1))$

${\displaystyle \psi _{0}(\Omega 2)=\varepsilon _{1))$ er det andet epsilon nummer ,

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

det vil sige det første faste punkt ,

{\displaystyle \alpha =\varepsilon _{\alpha ))

$\varphi (\alpha ,1+\beta )=\psi _{0}(\Omega ^{\alpha }\beta )$ , hvor angiver Veblen-funktionen , $\varphi$

$\psi _{0}(\Omega ^{\Omega })=\Gamma _{0}=\varphi (1,0,0)=\theta (\Omega ,0)$ , hvor betegner Feferman-funktionen , og betegner Feferman-Schütte-ordinalen $\theta$ $\Gamma_0$

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

– Ackermann ordinal ,

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

– Lille veblen ordinal ,

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

– Great Veblen ordinal ,

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

Lad os nu se, hvordan funktionen fungerer : $\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 \}

, det vil sige, at den indeholder alle tællelige ordinaler. Indeholder derfor alle mulige summer af alle tællelige ordinaler, og er den første utallige ordinal, der er større end alle tællelige ordinaler per definition, det vil sige den mindste ordinal med kardinalitet .

C_{1}(0)

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

\aleph_1

Hvis , så og . $\alpha=1$ $C_{1}(\alpha )=\{0,\ldots ,\psi _{0}(0)=\omega ,\ldots ,\psi _{1}(0)=\Omega ,\ldots ,\Omega +\omega ,\ldots ,\Omega +\Omega ,\ldots \}$ ${\displaystyle \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

, hvor er et naturligt tal, ,

k

k\geq 2

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

For casen indeholder sættet funktioner med alle argumenter mindre end , det vil sige argumenter som f.eks $\psi (\psi _{2}(0))=\psi (\Omega _{2})$ $C_{0}(\Omega _{2})$ $\psi_{0}$ ${\displaystyle \Omega _{2))$ $0,\psi _{1}(0),\psi _{1}(\psi _{1}(0)),\psi _{1}^{3}(0),\ldots, \psi _{1}^{\omega }(0)$

og så

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

Generelt:

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

Noter

↑ Buchholz, W. Et nyt system af bevisteoretiske ordinalfunktioner (ubestemt) // Annals of Pure and Applied Logic. - T. 32 .
↑ Jäger, G. -utilgængelige ordtaler, sammenklappende funktioner og et rekursivt notationssystem // Arkiv f. matematik. Logik og Grundlagenf. : journal. - 1984. - Bd. 24 , nr. 1 . - S. 49-62 . $\rho$
↑ Buchholz, W.; Schütte, K. Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der -Separation und Bar-Induktion (tysk) // Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. klasse: butik. - 1983. ${\displaystyle \Pi _{2}^{1))$

Links

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