Buchholzin Psi-funktiot

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 16. tammikuuta 2020 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Buchholzin psi-funktiot ovat saksalaisen matemaatikko Wilfried Buchholzin vuonna 1986 käyttöön ottamaa järjestysjärjestyksen romahtavien funktioiden hierarkiaa . [1] Nämä funktiot ovat yksinkertaistettu versio Feferman-funktioista [ , mutta niillä on silti sama teho. Myöhemmin tätä lähestymistapaa laajensivat saksalaiset matemaatikot G. Jäger [2] ja K. Schütte [3] . $\psi _{\nu }(\alpha )$ $\theta$

Määritelmä

Buchholz määritteli tehtävänsä seuraavasti:

{\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{aligned}}

missä

\omega

on pienin transfiniittinen järjestysluku

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

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

on joukko additiivisesti pääasiallisia numeroita sellaisessa muodossa , että ja ja , jossa on kaikkien järjestyslukujen luokka.

{\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 \operaattorinimi {On} \}=\{\alpha \ in \operaattorinimi {On} |0<\alpha \wedge \forall \xi ,\eta <\alpha (\xi +\eta <\alpha )\}

Päällä

Huomautus: Kreikan kirjaimet tarkoittavat järjestyslukuja kaikkialla .

Tämän merkinnän raja on Takeuchi-Feferman-Buchholz järjestysluku . $\psi _{0}(\varepsilon _{\Omega _{\omega }+1})$

Ominaisuudet

Buchholz osoitti näiden funktioiden seuraavat ominaisuudet:

$\psi _{\nu }(0)=\Omega _{\nu },$ erityisesti, $\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{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{ ja }}\nu \neq 0,$
$\theta (\varepsilon _{\Omega _{\nu }+1},0)=\psi _{0}(\varepsilon _{\Omega _{\nu }+1}){\text{ for }}0<\nu \leq \omega .$

Perussekvenssit ja normaalimuoto Buchholz-funktioille

Normaali muoto

Nollan normaalimuoto on 0. Jos on nollasta poikkeava järjestysluku, niin normaalimuoto on , missä ja , jossa jokainen järjestysluku kirjoitetaan myös normaalimuodossa. $\alpha$ $\alpha$ $\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})$ ${\displaystyle \beta _{i))$

Perussekvenssit

Kofinaalisuuden rajajärjestyksen perussekvenssi on tiukasti kasvava transfiniittijono, jonka pituus ja raja on , missä on tämän sekvenssin th elementti, eli . $\alpha$ $\operaattorin nimi {cof} (\alpha )=\beta$ ${\displaystyle (\alpha [\eta ])_{\eta <\beta ))$ $\beeta$ $\alpha$ $\alpha [\eta ]$ $\eta$ ${\displaystyle \alpha =\sup\{\alpha [\eta ]|\eta <\operaattorinimi {cof} (\alpha )\))$

Normaalimuodossa kirjoitettujen rajajärjestysten perussekvenssit määritellään seuraavasti: $\alpha$

Jos , missä , sitten ja , $\alpha =\psi _{\nu _{1}}(\beta _{1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\ psi _{\nu _{k}}(\beta _{k})$ $k\geq 2$ $\operaattorinnimi {cof} (\alpha )=\operaattorin nimi {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 ])$
Jos , sitten ja $\alpha =\psi _{\omega }(0)$ $\operaattorin nimi {cof} (\alpha )=\omega$ $\alpha [\eta ]=\psi _{\eta }(0)$
Jos , sitten ja $\alpha =\psi _{\nu +1}(0)$ ${\displaystyle \operaattorinnimi {cof} (\alpha )=\Omega _{\nu +1))$ $\alpha [\eta ]=\Omega _{\nu +1}[\eta ]=\eta$
Jos , sitten ja (huomaa, että: ), $\alpha =\psi _{\nu }(\beta +1)$ $\operaattorin nimi {cof} (\alpha )=\omega$ $\alpha [\eta ]=\psi _{\nu }(\beta )\cdot \eta$ ${\displaystyle \psi _{\nu }(0)=\Omega _{\nu ))$
Jos ja , niin ja $\alpha =\psi _{\nu }(\beta )$ ${\displaystyle \operatorname {cof} (\beta )\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu <\nu \))$ $\operaattorinnimi {cof} (\alpha )=\operaattorin nimi {cof} (\beta )$ $\alpha [\eta ]=\psi _{\nu }(\beta [\eta ])$
Jos ja , niin ja missä . $\alpha =\psi _{\nu }(\beta )$ ${\displaystyle \operatorname {cof} (\beta )\in \{\Omega _{\mu +1}\mid \mu \geq \nu \))$ $\operaattorin nimi {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.$

Selitys merkinnän periaatteista

Koska Buchholz toimii Zermelo-Fraenkel-järjestelmässä , jokainen ordinaal on yhtä suuri kuin kaikkien pienempien ordinaaleiden joukko, . Ehto tarkoittaa, että joukko sisältää kaikki järjestysluvut pienempiä tai toisin sanoen . $\alpha$ ${\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 }\))$

Ehto tarkoittaa, että sarja sisältää: $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 )$

kaikki järjestysluvut edellisestä sarjasta , $C_{\nu }^{n}(\alpha )$

kaikki järjestysluvut , jotka voidaan saada summaamalla yhteen edellisen joukon pääordinaaleja , $C_{\nu }^{n}(\alpha )$

kaikki järjestysluvut, jotka voidaan saada käyttämällä edellisen joukon ordinaaleja (pieniä kuin ) funktioiden argumentteina , missä . $\alpha$ $C_{\nu }^{n}(\alpha )$ ${\displaystyle \psi _{\mu ))$ $\mu \leq \omega$

Siksi tämä ehto voidaan kirjoittaa uudelleen seuraavasti:

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

Siten kaikkien joukkojen liitto , eli , on joukko kaikista järjestysluvuista, jotka voidaan muodostaa ordinaaleista funktioilla + (lisäys) ja , missä ja . $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$

Sitten on pienin järjestysluku, joka ei kuulu tähän joukkoon. ${\displaystyle \psi _{\nu }(\alpha )=\min\{\gamma \mid \gamma \not \in C_{\nu }(\alpha )\))$

Esimerkkejä

Harkitse seuraavia esimerkkejä:

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

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

(koska arvoille , ja 0 + 0 = 0 ei ole funktioarvoja ).

{\displaystyle \psi _{\nu ))

\eta <0

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

$C_{0}(1)$ sisältää kaikki mahdolliset luonnollisten lukujen summat. Siksi on ensimmäinen transfiniittinen järjestysluku, joka on määritelmän mukaan suurempi kuin kaikki luonnolliset luvut. $\psi _{0}(0)=1$ $\psi _{0}(1)=\omega$

$C_{0}(2)$ sisältää kaikki niiden mahdolliset summat. Siksi ,. $\psi _{0}(0)=1,\psi _{0}(1)=\omega$ $\psi _{0}(2)=\omega ^{2}$

Jos , sitten ja . $\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 ))$

Jos , niin ja on pienin luku epsilon , eli ensimmäinen kiinteä piste . $\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))$ $\alpha =\omega ^{\alpha }$

Jos , sitten ja . $\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))$ on toinen epsilonin numero ,

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

, eli ensimmäinen kiinteä piste ,

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

$\varphi (\alpha ,1+\beta )=\psi _{0}(\Omega ^{\alpha }\beta )$ , jossa tarkoittaa Veblen-funktiota , $\varphi$

$\psi _{0}(\Omega ^{\Omega })=\Gamma _{0}=\varphi (1,0,0)=\theta (\Omega ,0)$ , jossa tarkoittaa Feferman-funktiota ja tarkoittaa Feferman-Schütten järjestyslukua $\theta$ $\Gamma_0$

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

– Ackermann ordinaal ,

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

– Pieni Veblen ordinaal ,

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

– Great Veblen ordinaal ,

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

Katsotaan nyt kuinka funktio toimii : $\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 \}

, eli se sisältää kaikki laskettavat järjestysluvut. Siksi sisältää kaikki mahdolliset kaikkien laskettavien ordinaalien summat, ja on ensimmäinen laskematon järjestysluku, joka on määritelmän mukaan suurempi kuin kaikki laskettavat ordinaalit, eli pienin järjestysluku, jonka kardinaalisuus on .

C_{1}(0)

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

\aleph_1

Jos , sitten ja . $\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

, missä on luonnollinen luku, ,

k

k\geq 2

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

Tapauksessa joukko sisältää funktioita , joiden kaikki argumentit ovat pienempiä kuin , eli argumentit, kuten $\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)$

ja sitten

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

Yleisesti:

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

Muistiinpanot

↑ Buchholz, W. Uusi todistusteoreettisten ordinaalfunktioiden järjestelmä (määrittämätön) // Annals of Pure and Applied Logic. - T. 32 .
↑ Jäger, G. -pääsemättömät ordinaalit, kutistuvat funktiot ja rekursiivinen merkintäjärjestelmä // Archiv f. matematiikka. Logiikka ja Grundlagenf. : päiväkirja. - 1984. - Voi. 24 , ei. 1 . - s. 49-62 . $\rho$
↑ Buchholz, W.; Schütte, K. Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der -Separation und Bar-Induktion (saksa) // Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. luokka: kauppa. – 1983. ${\displaystyle \Pi _{2}^{1))$

Linkit

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ä