Psi funkce Buchholze

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 16. ledna 2020; ověření vyžaduje 1 úpravu .

Buchholzovy funkce psi jsou hierarchií ordinálních skládacích funkcí , které zavedl německý matematik Wilfried Buchholz v roce 1986. [1] Tyto funkce jsou zjednodušenou verzí Fefermanových funkcí , ale stále mají stejnou sílu. Později tento přístup rozšířili němečtí matematici G. Jäger [2] a K. Schütte [3] . $\psi _{\nu }(\alpha )$ $\theta$

Definice

Buchholz definoval své funkce takto:

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

kde

\omega

je nejmenší transfinitní ordinála

\Omega _{\nu }={\begin{cases}1{\text{ if }}\nu =0\\{\text{kardinální číslo }}\aleph _{\nu }{\text { pokud }}\nu >0\end{cases}}

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

je množina aditivně hlavních čísel ve tvaru , že a a , kde je třída všech pořadových čísel.

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

zapnuto

Poznámka: Řecká písmena znamenají všude pořadové číslo .

Limit tohoto zápisu je Takeuchi-Feferman-Buchholz ordinál . $\psi _{0}(\varepsilon _{\Omega _{\omega }+1})$

Vlastnosti

Buchholz ukázal následující vlastnosti těchto funkcí:

$\psi _{\nu }(0)=\Omega _{\nu },$ zejména, $\psi _{0}(0)=1,$
$\psi _{\nu }(\alpha )\v 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{ a }}\nu \neq 0,$
$\theta (\varepsilon _{\Omega _{\nu }+1},0)=\psi _{0}(\varepsilon _{\Omega _{\nu }+1}){\text{ pro }}0<\nu \leq \omega .$

Základní posloupnosti a normální tvar pro Buchholzovy funkce

Normální forma

Normální tvar pro nulu je 0. Jestliže je nenulová řadová číslovka, pak normální tvar pro je , kde a , kde se každá ordinální číslo také píše v normálním tvaru. $\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})$ $\beta _{i}$

Základní sekvence

Základní posloupnost pro limitní ordinálu s kofinalitou je přísně rostoucí transfinitní posloupnost s délkou a limitou , kde je tý prvek této posloupnosti, tedy . $\alpha$ $\operatorname {cof} (\alpha )=\beta$ ${\displaystyle (\alpha [\eta ])_{\eta <\beta ))$ $\beta$ $\alpha$ $\alpha [\eta ]$ $\eta$ ${\displaystyle \alpha =\sup\{\alpha [\eta ]|\eta <\jméno operátora {cof} (\alpha )\))$

Pro limitní ordinály psané v normálním tvaru jsou základní posloupnosti definovány takto: $\alpha$

Pokud , kde , pak a , $\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 ])$
Pokud , pak a , $\alpha =\psi _{\omega }(0)$ $\operatorname {cof} (\alpha )=\omega$ $\alpha [\eta ]=\psi _{\eta }(0)$
Pokud , pak a , $\alpha =\psi _{\nu +1}(0)$ ${\displaystyle \operatorname {cof} (\alpha )=\Omega _{\nu +1))$ $\alpha [\eta ]=\Omega _{\nu +1}[\eta ]=\eta$
Pokud , pak a (všimněte si, že: ), $\alpha =\psi _{\nu }(\beta +1)$ $\operatorname {cof} (\alpha )=\omega$ $\alpha [\eta ]=\psi _{\nu }(\beta )\cdot \eta$ ${\displaystyle \psi _{\nu }(0)=\Omega _{\nu ))$
Pokud a , pak a , $\alpha =\psi _{\nu }(\beta )$ ${\displaystyle \operatorname {cof} (\beta )\v \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu <\nu \))$ $\operatorname {cof} (\alpha )=\operatorname {cof} (\beta )$ $\alpha [\eta ]=\psi _{\nu }(\beta [\eta ])$
Pokud a , pak a , kde . $\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}}\vpravo.$

Vysvětlení principů zápisu

Protože Buchholz pracuje v systému Zermelo-Fraenkel , každá ordinála se rovná množině všech menších ordinál, . Podmínka znamená, že množina obsahuje všechny ordinály menší než nebo jinými slovy . $\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 }\))$

Podmínka znamená, že sada obsahuje: $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 )$

všechny pořadové čísla z předchozí sady , $C_{\nu }^{n}(\alpha )$

všechny ordinály, které lze získat aditivním sečtením hlavních řadových řad z předchozí množiny , $C_{\nu }^{n}(\alpha )$

všechny pořadové čísla, které lze získat použitím pořadových čísel (menších než ) z předchozí množiny jako argumentů funkcí , kde . $\alpha$ $C_{\nu }^{n}(\alpha )$ ${\displaystyle \psi _{\mu ))$ $\mu \leq \omega$

Proto lze tuto podmínku přepsat takto:

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

Sjednocení všech množin s , tedy , je množina všech ordinálů, které lze z ordinálů vytvořit funkcemi + (sčítání) a , kde a . $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$

Pak je nejmenší řadové číslo, které do této množiny nepatří. ${\displaystyle \psi _{\nu }(\alpha )=\min\{\gamma \mid \gamma \not \in C_{\nu }(\alpha )\))$

Příklady

Zvažte následující příklady:

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

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

(protože neexistují žádné funkční hodnoty pro , a 0 + 0 = 0).

{\displaystyle \psi _{\nu ))

\eta <0

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

$C_{0}(1)$ obsahuje všechny možné součty přirozených čísel. Proto je první transfinitní ordinální číslo, které je podle definice větší než všechna přirozená čísla. $\psi _{0}(0)=1$ $\psi _{0}(1)=\omega$

$C_{0}(2)$ obsahuje všechny jejich možné součty. Proto, . $\psi _{0}(0)=1,\psi _{0}(1)=\omega$ $\psi _{0}(2)=\omega ^{2}$

Pokud , pak a . $\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 ))$

Jestliže , pak a je nejmenší číslo epsilon , tedy první pevný bod . $\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 }$

Pokud , pak a . $\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))$ je druhé epsilon číslo ,

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

, tedy první pevný bod ,

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

$\varphi (\alpha ,1+\beta )=\psi _{0}(\Omega ^{\alpha }\beta )$ , kde označuje funkci Veblen , $\varphi$

$\psi _{0}(\Omega ^{\Omega })=\Gamma _{0}=\varphi (1,0,0)=\theta (\Omega ,0)$ , kde označuje Fefermanovu funkci , a označuje Feferman-Schütte ordinál $\theta$ $\Gamma_0$

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

– Ackermann ordinál ,

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

– Small Veblen ordinál ,

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

– Great Veblen ordinál ,

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

Nyní se podívejme, jak funkce funguje : $\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 \}

, to znamená, že obsahuje všechny počitatelné ordinály. Proto obsahuje všechny možné součty všech počitatelných řadových čísel a je první nepočitatelnou ordinálou, která je podle definice větší než všechny spočetné ordinály, to znamená nejmenší ordinální číslo s kardinalitou .

C_{1}(0)

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

\aleph_1

Pokud , pak a . $\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

, kde je přirozené číslo, ,

k

k\geq 2

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

Pro tento případ sada obsahuje funkce se všemi argumenty menšími než , tedy argumenty jako např $\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)$

a pak

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

Obecně:

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

Poznámky

↑ Buchholz, W. A New System of Proof-Theoretic Ordinal Functions (neurčité) // Annals of Pure and Applied Logic. - T. 32 .
↑ Jäger, G. -nepřístupné ordinály, skládací funkce a systém rekurzivní notace // Archiv f. matematika. Logika a Grundlagenf. : deník. - 1984. - Sv. 24 , č. 1 . - str. 49-62 . $\rho$
↑ Buchholz, W.; Schütte, K. Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der -Separation und Bar-Induktion (německy) // Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. třída: obchod. — 1983. ${\displaystyle \Pi _{2}^{1))$

Odkazy

Velká čísla
Čísla	googol Shannonovo číslo Googolplex Skewes číslo Moserovo číslo Grahamovo číslo STROM(3) Rayo číslo
Funkce	Ackermannova funkce Funkce Veblen Psi funkce Buchholze tetování Pentace Hyperoperátor Rychle rostoucí hierarchie Pomalu rostoucí hierarchie Hardyho hierarchie
Notace	Steinhaus-Moserova notace Knuthova šipková notace Notace Conwayovy šipky Masivní Bowers Notace