Buchholz Pszi-függvényei

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. január 16-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A Buchholz-pszi-függvények az ordinális összeomló függvények hierarchiája , amelyet Wilfried Buchholz német matematikus vezetett be 1986-ban. [1] Ezek a függvények a Feferman-függvények leegyszerűsített változatai , de még mindig ugyanaz a teljesítmény. Később ezt a megközelítést G. Jäger [2] és K. Schütte [3] német matematikusok is kiterjesztették . $\psi _{\nu }(\alpha )$ $\theta$

Definíció

Buchholz a következőképpen határozta meg funkcióit:

{\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{igazított}}

ahol

\omega

a legkisebb transzfinit sorszámú

\Omega _{\nu }={\begin{cases}1{\text{ if }}\nu =0\\{\text{kardinális szám }}\aleph _{\nu }{\text { if }}\nu >0\end{cases}}

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

az additív főszámok halmaza olyan formában , hogy és és , ahol az összes sorszám osztálya.

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

On

Megjegyzés: A görög betűk mindenhol sorszámot jelentenek .

Ennek a jelölésnek a határa a Takeuchi-Feferman-Buchholz sorszám . $\psi _{0}(\varepsilon _{\Omega _{\omega }+1})$

Tulajdonságok

Buchholz ezeknek a függvényeknek a következő tulajdonságait mutatta meg:

$\psi _{\nu }(0)=\Omega _{\nu },$ különösen, $\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{ és }}\nu \neq 0,$
$\theta (\varepsilon _{\Omega _{\nu }+1},0)=\psi _{0}(\varepsilon _{\Omega _{\nu }+1}){\text{ for }}0<\nu \leq \omega .$

Alapvető sorozatok és a Buchholz-függvények normálalakja

Normál forma

A nulla normálalakja 0. Ha nem nulla sorszámú, akkor a normálalak , ahol és , ahol minden sorszámot normál formában is írunk. $\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 _{ én})$ $\psi _{\nu _{1}}(\beta _{1})\geq \psi _{\nu _{2}}(\beta _{2})\geq \cdots \geq \ psi _{\nu _{k}}(\beta _{k})$ $\beta _{i}$

Alapvető sorozatok

A kofinalitású határsorrend alapvető sorozata egy szigorúan növekvő transzfinit sorozat , amelynek hossza és határértéke , ahol ennek a sorozatnak a th eleme, azaz . $\alpha$ $\operatorname {cof} (\alpha )=\beta$ ${\displaystyle (\alpha [\eta ])_{\eta <\beta ))$ $\beta$ $\alpha$ $\alpha [\eta ]$ $\eta$ ${\displaystyle \alpha =\sup\{\alpha [\eta ]|\eta <\operatorname {cof} (\alpha )\))$

Normál formában írt határértékek esetén az alapvető sorozatok a következők: $\alpha$

Ha , hol , akkor és , $\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 ])$
Ha , akkor és , $\alpha =\psi _{\omega }(0)$ $\operatorname {cof} (\alpha )=\omega$ $\alpha [\eta ]=\psi _{\eta }(0)$
Ha , akkor és , $\alpha =\psi _{\nu +1}(0)$ ${\displaystyle \operatorname {cof} (\alpha )=\Omega _{\nu +1))$ $\alpha [\eta ]=\Omega _{\nu +1}[\eta ]=\eta$
Ha , akkor és (jegyezd meg, hogy: ), $\alpha =\psi _{\nu }(\beta +1)$ $\operatorname {cof} (\alpha )=\omega$ $\alpha [\eta ]=\psi _{\nu }(\beta )\cdot \eta$ ${\displaystyle \psi _{\nu }(0)=\Omega _{\nu ))$
Ha és , akkor és , $\alpha =\psi _{\nu }(\beta )$ ${\displaystyle \operatorname {cof} (\beta )\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu <\nu \))$ $\operátornév {cof} (\alpha )=\operátornév {cof} (\beta )$ $\alpha [\eta ]=\psi _{\nu }(\beta [\eta ])$
Ha és , akkor és , hol . $\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.$

A jelölés alapelveinek magyarázata

Mivel Buchholz a Zermelo-Fraenkel rendszerben dolgozik , minden ordinális egyenlő az összes kisebb sorszámmal, . A feltétel azt jelenti, hogy a halmaz minden sorszámot tartalmaz kisebb vagy más szavakkal . $\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 }\))$

A feltétel azt jelenti, hogy a készlet tartalmazza: $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 )$

az előző halmaz összes sorszáma , $C_{\nu }^{n}(\alpha )$

az összes sorszám, amelyet az előző halmaz fő sorszámainak összeadásával kaphatunk , $C_{\nu }^{n}(\alpha )$

minden olyan sorszám, amelyet úgy kaphatunk meg, hogy az előző halmazból a függvények argumentumaiként használjuk az előző halmaz sorszámait , ahol . $\alpha$ $C_{\nu }^{n}(\alpha )$ ${\displaystyle \psi _{\mu ))$ $\mu \leq \omega$

Ezért ez a feltétel a következőképpen írható át:

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

Így az összes halmaz uniója -val , azaz az összes sorszámú halmaza, amely a + (összeadás) és a , ahol és függvények által ordinálisokból képezhető . $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$

Ezután a legkisebb sorszám, amely nem tartozik ebbe a halmazba. ${\displaystyle \psi _{\nu }(\alpha )=\min\{\gamma \mid \gamma \not \in C_{\nu }(\alpha )\))$

Példák

Tekintsük a következő példákat:

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

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

(mivel a , és a 0 + 0 = 0 esetén nincsenek függvényértékek ).

{\displaystyle \psi _{\nu ))

\eta <0

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

$C_{0}(1)$ tartalmazza a természetes számok összes lehetséges összegét. Ezért az első transzfinit sorszám, amely definíció szerint nagyobb minden természetes számnál. $\psi _{0}(0)=1$ $\psi _{0}(1)=\omega$

$C_{0}(2)$ tartalmazza az összes lehetséges összeget. Ezért ,. $\psi _{0}(0)=1,\psi _{0}(1)=\omega$ $\psi _{0}(2)=\omega ^{2}$

Ha , akkor és . $\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 ))$

Ha , akkor és a legkisebb szám epszilon , azaz az első fix pont . $\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 }$

Ha , akkor és . $\alpha =\Omega +1$ $C_{0}(\alpha )=\{0,1,\ldots ,\psi _{0}(\Omega )=\varepsilon _{0},\ldots ,\varepsilon _{0}+\ varepszilon _{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))$ a második epszilonszám ,

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

, azaz az első fix pont ,

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

$\varphi (\alpha ,1+\beta )=\psi _{0}(\Omega ^{\alpha }\beta )$ , ahol a Veblen függvényt jelöli , $\varphi$

$\psi _{0}(\Omega ^{\Omega })=\Gamma _{0}=\varphi (1,0,0)=\theta (\Omega ,0)$ , ahol a Feferman függvény , és a Feferman -Schütte sorszám $\theta$ $\Gamma_0$

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

– Ackermann sorszámú ,

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

– Kis Veblen sorszámú ,

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

– Nagy Veblen sorszám ,

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

Most nézzük meg, hogyan működik a függvény : $\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 \}

, azaz minden megszámlálható sorszámot tartalmaz. Ezért tartalmazza az összes megszámlálható ordinális összes lehetséges összegét, és az első megszámlálhatatlan sorszám, amely definíció szerint nagyobb, mint az összes megszámlálható sorszám, vagyis a legkisebb számsorszámú .

C_{1}(0)

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

\aleph_1

Ha , akkor és . $\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

, ahol egy természetes szám, ,

k

k\geq 2

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

Ebben az esetben a halmaz olyan függvényeket tartalmaz , amelyek összes argumentuma kisebb, mint , azaz olyan argumentumokat, mint pl $\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)$

és akkor

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

Általában:

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

Jegyzetek

↑ Buchholz, W. A bizonyítási-elméleti ordinális függvények új rendszere (határozatlan) // Annals of Pure and Applied Logic. - T. 32 .
↑ Jäger, G. -elérhetetlen sorszámok, összeomló függvények és rekurzív jelölésrendszer // Archiv f. matematika. Logika és Grundlagenf. : folyóirat. - 1984. - 1. évf. 24 , sz. 1 . - P. 49-62 . $\rho$
↑ Buchholz, W.; Schütte, K. Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der -Separation und Bar-Induktion (német) // Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. osztály: bolt. – 1983. ${\displaystyle \Pi _{2}^{1))$

Linkek

Nagy számok
Számok	googol Shannon szám Googolplex Skewes szám Moser szám Graham szám FA (3) Rayo szám
Funkciók	Ackermann függvény Veblen funkció Buchholz Pszi-függvényei tetració Pentation Hiperoperátor Gyorsan növekvő hierarchia Lassan növekvő hierarchia Hardy hierarchia
Jelölések	Steinhaus-Moser jelölés Knuth nyíl jelölése Conway nyíl jelölése Massive Bowers jelölés