Psi-funktioner för Buchholz

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 16 januari 2020; verifiering kräver 1 redigering .

Buchholz psi-funktioner är en hierarki av ordinala kollapsande funktioner som introducerades av den tyske matematikern Wilfried Buchholz 1986. [1] Dessa funktioner är en förenklad version av Feferman-funktionerna , men har fortfarande samma kraft. Senare utvidgades detta tillvägagångssätt av de tyska matematikerna G. Jäger [2] och K. Schütte [3] . $\psi _{\nu}(\alpha )$ $\theta$

Definition

Buchholz definierade sina funktioner enligt följande:

{\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 )\} \\&{}\kopp \{\psi _{\mu}(\xi )\mid \xi \in \alpha \cap C_{\nu }^{n}(\alpha )\kil \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 \inte \in C_{\nu }(\alpha ) \},\end{aligned}}

var

\omega

är den minsta transfinita ordinalen

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

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

är uppsättningen av additivt huvudtal i formen så att och och , där är klassen för alla ordningstalen.

{\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 \in \operatörsnamn {På} \}=\{\alpha \ i \operatörsnamn {På} |0<\alpha \wedge \forall \xi ,\eta <\alpha (\xi +\eta <\alpha )\}

På

Obs: Grekiska bokstäver betyder ordningsnumer överallt .

Gränsen för denna notation är Takeuchi-Feferman-Buchholz ordinal . $\psi _{0}(\varepsilon _{\Omega _{\omega }+1})$

Egenskaper

Buchholz visade följande egenskaper hos dessa funktioner:

$\psi _{\nu }(0)=\Omega _{\nu },$ särskilt, $\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{ och }}\nu \neq 0,$
$\theta (\varepsilon _{\Omega _{\nu }+1},0)=\psi _{0}(\varepsilon _{\Omega _{\nu}+1}){\text{ för }}0<\nu \leq \omega .$

Grundläggande sekvenser och normalformen för Buchholz-funktioner

Normal form

Normalformen för noll är 0. Om är en icke-nollordinal, då är normalformen för , där och , där varje ordinal också skrivs i 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 _{ i})$ $\psi _{\nu _{1}}(\beta _{1})\geq \psi _{\nu _{2}}(\beta _{2})\geq \cdots \geq \ psi _{\nu _{k}}(\beta _{k})$ $\beta _{i}$

Grundläggande sekvenser

Den grundläggande sekvensen för en gränsordinal med kofinalitet är en strikt ökande transfinit sekvens med längd och gräns , där är det th elementet i denna sekvens, det vill säga . $\alfa$ $\operatörsnamn {cof} (\alpha )=\beta$ ${\displaystyle (\alpha [\eta ])_{\eta <\beta ))$ $\beta$ $\alfa$ $\alpha [\eta ]$ $\eta$ ${\displaystyle \alpha =\sup\{\alpha [\eta ]|\eta <\operatörsnamn {cof} (\alpha )\))$

För gränsordningstal , skrivna i normal form, definieras de grundläggande sekvenserna enligt följande: $\alfa$

Om , var , då och , $\alpha =\psi _{\nu _{1}}(\beta _{1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\ psi _{\nu _{k}}(\beta _{k})$ $k\geq 2$ $\operatörsnamn {cof} (\alpha )=\operatörsnamn {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 ])$
Om , då och , $\alpha =\psi _{\omega }(0)$ $\operatörsnamn {cof} (\alpha )=\omega$ $\alpha [\eta ]=\psi _{\eta }(0)$
Om , då och , $\alpha =\psi _{\nu +1}(0)$ ${\displaystyle \operatörsnamn {cof} (\alpha )=\Omega _{\nu +1))$ $\alpha [\eta ]=\Omega _{\nu +1}[\eta ]=\eta$
Om , då och (observera att: ), $\alpha =\psi _{\nu}(\beta +1)$ $\operatörsnamn {cof} (\alpha )=\omega$ $\alpha [\eta ]=\psi _{\nu }(\beta )\cdot \eta$ ${\displaystyle \psi _{\nu }(0)=\Omega _{\nu ))$
Om och , då och , $\alpha =\psi _{\nu }(\beta )$ ${\displaystyle \operatorname {cof} (\beta )\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu <\nu \))$ $\operatörsnamn {cof} (\alpha )=\operatörsnamn {cof} (\beta )$ $\alpha [\eta ]=\psi _{\nu }(\beta [\eta ])$
Om och , då och , var . $\alpha =\psi _{\nu }(\beta )$ ${\displaystyle \operatörsnamn {cof} (\beta )\in \{\Omega _{\mu +1}\mid \mu \geq \nu \))$ $\operatörsnamn {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 förklaring av principerna för notation

Eftersom Buchholz arbetar i Zermelo-Fraenkel-systemet är varje ordinal lika med mängden av alla mindre ordtal, . Villkoret innebär att mängden innehåller alla ordningstal mindre än eller med andra 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 }\))$

Villkoret innebär att setet innehåller: $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 )$

alla ordningstal från föregående uppsättning , $C_{\nu }^{n}(\alpha )$

alla ordningstal som kan erhållas genom att additivt summera principalordningar från föregående uppsättning , $C_{\nu }^{n}(\alpha )$

alla ordtal som kan erhållas genom att använda ordtal (mindre än ) från föregående uppsättning som argument för funktioner , där . $\alfa$ $C_{\nu }^{n}(\alpha )$ ${\displaystyle \psi _{\mu ))$ $\mu \leq \omega$

Därför kan detta villkor skrivas om enligt följande:

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 är föreningen av alla mängder med , det vill säga är mängden av alla ordtal som kan bildas av ordtal av funktionerna + (tillägg) och , där och . $C_{\nu }^{n}(\alpha )$ $n<\omega$ $C_{\nu }(\alpha )=\bigcup _{n<\omega }C_{\nu}^{n}(\alpha )$ ${\displaystyle <\aleph _{\nu ))$ $\psi _{\mu }(\eta )$ $\mu \leq \omega$ $\eta <\alpha$

Då är den minsta ordinalen som inte hör till denna uppsättning. ${\displaystyle \psi _{\nu }(\alpha )=\min\{\gamma \mid \gamma \inte \in C_{\nu }(\alpha )\))$

Exempel

Tänk på följande exempel:

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

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

(eftersom det inte finns några funktionsvärden för , och 0 + 0 = 0).

{\displaystyle \psi _{\nu))

\eta <0

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

$C_{0}(1)$ innehåller alla möjliga summor av naturliga tal. Därför är den första transfinita ordningen, som är större än alla naturliga tal per definition. $\psi _{0}(0)=1$ $\psi _{0}(1)=\omega$

$C_{0}(2)$ innehåller alla deras möjliga summor. Därför, . $\psi _{0}(0)=1,\psi _{0}(1)=\omega$ ${\displaystyle \psi _{0}(2)=\omega ^{2))$

Om , då och . $\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 ))$

Om , då och är det minsta antalet epsilon , det vill säga den första fasta punkten . $\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 ))$

Om , då och . $\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))$ är det andra epsilonnumret ,

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

, det vill säga den första fasta punkten ,

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

$\varphi (\alpha ,1+\beta )=\psi _{0}(\Omega ^{\alpha }\beta )$ , där betecknar Veblen-funktionen , $\varphi$

$\psi _{0}(\Omega ^{\Omega })=\Gamma _{0}=\varphi (1,0,0)=\theta (\Omega ,0)$ , där betecknar Feferman-funktionen , och betecknar Feferman-Schütte-ordinalen $\theta$ $\Gamma_0$

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

– Ackermann ordinal ,

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

– Liten 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).

Låt oss nu se hur funktionen fungerar : $\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 vill säga den innehåller alla räknebara ordningstal. Innehåller därför alla möjliga summor av alla räknebara ordinaler, och är den första oräkneliga ordinalen som är större än alla räknebara ordinaler per definition, det vill säga den minsta ordinalen med kardinalitet .

C_{1}(0)

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

\aleph_1

Om , då och . $\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

, där är ett naturligt tal, ,

k

k\geq 2

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

För fallet innehåller uppsättningen funktioner med alla argument mindre än , det vill säga argument som t.ex $\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)$

och då

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

I allmänhet:

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

Anteckningar

↑ Buchholz, W. Ett nytt system av bevisteoretiska ordinalfunktioner (obestämd) // Annals of Pure and Applied Logic. - T. 32 .
↑ Jäger, G. -otillgängliga ordtal, kollapsande funktioner och ett rekursivt notationssystem // Arkiv f. matematik. Logik och Grundlagenf. : journal. - 1984. - Vol. 24 , nr. 1 . - S. 49-62 . $\rho$
↑ Buchholz, W.; Schütte, K. Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der -Separation und Bar-Induktion (tyska) // Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. klass: butik. — 1983. ${\displaystyle \Pi _{2}^{1))$

Länkar

Stora siffror
Tal	googol Shannon nummer Googolplex Skeves nummer Moser nummer Graham nummer TRÄD(3) Rayo nummer
Funktioner	Ackermann funktion Veblen funktion Psi-funktioner för Buchholz tetration Pentation Hyperoperator Snabbväxande hierarki Långsamt växande hierarki Härlig hierarki
Noteringar	Steinhaus-Moser notation Knuth pilnotation Conway pil notation Massiv Bowers Notation