Funciones psi de Buchholz

Las funciones psi de Buchholz son una jerarquía de funciones ordinales de un solo argumento introducidas por el matemático alemán Wilfried Buchholz en 1986. Estas funciones son una versión simplificada de las funciones , pero sin embargo tienen la misma fuerza ^{[ aclaración necesaria ]} que aquellas. Más tarde, este enfoque fue ampliado por Jäger ^[1] y Schütte ^[2] . ${\displaystyle \psi _{\nu }(\alpha )}$ ${\displaystyle \theta }$

Definición

Buchholz definió sus funciones de la siguiente manera: Defina:

• Ω _ξ = ω _ξ si ξ > 0, Ω ₀ = 1

Las funciones ψ _v (α) para α un ordinal, v un ordinal como máximo ω, se definen por inducción en α de la siguiente manera:

• ψ _v (α) es el ordinal más pequeño que no está en C _v (α)

donde C _v (α) es el conjunto más pequeño tal que

• C _v (α) contiene todos los ordinales menores que Ω _v
• C _v (α) está cerrado bajo adición ordinal
• C _v (α) es cerrado bajo las funciones ψ _u (para u ≤ω) aplicadas a argumentos menores que α.

El límite de esta notación es el ordinal Takeuti–Feferman–Buchholz .

Propiedades

Sea la clase de ordinales principales aditivos . Buchholz demostró las siguientes propiedades de estas funciones: ${\displaystyle P}$

• ${\displaystyle \psi _{\nu }(0)=\Omega _{\nu },}$ ^{[3] : 197}
• ${\displaystyle \psi _{\nu }(\alpha )\in P,}$ ^{[3] : 197}
• ${\displaystyle \psi _{\nu }(\alpha +1)=\min\{\gamma \in P:\psi _{\nu }(\alpha )<\gamma \}{\text{ if }}\alpha \in C_{\nu }(\alpha ),}$ ^{[3] : 199}
• ${\displaystyle \Omega _{\nu }\leq \psi _{\nu }(\alpha )<\Omega _{\nu +1}}$ ^{[3] : 197}
• ${\displaystyle \psi _{0}(\alpha )=\omega ^{\alpha }{\text{ if }}\alpha <\varepsilon _{0},}$ ^{[3] : 199}
• ${\displaystyle \psi _{\nu }(\alpha )=\omega ^{\Omega _{\nu }+\alpha }{\text{ if }}\alpha <\varepsilon _{\Omega _{\nu }+1}{\text{ and }}\nu \neq 0,}$ ^{[3] : 199}
• ${\displaystyle \theta (\varepsilon _{\Omega _{\nu }+1},0)=\psi (\varepsilon _{\Omega _{\nu }+1}){\text{ for }}0<\nu \leq \omega .}$ ^{[3] : 206}

Sucesiones fundamentales y forma normal de la función de Buchholz

Forma normal

La forma normal para 0 es 0. Si es un número ordinal distinto de cero , entonces la forma normal para es donde y y cada uno también se escribe en forma normal. ${\displaystyle \alpha }$ ${\displaystyle \alpha <\Omega _{\omega }}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha =\psi _{\nu _{1}}(\beta _{1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\psi _{\nu _{k}}(\beta _{k})}$ ${\displaystyle \nu _{i}\in \mathbb {N} _{0},k\in \mathbb {N} _{>0},\beta _{i}\in C_{\nu _{i}}(\beta _{i})}$ ${\displaystyle \psi _{\nu _{1}}(\beta _{1})\geq \psi _{\nu _{2}}(\beta _{2})\geq \cdots \geq \psi _{\nu _{k}}(\beta _{k})}$ ${\displaystyle \beta _{i}}$

Secuencias fundamentales

La sucesión fundamental de un número ordinal con cofinalidad es una sucesión estrictamente creciente con longitud y con límite , donde es el -ésimo elemento de esta sucesión. Si es un ordinal sucesor entonces y la sucesión fundamental tiene solo un elemento . Si es un ordinal límite entonces . ${\displaystyle \alpha }$ ${\displaystyle \operatorname {cof} (\alpha )=\beta }$ ${\displaystyle (\alpha [\eta ])_{\eta <\beta }}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha [\eta ]}$ ${\displaystyle \eta }$ ${\displaystyle \alpha }$ ${\displaystyle \operatorname {cof} (\alpha )=1}$ ${\displaystyle \alpha [0]=\alpha -1}$ ${\displaystyle \alpha }$ ${\displaystyle \operatorname {cof} (\alpha )\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu \geq 0\}}$

Para los ordinales distintos de cero , escritos en forma normal, las secuencias fundamentales se definen de la siguiente manera: ${\displaystyle \alpha <\Omega _{\omega }}$

1. Si donde entonces y ${\displaystyle \alpha =\psi _{\nu _{1}}(\beta _{1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\psi _{\nu _{k}}(\beta _{k})}$ ${\displaystyle k\geq 2}$ ${\displaystyle \operatorname {cof} (\alpha )=\operatorname {cof} (\psi _{\nu _{k}}(\beta _{k}))}$ ${\displaystyle \alpha [\eta ]=\psi _{\nu _{1}}(\beta _{1})+\cdots +\psi _{\nu _{k-1}}(\beta _{k-1})+(\psi _{\nu _{k}}(\beta _{k})[\eta ]),}$
2. Si , entonces y , ${\displaystyle \alpha =\psi _{0}(0)=1}$ ${\displaystyle \operatorname {cof} (\alpha )=1}$ ${\displaystyle \alpha [0]=0}$
3. Si , entonces y , ${\displaystyle \alpha =\psi _{\nu +1}(0)}$ ${\displaystyle \operatorname {cof} (\alpha )=\Omega _{\nu +1}}$ ${\displaystyle \alpha [\eta ]=\Omega _{\nu +1}[\eta ]=\eta }$
4. Si entonces y (y nota: ), ${\displaystyle \alpha =\psi _{\nu }(\beta +1)}$ ${\displaystyle \operatorname {cof} (\alpha )=\omega }$ ${\displaystyle \alpha [\eta ]=\psi _{\nu }(\beta )\cdot \eta }$ ${\displaystyle \psi _{\nu }(0)=\Omega _{\nu }}$
5. Si y entonces y , ${\displaystyle \alpha =\psi _{\nu }(\beta )}$ ${\displaystyle \operatorname {cof} (\beta )\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu <\nu \}}$ ${\displaystyle \operatorname {cof} (\alpha )=\operatorname {cof} (\beta )}$ ${\displaystyle \alpha [\eta ]=\psi _{\nu }(\beta [\eta ])}$
6. Si y entonces y donde . ${\displaystyle \alpha =\psi _{\nu }(\beta )}$ ${\displaystyle \operatorname {cof} (\beta )\in \{\Omega _{\mu +1}\mid \mu \geq \nu \}}$ ${\displaystyle \operatorname {cof} (\alpha )=\omega }$ ${\displaystyle \alpha [\eta ]=\psi _{\nu }(\beta [\gamma [\eta ]])}$ ${\displaystyle \left\{{\begin{array}{lcr}\gamma [0]=\Omega _{\mu }\\\gamma [\eta +1]=\psi _{\mu }(\beta [\gamma [\eta ]])\\\end{array}}\right.}$

Explicación

Buchholz trabaja en la teoría de conjuntos de Zermelo-Fraenkel, lo que significa que cada ordinal es igual al conjunto . Entonces, la condición significa que el conjunto incluye todos los ordinales menores que, en otras palabras , . ${\displaystyle \alpha }$ ${\displaystyle \{\beta \mid \beta <\alpha \}}$ ${\displaystyle C_{\nu }^{0}(\alpha )=\Omega _{\nu }}$ ${\displaystyle C_{\nu }^{0}(\alpha )}$ ${\displaystyle \Omega _{\nu }}$ ${\displaystyle C_{\nu }^{0}(\alpha )=\{\beta \mid \beta <\Omega _{\nu }\}}$

La condición significa que el conjunto incluye: ${\displaystyle 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 \}}$ ${\displaystyle C_{\nu }^{n+1}(\alpha )}$

• todos los ordinales del conjunto anterior , ${\displaystyle C_{\nu }^{n}(\alpha )}$
• todos los ordinales que se pueden obtener sumando de forma aditiva los ordinales principales del conjunto anterior , ${\displaystyle C_{\nu }^{n}(\alpha )}$
• todos los ordinales que se pueden obtener aplicando ordinales menores que del conjunto anterior como argumentos de funciones , donde . ${\displaystyle \alpha }$ ${\displaystyle C_{\nu }^{n}(\alpha )}$ ${\displaystyle \psi _{\mu }}$ ${\displaystyle \mu \leq \omega }$

Por eso podemos reescribir esta condición como:

${\displaystyle 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 \}.}$

Así, la unión de todos los conjuntos con ie denota el conjunto de todos los ordinales que pueden generarse a partir de ordinales mediante las funciones + (suma) y , donde y . ${\displaystyle C_{\nu }^{n}(\alpha )}$ ${\displaystyle n<\omega }$ ${\displaystyle C_{\nu }(\alpha )=\bigcup _{n<\omega }C_{\nu }^{n}(\alpha )}$ ${\displaystyle <\aleph _{\nu }}$ ${\displaystyle \psi _{\mu }(\eta )}$ ${\displaystyle \mu \leq \omega }$ ${\displaystyle \eta <\alpha }$

Entonces es el ordinal más pequeño que no pertenece a este conjunto. ${\displaystyle \psi _{\nu }(\alpha )=\min\{\gamma \mid \gamma \not \in C_{\nu }(\alpha )\}}$

Ejemplos

Consideremos los siguientes ejemplos:

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

${\displaystyle C_{0}(0)=\{0\}}$(ya que no hay funciones y 0 + 0 = 0). ${\displaystyle \psi (\eta <0)}$

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

${\displaystyle C_{0}(1)}$incluye y todas las sumas posibles de números naturales y por lo tanto – primer ordinal transfinito, que es mayor que todos los números naturales por su definición. ${\displaystyle \psi _{0}(0)=1}$ ${\displaystyle \psi _{0}(1)=\omega }$

${\displaystyle C_{0}(2)}$incluye y todas las sumas posibles de ellos y por lo tanto . ${\displaystyle \psi _{0}(0)=1,\psi _{0}(1)=\omega }$ ${\displaystyle \psi _{0}(2)=\omega ^{2}}$

Si entonces y . ${\displaystyle \alpha =\omega }$ ${\displaystyle 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 }}$

Si entonces y – el número épsilon más pequeño, es decir, el primer punto fijo de . ${\displaystyle \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 }}$

Si entonces y . ${\displaystyle \alpha =\Omega +1}$ ${\displaystyle 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}}$el segundo número épsilon,

${\displaystyle \psi _{0}(\Omega ^{2})=\varepsilon _{\varepsilon _{\cdots }}=\zeta _{0}}$es decir primer punto fijo de , ${\displaystyle \alpha =\varepsilon _{\alpha }}$

${\displaystyle \varphi (\alpha ,\beta )=\psi _{0}(\Omega ^{\alpha }(1+\beta ))}$, donde denota la función de Veblen , ${\displaystyle \varphi }$

${\displaystyle \psi _{0}(\Omega ^{\Omega })=\Gamma _{0}=\varphi (1,0,0)=\theta (\Omega ,0)}$, donde denota la función de Feferman y es el ordinal de Feferman-Schütte , ${\displaystyle \theta }$ ${\displaystyle \Gamma _{0}}$

${\displaystyle \psi _{0}(\Omega ^{\Omega ^{2}})=\varphi (1,0,0,0)}$es el ordinal de Ackermann ,

${\displaystyle \psi _{0}(\Omega ^{\Omega ^{\omega }})}$es el ordinal pequeño de Veblen ,

${\displaystyle \psi _{0}(\Omega ^{\Omega ^{\Omega }})}$es el ordinal grande de Veblen ,

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

Ahora investiguemos cómo funciona: ${\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 \}}$es decir, incluye todos los ordinales contables y, por lo tanto, incluye todas las sumas posibles de todos los ordinales contables y el primer ordinal incontable que sea mayor que todos los ordinales contables por su definición, es decir, el número más pequeño con cardinalidad . ${\displaystyle C_{1}(0)}$ ${\displaystyle \psi _{1}(0)=\Omega _{1}}$ ${\displaystyle \aleph _{1}}$

Si entonces y . ${\displaystyle \alpha =1}$ ${\displaystyle 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}}$

${\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}$donde es un número natural, , ${\displaystyle k}$ ${\displaystyle k\geq 2}$

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

Para el caso en que el conjunto incluya funciones con todos los argumentos menores que ie, argumentos tales como ${\displaystyle \psi (\psi _{2}(0))=\psi (\Omega _{2})}$ ${\displaystyle C_{0}(\Omega _{2})}$ ${\displaystyle \psi _{0}}$ ${\displaystyle \Omega _{2}}$ ${\displaystyle 0,\psi _{1}(0),\psi _{1}(\psi _{1}(0)),\psi _{1}^{3}(0),\ldots ,\psi _{1}^{\omega }(0)}$

y luego

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

En el caso general:

${\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).}$

También podemos escribir:

${\displaystyle \theta (\Omega _{\nu },0)=\psi _{0}(\Omega _{\nu }^{\Omega }){\text{ (for }}1\leq \nu )<\omega }$

Notación ordinal

Buchholz ^[3] definió una notación ordinal asociada a la función. Definimos simultáneamente los conjuntos y como cadenas formales que consisten en indexados por , llaves y comas de la siguiente manera: ${\displaystyle {\mathsf {(OT,<)}}}$ ${\displaystyle \psi }$ ${\displaystyle T}$ ${\displaystyle PT}$ ${\displaystyle 0,D_{v}}$ ${\displaystyle v\in \omega +1}$

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

Un elemento de se llama término , y un elemento de se llama término principal . Por definición, es un conjunto recursivo y es un subconjunto recursivo de . Cada término es , un término principal o una matriz entre corchetes de términos principales de longitud . Denotamos por . Por convención, cada término se puede expresar de forma única como o una matriz entre corchetes, no vacía, de términos principales. Dado que las cláusulas 3 y 4 en la definición de y son aplicables solo a matrices de longitud , esta convención no causa una ambigüedad grave. ${\displaystyle T}$ ${\displaystyle PT}$ ${\displaystyle T}$ ${\displaystyle PT}$ ${\displaystyle T}$ ${\displaystyle 0}$ ${\displaystyle \geq 2}$ ${\displaystyle a\in PT}$ ${\displaystyle (a)}$ ${\displaystyle 0}$ ${\displaystyle T}$ ${\displaystyle PT}$ ${\displaystyle \geq 2}$

Definimos entonces una relación binaria de la siguiente manera: ${\displaystyle a<b}$ ${\displaystyle T}$

• ${\displaystyle b=0\rightarrow a<b=\bot }$
• ${\displaystyle a=0\rightarrow (a<b\leftrightarrow b\neq 0)}$
• Si , entonces: ${\displaystyle a\neq 0\land b\neq 0}$
  • Si para algunos , entonces es verdadero si se cumple alguna de las siguientes condiciones: ${\displaystyle a=D_{u}a'\land b=D_{v}b'}$ ${\displaystyle ((u,a'),(v,b'))\in ((\omega +1)\times T)^{2}}$ ${\displaystyle a<b}$
    • ${\displaystyle u<v}$
    • ${\displaystyle u=v\land a'<b'}$
  • Si para algunos , entonces es verdadero si se cumple alguna de las siguientes condiciones: ${\displaystyle a=(a_{0},...,a_{n})\land b=(b_{0},...,b_{m})}$ ${\displaystyle (n,m)\in \mathbb {N} ^{2}\land 1\leq n+m}$ ${\displaystyle a<b}$
    • ${\displaystyle \forall i\in \mathbb {N} \land i\leq n(n<m\land a_{i}=b_{i})}$
    • ${\displaystyle \exists k\in \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 <}$es un ordenamiento total estricto recursivo en . Lo abreviamos como . Aunque en sí mismo no es un buen ordenamiento, su restricción a un subconjunto recursivo , que se describirá más adelante, forma un buen ordenamiento. Para definir , definimos un subconjunto para cada uno de la siguiente manera: ${\displaystyle T}$ ${\displaystyle (a<b)\lor (a=b)}$ ${\displaystyle a\leq b}$ ${\displaystyle \leq }$ ${\displaystyle OT\subset T}$ ${\displaystyle OT}$ ${\displaystyle G_{u}a\subset T}$ ${\displaystyle (u,a)\in (\omega +1)\times T}$

• ${\displaystyle a=0\rightarrow G_{u}a=\varnothing }$
• Supongamos que para algunos , entonces: ${\displaystyle a=D_{v}a'}$ ${\displaystyle (v,a')\in (\omega +1)\times T}$
  • ${\displaystyle u\leq v\rightarrow G_{u}a=\{a'\}\cup G_{u}a'}$
  • ${\displaystyle u>v\rightarrow G_{u}a=\varnothing }$

• Si para algunos para algunos . ${\displaystyle a=(a_{0},...,a_{k})}$ ${\displaystyle (a_{i})_{i=0}^{k}\in PT^{k+1}}$ ${\displaystyle k\in \mathbb {N} \backslash \{0\},G_{u}a=\bigcup _{i=0}^{k}G_{u}a_{i}}$

${\displaystyle b\in G_{u}a}$es una relación recursiva sobre . Finalmente, definimos un subconjunto de la siguiente manera: ${\displaystyle (u,a,b)\in (\omega +1)\times T^{2}}$ ${\displaystyle OT\subset T}$

• ${\displaystyle 0\in OT}$
• Para cualquier , es equivalente a y, para cualquier , . ${\displaystyle (v,a)\in (\omega +1)\times T}$ ${\displaystyle D_{v}a\in OT}$ ${\displaystyle a\in OT}$ ${\displaystyle a'\in G_{v}a}$ ${\displaystyle a'<a}$
• Para cualquier , es equivalente a y . ${\displaystyle (a_{i})_{i=0}^{k}\in PT^{k+1}}$ ${\displaystyle (a_{0},...,a_{k})\in OT}$ ${\displaystyle (a_{i})_{i=0}^{k}\in OT}$ ${\displaystyle a_{k}\leq ...\leq a_{0}}$

${\displaystyle OT}$es un subconjunto recursivo de , y un elemento de se denomina término ordinal . Podemos definir entonces una función de la siguiente manera: ${\displaystyle T}$ ${\displaystyle OT}$ ${\displaystyle o:OT\rightarrow C_{0}(\varepsilon _{\Omega _{\omega }+1})}$

• ${\displaystyle a=0\rightarrow o(a)=0}$
• Si para algunos , entonces . ${\displaystyle a=D_{v}a'}$ ${\displaystyle (v,a')\in (\omega +1)\times OT}$ ${\displaystyle o(a)=\psi _{v}(o(a'))}$
• Si para algunos con , entonces , donde denota la suma descendente de ordinales, lo cual coincide con la adición usual por la definición de . ${\displaystyle a=(a_{0},...,a_{k})}$ ${\displaystyle (a_{i})_{i=0}^{k}\in (OT\cap PT)^{k+1}}$ ${\displaystyle k\in \mathbb {N} \backslash \{0\}}$ ${\displaystyle o(a)=o(a_{0})\#...\#o(a_{k})}$ ${\displaystyle \#}$ ${\displaystyle OT}$

Buchholz verificó las siguientes propiedades de : ${\displaystyle o}$

• El mapa es un mapa biyectivo que preserva el orden con respecto a y . En particular, es un buen ordenamiento estricto recursivo en . ${\displaystyle o}$ ${\displaystyle <}$ ${\displaystyle \in }$ ${\displaystyle o}$ ${\displaystyle OT}$
• Para cualquier satisfacción , coincide con el tipo ordinal de restringido al subconjunto contable . ${\displaystyle a\in OT}$ ${\displaystyle a<D_{1}0}$ ${\displaystyle o(a)}$ ${\displaystyle <}$ ${\displaystyle \{x\in OT\;|\;x<a\}}$
• El ordinal Takeuti-Feferman-Buchholz coincide con el tipo ordinal de restringido al subconjunto recursivo . ${\displaystyle <}$ ${\displaystyle \{x\in OT\;|\;x<D_{1}0\}}$
• El tipo ordinal de es mayor que el ordinal de Takeuti-Feferman-Buchholz . ${\displaystyle (OT,<)}$
• Para cualquier , el fundamento de la restricción al subconjunto recursivo en el sentido de la no existencia de una secuencia descendente infinita recursiva primitiva no es demostrable bajo . ${\displaystyle v\in \mathbb {N} \;\backslash \;\{0\}}$ ${\displaystyle <}$ ${\displaystyle \{x\in OT\;|\;x<D_{0}D_{v+1}0\}}$ ${\displaystyle {\mathsf {ID}}_{v}}$
• El fundamento de la restricción al subconjunto recursivo en el mismo sentido que el anterior no se puede demostrar bajo . ${\displaystyle <}$ ${\displaystyle \{x\in OT\;|\;x<D_{0}D_{\omega }0\}}$ ${\displaystyle \Pi _{1}^{1}-CA_{0}}$

Forma normal

La forma normal de la función de Buchholz se puede definir mediante la retirada de la forma estándar de la notación ordinal asociada a ella por . Es decir, el conjunto de predicados sobre ordinales en se define de la siguiente manera: ${\displaystyle o}$ ${\displaystyle NF}$ ${\displaystyle C_{0}(\varepsilon _{\Omega _{\omega }+1})}$

• El predicado de un ordinal definido como pertenece a . ${\displaystyle \alpha =_{NF}0}$ ${\displaystyle \alpha \in C_{0}(\varepsilon _{\Omega _{\omega }+1})}$ ${\displaystyle \alpha =0}$ ${\displaystyle NF}$

• El predicado  de los ordinales  con  definido como  y  pertenece a . ${\displaystyle \alpha _{0}=_{NF}\psi _{k_{1}}(\alpha _{1})}$ ${\displaystyle \alpha _{0},\alpha _{1}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})}$ ${\displaystyle k_{1}=\omega +1}$ ${\displaystyle \alpha _{0}=\psi _{k_{1}}(\alpha _{1})}$ ${\displaystyle \alpha _{1}=C_{k_{1}}(\alpha _{1})}$ ${\displaystyle NF}$
• El predicado de los ordinales  con un entero  definido como , , y  pertenece a . Aquí  se trata de un símbolo de función en lugar de una suma real y  denota la clase de números principales aditivos. ${\displaystyle \alpha _{0}=_{NF}\alpha _{1}+...+\alpha _{n}}$ ${\displaystyle \alpha _{0},\alpha _{1},...,\alpha _{n}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})}$ ${\displaystyle n>1}$ ${\displaystyle \alpha _{0}=\alpha _{1}+...+\alpha _{n}}$ ${\displaystyle \alpha _{1}\geq ...\geq \alpha _{n}}$ ${\displaystyle \alpha _{1},...,\alpha _{n}\in AP}$ ${\displaystyle NF}$ ${\displaystyle +}$ ${\displaystyle AP}$

También es útil sustituir el tercer caso por el siguiente, obtenido combinando la segunda condición:

• El predicado de los ordinales  con un entero  y definido como , , y  pertenece a . ${\displaystyle \alpha _{0}=_{NF}\psi _{k_{1}}(\alpha _{1})+...+\psi _{k_{n}}(\alpha _{n})}$ ${\displaystyle \alpha _{0},\alpha _{1},...,\alpha _{n}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})}$ ${\displaystyle n>1}$ ${\displaystyle k_{1},...,k_{n}\in \omega +1}$ ${\displaystyle \alpha _{0}=\psi _{k_{1}}(\alpha _{1})+...+\psi _{k_{n}}(\alpha _{n})}$ ${\displaystyle \psi _{k_{1}}(\alpha _{1})\geq ...\geq \psi _{k_{n}}(\alpha _{n})}$ ${\displaystyle \alpha _{1}\in C_{k_{1}}(\alpha _{1}),...,\alpha _{n}\in C_{k_{n}}(\alpha _{n})\in AP}$ ${\displaystyle NF}$

Observamos que esas dos formulaciones no son equivalentes. Por ejemplo,  es una fórmula válida que es falsa con respecto a la segunda formulación debido a , mientras que es una fórmula válida que es verdadera con respecto a la primera formulación debido a , , y . De esta manera, la noción de forma normal depende en gran medida del contexto. En ambas formulaciones, cada ordinal en  puede expresarse de forma única en forma normal para la función de Buchholz. ${\displaystyle \psi _{0}(\Omega )+1=_{NF}\psi _{0}(\zeta _{1})+\psi _{0}(0)}$ ${\displaystyle \zeta _{1}\neq C_{0}(\zeta _{1})}$ ${\displaystyle \psi _{0}(\Omega )+1=\psi _{0}(\zeta _{1})+\psi _{0}(0)}$ ${\displaystyle \psi _{0}(\zeta _{1}),\psi _{0}(0)\in AP}$ ${\displaystyle \psi _{0}(\zeta _{1})\geq \psi _{0}(0)}$ ${\displaystyle C_{0}(\varepsilon _{\Omega _{\omega }+1})}$

Referencias

1. Jäger, G (1984). "Ordinales ρ-inaccesibles, funciones colapsantes y un sistema de notación recursivo". Archiv für Mathematische Logik und Grundlagenforschung . 24 (1): 49–62. doi :10.1007/BF02007140. S2CID  38619369.
2. Buchholz, W.; Schütte, K. (1983). "Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der H~-Separation und Bar-Induktion". Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. Clase .
3. Buchholz, W. (1986). "Un nuevo sistema de funciones ordinales demostrativas". Anales de lógica pura y aplicada . 32 : 195–207. doi : 10.1016/0168-0072(86)90052-7 .