Funkcje psi Buchholza

Funkcje psi Buchholza to hierarchia jednoargumentowych funkcji porządkowych wprowadzona $są$ wersją ${\ displaystyle \ theta}$ -funkcje, ale mimo to mają taką samą siłę jak te. Później podejście to rozszerzyli Jaiger i Schütte .

Definicja

Buchholz zdefiniował swoje funkcje w następujący sposób. Definiować:

• ₀ Ω _ξ = ω _ξ jeśli ξ > 0, Ω = 1

Funkcje ψ _v (α) dla α liczby porządkowej, v liczby porządkowej co najwyżej ω są definiowane przez indukcję po α w następujący sposób:

• ψ _v (α) jest najmniejszą liczbą porządkową nie w C _v (α)

gdzie C _v (α) jest najmniejszym zbiorem takim, że

• C _v (α) zawiera wszystkie liczby porządkowe mniejsze niż Ω _v
• C _v (α) jest domknięte przy dodawaniu porządkowym
• C _v (α) jest domknięte pod funkcjami ψ _u (dla u ≤ω) zastosowanymi do argumentów mniejszych od α.

Granicą tego zapisu jest liczba porządkowa Takeuti – Feferman – Buchholz .

Nieruchomości

Niech będzie klasą $porządkowych$ głównych liczb . Buchholz wykazał następujące własności tej funkcji:

• ${\ Displaystyle \ psi _ {\ nu} (0) = \ Omega _ {\ nu},}$
• ${\ Displaystyle \ psi _ {\ nu} (\ alfa) \ w P}$
• ${\ Displaystyle \ psi _ {\ nu} (\ alfa + 1) = \ min \{\gamma \in P:\psi _{\nu }(\alpha )<\gamma \}{\text{if }}\alpha \in C_{\nu }(\alpha ),}$
• ${\ Displaystyle \ Omega _ {\ nu} \ równoważnik \ psi _ {\ nu} (\ alfa) <\ Omega _ {\ nu + 1}}$
• ${\ Displaystyle \ psi _ {0} (\ alfa) = \ omega ^ {\ alfa} {\ tekst {jeśli}} \ alfa <\ varepsilon _ {0}, }$
• ${\ Displaystyle \ psi _ {\ nu} (\ alfa) = \ omega ^ {\ Omega _ {\ nu} + \alpha }{\text{ if }}\alpha <\varepsilon _{\Omega _{\nu }+1}{\text{i }}\nu \neq 0,}$
• ${\ Displaystyle \ theta (\ varepsilon _ {\ Omega _ {\ nu} + 1}, 0) = \ psi (\ varepsilon _ {\ Omega _ {\ nu} + 1}) {\ tekst {dla}} 0 <\nu \leq \omega .}$

Ciągi podstawowe i postać normalna funkcji Buchholza

Normalna forma

Postać normalna dla 0 to 0. Jeśli jest niezerową liczbą porządkową $Displaystyle$$\ alpha <\ Omega _ {\ omega}},$ to postać normalna dla $displaystyle \ alpha} }$ jest ${\ Displaystyle \ alfa = \ psi _ {\ nu _ {1}} (\ beta _ {1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\psi _{\nu _{k}}(\beta _{k})}$ gdzie ${\ Displaystyle \ nu _ {i} \ in \ mathbb {N} _ {0}, k \ in \ mathbb {N} _ { >0},\beta _{i}\in C_{\nu _{i}}(\beta _{i})}$ i $cdots \ geq \ psi _ {\ nu _ {k}} (\ beta _ {k})} i$${\ Displaystyle \ psi _ {\ nu _ {1}} (\ beta _ {1}) \ geq \ psi _ {\ nu _ {2}} (\ beta _ {2}) \ geq$$każdy$ jest zapisany w normalnej formie.

Podstawowe sekwencje

Sekwencja podstawowa dla liczby porządkowej ze współfinalnością $Displaystyle \ operatorname {cof} (\ alfa) = \ beta}$$)$${\ Displaystyle (\ alfa [\ eta]) _ {\ eta <\ beta}}$ jest ściśle rosnącą sekwencją o długości ${\ Displaystyle \ beta}$ i z granicą ${\ Displaystyle \ alfa}$ , gdzie $\ alpha [\ eta ]}$${\$$displaystyle$ jest elementem tej sekwencji. Jeśli jest następcą porządkowym, to ${\ Displaystyle \ alfa [0] = \ alfa -1}$$Displaystyle \ operatorname {cof} (\ alfa) = 1},$$=$ a sekwencja podstawowa ma tylko jeden element . Jeśli ${\ Displaystyle \ alfa}$ jest graniczną liczbą porządkową, to ${\ Displaystyle \ operatorname {cof} (\ alfa) \ w \ {\ omega \}\cup \{\Omega _{\mu +1}\mid \mu \geq 0\}}$ .

Dla niezerowych liczb porządkowych , zapisanych w postaci normalnej, podstawowe sekwencje są zdefiniowane w następujący sposób: ${\ Displaystyle \ alpha <\ Omega _ {\ omega}}$

1. Jeśli ${\ Displaystyle \ alfa = \ psi _ {\ nu _ {1}} (\ beta _ { 1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\psi _{\nu _{k}}(\beta _{k})}$ gdzie ${\ Displaystyle k \ geq 2}$ następnie ${\ Displaystyle \ operatorname {cof} (\ alfa) = \ operatorname {cof} (\ psi _ { \nu _{k}}(\beta _{k}))}$ i ${\ Displaystyle \ alfa [\ eta ] = \ psi _ {\ nu _ {1}} (\ beta _ {1}) + \ cdots + \ psi _ {\ nu _ {k -1}}(\beta _{k-1})+(\psi _{\nu _{k}}(\beta _{k})[\eta ]),}$
2. Jeśli ${\ Displaystyle \ alfa = \ psi _ {0} (0) = 1}$ , to ${\ Displaystyle \ nazwa operatora {cof} (\ alfa) = 1}$ i ${\ Displaystyle \ alfa [0] = 0}$ ,
3. Jeśli ${\ Displaystyle \ alfa = \ psi _ {\ nu + 1} (0)}$ , to ${\ Displaystyle \ operatorname {cof} (\ alfa ) = \ Omega _ {\ nu +1}}$ i ${\ Displaystyle \ alfa [\ eta ] = \ Omega _ {\ nu + 1} [\ eta ]=\eta}$ ,
4. Jeśli ${\ Displaystyle \ alfa = \ psi _ {\ nu} (\ beta + 1)}$ to ${\ Displaystyle \ operatorname {cof} (\ alfa) = \ omega}$ i ${\ Displaystyle \ alfa [\ eta ] = \ psi _ {\ nu} (\ beta) \ cdot \ eta} ($ i uwaga: ${\ Displaystyle \ psi _ {\ nu} (0) = \ Omega _ {\ nu}}$ ),
5. α $\ nu} (\ beta)}$${\ Displaystyle \operatorname {cof} (\beta )\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu <\nu \}}$ i następnie ${\ Displaystyle \ nazwa operatora {cof} (\ alfa) = \ nazwa operatora {cof} (\ beta)}$ i ${\ Displaystyle \ alfa [\ eta] = \ psi _{\nu }(\beta [\eta ])}$ ,
6. Jeśli ${\ Displaystyle \ alfa = \ psi _ {\ nu} (\ beta)}$ i ${\ Displaystyle \ nazwa operatora {cof } (\ beta) \ in \ {\ Omega _ {\ mu + 1} \ mid \ mu \ geq \ nu \}}$ następnie ${\ Displaystyle \ operatorname {cof} (\ alfa) = \ omega}$ i ${\ Displaystyle \ alfa [\ eta] = \ psi _ {\ nu} (\ beta [\ gamma [\ eta]])}$ gdzie ${\ Displaystyle \ lewo \ {{\ rozpocząć {tablica} {lcr} \ gamma [0] = \ Omega _{\mu }\\\gamma [\eta +1]=\psi _{\mu }(\beta [\gamma [\eta ]])\\\end{array}}\right.}$ .

Wyjaśnienie

$,$ pracuje w teorii mnogości Zermelo-Fraenkla, co $jest$ zbiorowi Wtedy warunek oznacza, że ​​zestaw do $α$${0} (\ alfa)}$$C_ {\ nu$$obejmuje$${\ Displaystyle C_ { \nu }^{0}(\alpha )=\{\beta \mid \beta <\Omega _{\nu }\}}$ wszystkie liczby porządkowe mniejsze niż innymi słowy .

Warunek ${\ Displaystyle C _ {\ nu} ^ {n + 1} (\ alfa) = C _ {\ nu} ^ {n} (\ alfa) \ kubek \ {\ gamma \ mid P (\ gamma )\subseteq C_{\nu }^{n}(\alpha )\}\cup \{\psi _{\mu }(\xi)\mid \xi \in \alpha \cap C_{\nu }^{ n} (\ alfa) \ klin \ mu \ równoważnik \ omega \}} oznacza, że ​​zestaw$ zawiera: do $} (\ alfa)}$

• wszystkie liczby porządkowe z poprzedniego zestawu $\ Displaystyle C _ {\ nu} ^ {n} (\ alfa)}$ ,
• ${\ Displaystyle C _ {\ nu} ^ {n} (\ alfa)}$ , które można uzyskać przez zsumowanie addytywnie głównych liczb porządkowych z poprzedniego zbioru do ,
• $C _ {\ nu} ^ {n} (\ alpha)}$ można uzyskać, stosując liczby porządkowe mniejsze niż ${\ Displaystyle \ psi _ {\ mu}}$ poprzedniego zestawu jako argumenty funkcji $Displaystyle$ μ $\ Displaystyle \ mu \ leq \ omega} μ {\ Displaystyle \ psi _ {\ mu}$ }

Dlatego możemy przepisać ten warunek jako:

${\ Displaystyle C _ {\ nu} ^ {n + 1} (\ alfa) = \ {\ beta + \ gamma, \ psi _ {\ mu} (\ eta) \ mid \ beta, \ gamma, \ eta \ in C_{\nu }^{n}(\alpha )\wedge \eta <\alpha \wedge \mu \leq \omega \}.}$

$omega} C _ {\ nu} ^ {n} (\ alfa)} oznacza zbiór wszystkich liczb porządkowych,$ połączenie wszystkich zbiorów n $n$$<\ omega$ . które można wygenerować z liczb porządkowych $)$ funkcji + (dodatek) i ${\ Displaystyle \ psi _ {\ mu} (\$ } ${\ Displaystyle \ mu \ równoważnik \ omega}$ i ${\ Displaystyle \ eta <\ alfa}$ .

${\ Displaystyle \ psi _ {\ nu} (\ alfa) = \ min \ {\ gamma \ mid \ gamma \ nie \ w C_$ min to najmniejsza liczba porządkowa, która nie należy do tego zbioru.

Przykłady

Rozważ następujące przykłady:

${\ Displaystyle C_ {0} ^ {0} (\ alfa) = \ {0 \} = \ {\ beta \ mid \ beta <1 \} ,}$

${\ Displaystyle C_ {0} (0) = \ {0 \}}$ (ponieważ nie ma funkcji ${\ Displaystyle \ psi (\ eta <0)}$ i 0 + 0 = 0).

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

${\ Displaystyle C_ {0} (1)}$ obejmuje ${\ Displaystyle \ psi _ {0} (0) = 1}$ i wszystkie możliwe sumy liczb naturalnych, a zatem ${\ Displaystyle \ psi _ {0} (1) = \ omega}$ - pierwsza pozaskończona liczba porządkowa, która z definicji jest większa niż wszystkie liczby naturalne.

${\ Displaystyle C_ {0} (2)}$ obejmuje ${\ Displaystyle \ psi _ {0} (0) = 1, \ psi _ {0} ( 1) = \ omega}$ i wszystkie możliwe ich sumy, a zatem ${\ Displaystyle \ psi _ {0} (2) = \ omega ^ {2}}$ .

Jeśli ${\ Displaystyle \ alfa = \ omega},$${\ Displaystyle C_ {0} (\ alfa) = \ {0, \ psi (0) = 1, \ ldots, \ psi (1) = \ omega, \ ldots, \ psi ( 2) = \ omega ^ {2}, \ ldots, \ psi (3) = \ omega ^ {3}, \ ldots \}}$ do i ${\ Displaystyle \ psi _ {0} (\ omega )=\omega ^{\omega}}$ .

Jeśli $\ Displaystyle \ alfa = \ Omega},$${\ Displaystyle C_ {0} (\ alfa) = \ {0, \ psi (0) = 1, \ ldots, \ psi (1) = \ omega, \ ldots, \ psi (\omega )=\omega ^{\omega },\ldots ,\psi (\omega ^{\omega })=\omega ^{\omega ^{\omega }},\ldots \}}$ to do i ${\ Displaystyle \ psi _ {0} (\ Omega) = \ varepsilon _ {0}}$ - najmniejsza liczba epsilon, tj. pierwszy stały punkt ${\ Displaystyle \ alfa = \ omega ^ {\ alfa }}$ .

Jeśli ${\ Displaystyle \ alfa = \ Omega + 1}$${\ Displaystyle C_ {0} (\ alfa) = \ {0,1, \ ldots, \ psi _ {0} (\ Omega) = \ varepsilon _ {0}, \ ldots, \ varepsilon _ {0 } + \ varepsilon _ {0}, \ ldots, \ psi _ {1} (0) = \ Omega, \ ldots \}} i$ do ψ $\ Displaystyle \ psi _{0}(\Omega +1)=\varepsilon _{0}\omega =\omega ^{\varepsilon _{0}+1}}$ .

${\ Displaystyle \ psi _ {0} (\ Omega 2) = \ varepsilon _ {1}}$ drugi numer epsilon,

${\ Displaystyle \ psi _ {0} (\ Omega ^ {2}) = \ varepsilon _ {\ varepsilon _ {\ cdots}} = \ zeta _ {0}} tj$ . pierwszy stały punkt ${\ Displaystyle \ alpha = \ varepsilon _ {\ alfa}}$ ,

${\ Displaystyle \ varphi (\ alfa, \ beta) = \ psi _ {0} (\ Omega ^ {\ alfa} (1 + \ beta) )}$ , gdzie oznacza funkcję Veblena, ${\ Displaystyle \ varphi}$

${\ Displaystyle \ psi _ {0} (\ Omega ^ {\ Omega}) = \ Gamma _ {0} = \ varphi (1 0,0) = \ theta (\ Omega, 0)}$ , gdzie oznacza funkcję Fefermana, ${\ Displaystyle \ theta}$

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

jest

$\ psi _{0}(\Omega ^{\Omega ^{\Omega }})}$ to duża liczba porządkowa Veblena,

$jest$ małą liczbą porządkową Veblena

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

Teraz zbadajmy, jak działa: ${\ displaystyle \ psi _ {1}}$

${\ Displaystyle C_ {1}^{0}(0)=\{\beta \mid \beta <\Omega _{1}\}=\{0,\psi (0)=1,2,\ldots {\text{googol }},\ldots,\psi _{0}(1)=\omega,\ldots,\psi _{0}(\Omega)=\varepsilon _{0},\ldots}$

${\ Displaystyle \ ldots, \ psi _ {0} (\ Omega ^ {\ Omega}) = \ Gamma _ { 0},\ldots ,\psi (\Omega ^{\Omega ^{\Omega }+\Omega ^{2}}),\ldots \}} tj.$ obejmuje wszystkie policzalne liczby porządkowe. A zatem zawiera wszystkie możliwe sumy wszystkich policzalnych liczb porządkowych i $ψ$$1}}$$\ Displaystyle \ psi _ {1} (0) =$ pierwsza niepoliczalna liczba porządkowa, która z definicji jest większa niż wszystkie policzalne liczby porządkowe, tj. najmniejsza liczba z licznością. ${\ displaystyle \ aleph _ {1}$ }

Jeśli ${\ Displaystyle \ alpha = 1}$${\ Displaystyle C_ {1} (\ alfa) = \ {0, \ ldots, \ psi _ {0} (0) = \ omega, \ ldots, \ psi _ {1} (0) = \ omega, \ ldots, \ Omega + \ omega, \ ldots, \ Omega + \ Omega, \ ldots \}}$ do i ${\ Displaystyle \ psi _ {1} (1) = \Omega \omega =\omega ^{\Omega +1}}$ .

${\ Displaystyle \ psi _ {1} (2) = \ Omega \ omega ^ {2} = \ omega ^ {\ Omega + 2}}$

${\ Displaystyle \ psi _ {1} (\ psi _ {1} (0)) = \ psi _ {1} (\ Omega )=\Omega ^{2}=\omega ^{\Omega +\Omega},}$

${\ Displaystyle \ psi _ {1} (\ psi _ {1} (\ psi _ {1} (0))} = \ omega ^ {\ Omega + \ omega ^ {\ Omega + \Omega }}=\omega ^{\Omega \cdot \Omega }=(\omega ^{\Omega })^{\Omega }=\Omega ^{\Omega },}$

${\ Displaystyle \ psi _ {1} ^ {4} (0) = \ Omega ^ {\ Omega ^ {\ Omega}},} ψ$

${\ Displaystyle \ psi _ {1} ^ {k + 1} (0) = \ Omega \ uparrow \ uparrow k}$ gdzie ${\ Displaystyle k}$ jest liczbą naturalną, ${\ Displaystyle k \ geq 2}$ ,

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

Dla przypadku ${\ Displaystyle \ psi (\ psi _ {2} (0)) = \ psi (\ Omega _ {2})}$ zestaw ${\ Displaystyle C_ {0} (\ Omega _ {2})}$ zawiera funkcje $wszystkimi$ argumentami mniejszymi niż ${\ Displaystyle \ Omega _ {2}}$ tj. takie argumenty jak ${\ Displaystyle 0, \ psi _ {1} (0), \ psi _ {1} ( \psi _{1}(0)),\psi_{1}^{3}(0),\ldots,\psi_{1}^{\omega}(0)}$

i wtedy

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

W ogólnym przypadku:

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

Możemy również napisać:

${\ Displaystyle \ teta (\ Omega _ {\ nu}, 0) = \ psi _ {0} (\ Omega _ {\ nu }^{\Omega }){\text{ (dla }}1\równik \nu )<\omega }$

Notacja porządkowa

$_$ zdefiniował notację _ $_$ _ ${$ definiujemy $T$ i $_ \omega +1}$ formalne $z$ indeksowanych , nawiasy klamrowe i przecinki w następujący sposób:

• ${\ Displaystyle 0 \ w T \ ziemia 0 \ w PT}$ ,
• ${\ Displaystyle \ forall (v, a) \ w (\ omega + 1) \ razy T ( D_{v}a\w T\land D_{v}a\w PT)}$ .
• ${\ Displaystyle \ forall (a_ {0}, a_ {1}) \ w PT ^ {2} ((a_ {0} ,a_{1})\w T)}$ .
• ${\ Displaystyle \ istnieje s (a_ {0} = s) \ ziemia (a_ {0}, a_{1})\in T\times PT\rightarrow (s,a_{1})\in T}$ .

Element $nazywany$ jest terminem , a element $głównym$ terminem $T}$ definicji $jest$ zbiorem rekurencyjnym i jest rekurencyjnym podzbiorem $displaystyle$ . Każdy termin jest albo $głównym$ , albo ujętą w nawiasy tablicą głównych wyrazów o długości ${\ displaystyle \ geq 2}$ . Oznaczamy ${\ Displaystyle a \ in PT}$ przez ${\ Displaystyle (a)}$ . Zgodnie z konwencją, każdy termin można jednoznacznie wyrazić jako ${\ displaystyle 0}$ lub nawiasową, niepustą tablicę głównych terminów. Ponieważ klauzule $3 i$$4$ w definicji i $ta$ tylko do tablic o długości konwencja nie powoduje poważnych dwuznaczności

Następnie definiujemy $\ displaystyle a <b}$ binarną na ${\ displaystyle T}$ w następujący sposób: za

• ${\ Displaystyle b = 0 \ strzałka w prawo a <b = \ bot}$
• ${\ Displaystyle a = 0 \ strzałka w prawo (a <b \ strzałka w lewo b \ neq 0)}$
• Jeśli za ${\ Displaystyle a \ neq 0 \ ziemia b \ neq 0}$ to:
  • za $u} a '\ ziemia b = D_ {v} b'}$ dla niektórych ${\ Displaystyle ((u, a '), (v, b')} \ w ((\ omega + 1) \ razy T) ^ {2}$ , to jest prawdziwe ${\ displaystyle a <b}$ jeśli prawdziwe jest jedno z poniższych stwierdzeń: za
    • ${\ displaystyle u <v}$
    • ${\ Displaystyle u = v \ ziemia a'<b'}$
  • za $\ Displaystyle a = (a_ {0}, ..., a_ {n}) \ ziemia$ dla niektórych ${\ Displaystyle (n, m) \ in \ mathbb {N} ^ {2 } \ land 1 \ równoważnik n + m}$ , to ${\ displaystyle a <b}$ prawdziwe, jeśli spełniony jest jeden z następujących warunków: za
    • ${\ Displaystyle \ forall i \ in \ mathbb {N} \ ziemia i \ równoważnik n (n <m \ ziemia a_ {i} = b_ {I})}$
    • ${\ Displaystyle \ istnieje k \ w \ mathbb {N} \ forall i\in \mathbb {N} \land i<k(k\leq min\{n,m\}\land a_{k}<b_{k}\land a_{i}=b_{1})}$

${\ displaystyle <}$ to rekurencyjne ścisłe uporządkowanie całkowite na ${\ displaystyle T}$ . $\ Displaystyle (a <b) \ lor (a = b)}$ ∨ ${\ Displaystyle a \ leq b}$ jako . Chociaż $zostanie$ w sobie nie jest dobrze uporządkowane, jego ograniczenie do podzbioru rekurencyjnego $,$ tworzy dobrze uporządkowane. Aby zdefiniować $displaystyle$ definiujemy podzbiór $OT} sol u za$ każdego $} displaystyle (u,a)\in (\omega +1)\times T}$ w następujący sposób:

• ${\ Displaystyle a = 0 \ rightarrow G_ {u} a = \ varnothing}$
• Załóżmy, że dla pewnego $, za ′$$+1)\razy T}$$v, a')$ , wtedy:
  • ${\ Displaystyle u \ równoważnik v \ strzałka w prawo G_ {u} a = \ {a '\} \ kubek G_ {u} a '}$
  • ${\ Displaystyle u> v \ rightarrow G_ {u} a = \ varnothing}$

• za ${\ Displaystyle a = (a_ {0}, ..., a_ {k})$ niektórych ${ \ Displaystyle (a_ {i}) _ {i = 0} ^ {k} \ w PT ^ {k + 1}}$ dla pewnego ${ \displaystyle k\in \mathbb {N} \backslash \{0\},G_{u}a=\bigcup _{i=0}^{k}G_{u}a_{i}}$ .

${\ Displaystyle b \ in G_ {u} a}$ jest rekurencyjną relacją na ${\ Displaystyle (u, a, b) \ w (\omega +1)\razy T^{2}}$ . Na koniec definiujemy podzbiór w następujący sposób: ${\ Displaystyle OT \ podzbiór T}$

• ${\ Displaystyle 0 \ w ST}$
• dla każdego ${\ Displaystyle (v, a) \ in (\ omega + 1) \ razy T}$ , ${\ Displaystyle D_ {v} a \w OT}$ jest równoważne z za $\ Displaystyle a \ w OT}$ i dla każdego $G_ {v} a}$${\ displaystyle a'<a}$ , .
• dla dowolnego $\ Displaystyle (a_ {i}) _ {i = 0} ^ {k} \ w PT ^ {k + 1}}$$OT}$ , jest równoważne ${\ Displaystyle (a_ {i })_{i=0}^{k}\w OT}$ i ${\ Displaystyle a_ {k} \ równoważnik ... \ równoważnik a_ {0}}$ .

$displaystyle OT}$$\$$porządkowym$ podzbiorem , a element jest terminem . $_$ możemy _ podążać drogą:

• ${\ Displaystyle a = 0 \ strzałka w prawo o (a) = 0}$
• Jeśli $\ Displaystyle a = D_ {v} a'}$ dla jakiegoś ${\ Displaystyle (v, a') \ w (\ omega +1) \ razy OT}$ , wtedy ${\ Displaystyle o (a) = \ psi _ {v} (o (a '))}$ .
• za ${\ Displaystyle a = (a_ {0}, ..., a_ {k})$${\ Displaystyle (a_ {i}) _ {i = 0} ^ {k} \ in (OT \ cap PT) ^ {k + 1}} z k ∈ N$ pewnego ∖ $\ w \mathbb {N} \backslash \{0\}}$ , wtedy ${\ Displaystyle o (a) = o (a_ {0}) \ #... \ # o (a_ {k})}$ , gdzie ${\ Displaystyle \ #}$ oznacza malejącą sumę liczby porządkowe, co pokrywa się ze zwykłym dodawaniem zgodnie z definicją . ${\ displaystyle OT}$ .

Buchholz zweryfikował następujące właściwości: ${\ displaystyle o}$ :

• Mapa $jest$ zachowującą porządek mapą bijektywną w odniesieniu do i ${ \$$}$ . W szczególności $displaystyle$ ścisłe uporządkowanie na $OT}$ .
• Dla każdego $\ displaystyle$ za $<D_ {1} 0}$ , ${\ displaystyle o (a)}$ z typem porządkowym ${\ Displaystyle <}$ ograniczone do policzalnego podzbioru ${\ Displaystyle \ {x \ w ST \; | \; x <a \}}$ .
• $ograniczonym$ Takeuti -Fefermana-Buchholza pokrywa się z typem porządkowym do podzbioru rekurencyjnego ${\ Displaystyle \ {x \ w OT \;|\; x <D_ {1}0 \}}$ .
• Typ porządkowy $-$ większy niż - .
• Dla $,$ zasadność $_$ _ ${\ Displaystyle \ {x \ w OT \;|\; x <D_ {0} D_ {v + 1} 0 \}}$ w sensie nieistnienia prymitywnej rekurencyjnej nieskończonej sekwencji malejącej nie da się udowodnić pod ${\ displaystyle {\ mathsf {ID}} _ {v}}$ .
• Zasadność ograniczona ${\ Displaystyle \ {x \ w OT \;|\; x <D_ {0} D _ {\ omega} 0 \}} w tym samym sensie,$ podzbioru $rekurencyjnego$ jak powyżej, nie można udowodnić pod ${\ Displaystyle \ Pi _ {1} ^ {1} -CA_ {0}}$ .

Normalna forma

Postać normalną funkcji Buchholza można zdefiniować przez wycofanie postaci standardowej dla związanej z nią notacji porządkowej przez ${\ displaystyle o}$ . $.$$_$ zbiór na _ w następujący sposób:

• Predykat na liczbie porządkowej ${\ Displaystyle \ alfa = _ {NF} 0}$ na liczbie porządkowej $+ 1}}}$${\ Displaystyle \ alpha \ in C_ {0} (\ varepsilon _ {\ Omega _ {\ omega$$\ displaystyle$ zdefiniowany jako do $\ alpha = 0}$ .

• Predykat na liczbach porządkowych ${\ Displaystyle \ alfa _ {0} = _ {NF} \ psi _ {k_ {1}} (\ alfa _$$_$ _ ${\ Displaystyle k_ {1} = \ omega + 1}$ zdefiniowane jako ${\ Displaystyle \ alpha _ {0} = \ psi _ {k_ {1}} ( \ alfa _ {1})}$ i ${\ Displaystyle \ alfa _ {1} = C_ {k_ {1}} (\ alfa _ {1})}$ należy do ${ \displaystyle NF}$ .
• Predykat ${\ Displaystyle \ alfa _ {0} = _ {NF} \ alfa _ {1} +... + \ alfa _ {n}}$ na liczbach porządkowych ${\ Displaystyle \ alfa _ {0}, \ alfa _ {1}, ..., \ alfa _ {n} \ w C_ {0} (\ varepsilon _$ z liczbą całkowitą ${\ Displaystyle n> 1}$ zdefiniowaną jako ${\ Displaystyle \ alfa _ {0} = \ alfa _ {1} + ... + \ alfa _ {n}$ } ${\ Displaystyle \ alfa _ {1} \ geq ... \ geq \ alfa _ {n}}$ i $fa$$displaystyle NF}$ do . Tutaj $liczb$$raczej$ symbolem funkcji niż faktycznym dodatkiem, a oznacza głównych.

Przydatne jest również zastąpienie trzeciego przypadku następującym otrzymanym przez połączenie drugiego warunku:

• Predykat ${\ Displaystyle \ alfa _ {0} = _ {NF} \ psi _ {k_ {1}} (\ alfa _ {1}) + ... + \ psi _ {k_ { n}}(\alpha _{n})}$ na liczbach porządkowych ${\ Displaystyle \ alfa _ {0}, \ alfa _ {1}, ..., \ alfa _ {n} \ w C_ {0} (\ varepsilon _$ z liczbą całkowitą ${\ Displaystyle n> 1}$ i $k_ {n} \ w \ omega + 1}$${\ Displaystyle \ alfa _ {0} = \ psi _ {k_ {1}} (\ alfa _ {1}) + ... + \ psi _ {k_ {n}} ( \alpha _{n})}$ zdefiniowane jako , ${\ Displaystyle \ psi _ {k_ {1}} (\ alfa _ {1}) \ geq ... \ geq \ psi _ {k_ {n}} (\ alfa _ {n })}$ , i ${\ Displaystyle \ alfa _ {1} \ w C_ {k_ {1}} (\ alfa _ {1}), ..., \ alfa _ {$ należy do ${\ displaystyle NF}$ .

Zauważmy, że te dwa sformułowania nie są równoważne. Na przykład ${\ Displaystyle \ psi _ {0} (\ Omega) + 1 = _ {NF} \ psi _ {0} (\ zeta _ {1}) + \ psi _ {0} (0)}$ jest prawidłową formułą, która jest fałszywa w odniesieniu do drugiego sformułowania, ponieważ ${\ Displaystyle \ zeta _ {1} \ neq C_ {0} (\ zeta _ {1})}$ , podczas gdy jest to poprawna formuła, która jest prawdziwa w odniesieniu do pierwszego sformułowania, ponieważ ${\ Displaystyle \psi _{0}(\Omega)+1=\psi _{0}(\zeta _{1})+\psi _{0}(0)}$ , ${\ Displaystyle \ psi _ {0} (\ zeta _ {1}), \ psi _ {0} (0) \ w AP}$ i ${\ Displaystyle \ psi _ { 0}(\zeta _{1})\geq \psi _{0}(0)}$ . W ten sposób pojęcie postaci normalnej w dużym stopniu zależy od kontekstu. W obu sformułowaniach każda liczba porządkowa w $może$ postaci normalnej