Funciones psi de Buchholz

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 16 de enero de 2020; la verificación requiere 1 edición .

Las funciones psi de Buchholz son una jerarquía de funciones ordinales colapsadas introducidas por el matemático alemán Wilfried Buchholz en 1986. [1] Estas funciones son una versión simplificada de las funciones de Feferman , pero aún tienen el mismo poder. Posteriormente este enfoque fue ampliado por los matemáticos alemanes G. Jäger [2] y K. Schütte [3] . ${\ estilo de visualización \ psi _ {\ nu} (\ alfa)}$ $\ theta$

Definición

Buchholz definió sus funciones de la siguiente manera:

{\begin{alineado}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 )\cuña \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{alineado}}

dónde

\omega

es el ordinal transfinito más pequeño

\Omega _{\nu }={\begin{cases}1{\text{ if }}\nu =0\\{\text{número cardinal}}\aleph _{\nu }{\text { si }}\nu >0\end{casos}}

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

es el conjunto de números principales aditivos en la forma tal que y y , donde es la clase de todos los ordinales.

{\ Displaystyle \ omega ^ {\ xi}}

{\ estilo de visualización \ gamma = \ gamma _ {1} + \ cdots + \ gamma _ {k}}

{\ estilo de visualización \ gamma _ {1} \ geq \ cdots \ geq \ gamma _ {k}}

\gamma _{1},\ldots,\gamma _{k}\in P=\{\omega ^{\xi }|\xi \in \operatorname {On} \}=\{\alpha \ en \operatorname {On} |0<\alpha \wedge \forall \xi ,\eta <\alpha (\xi +\eta <\alpha )\}

{\ estilo de visualización activado}

Nota: las letras griegas significan ordinales en todas partes .

El límite de esta notación es el ordinal Takeuchi-Feferman-Buchholz . ${\ estilo de visualización \ psi _ {0} (\ varepsilon _ {\ omega _ {\ omega} + 1})}$

Propiedades

Buchholz mostró las siguientes propiedades de estas funciones:

${\ estilo de visualización \ psi _ {\ nu} (0) = \ Omega _ {\ nu},}$ En particular, ${\ estilo de visualización \ psi _ {0} (0) = 1,}$
${\ estilo de visualización \ psi _ {\ nu} (\ alfa) \ en P,}$
$\psi _{\nu }(\alpha +1)={\begin{casos}\min\{\gamma \in P:\psi _{\nu }(\alpha )<\gamma \}{ \text{ si }}\alpha \in C_{\nu }(\alpha )\\\psi _{\nu }(\alpha ){\text{ if }}\alpha \notin C_{\nu }(\ alfa )\end{casos}},$
${\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{ y }}\nu \neq 0,$
$\theta (\varepsilon _{\Omega _{\nu }+1},0)=\psi _{0}(\varepsilon _{\Omega _{\nu }+1}){\text{ para }}0<\nu \leq \omega .$

Secuencias fundamentales y la forma normal de las funciones de Buchholz

Forma normal

La forma normal de cero es 0. Si es un ordinal distinto de cero, entonces la forma normal de es , donde y , donde cada ordinal también se escribe en forma normal. $\alfa$ $\alfa$ $\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})$ ${\ estilo de visualización \ psi _ {\ nu _ {1}} (\ beta _ {1}) \ geq \ psi _ {\ nu _ {2}} (\ beta _ {2}) \ geq \ cdots \ geq \ psi _ {\ nu _ {k}} (\ beta _ {k})}$ ${\ estilo de visualización \ beta _ {i}}$

Secuencias fundamentales

La sucesión fundamental para un ordinal límite con cofinalidad es una sucesión transfinita estrictamente creciente de longitud y límite , donde es el elemento th de esta sucesión, es decir, . $\alfa$ ${\ estilo de visualización \ nombre del operador {cof} (\ alfa) = \ beta}$ ${\ estilo de visualización (\ alfa [\ eta]) _ {\ eta <\ beta))$ $\beta$ $\alfa$ ${\ estilo de visualización \ alfa [\ eta]}$ $\eta$ ${\displaystyle \alpha =\sup\{\alpha [\eta ]|\eta <\operatorname {cof} (\alpha )\))$

Para ordinales límite , escritos en forma normal, las sucesiones fundamentales se definen de la siguiente manera: $\alfa$

Si , donde , entonces y , $\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}))$ ${\ estilo de visualización \ alfa [\ eta] = \ psi _ {\ nu _ {1)} (\ beta _ {1}) + \ cdots + \ psi _ {\ nu _ {k-1)} (\ beta _ {k-1})+(\psi _{\nu _{k))(\beta _{k})[\eta ])}$
Si , entonces y , ${\ estilo de visualización \ alfa = \ psi _ {\ omega} (0)}$ ${\ estilo de visualización \ nombre del operador {cof} (\ alfa) = \ omega}$ ${\ estilo de visualización \ alfa [\ eta] = \ psi _ {\ eta} (0)}$
Si , entonces y , ${\ estilo de visualización \ alfa = \ psi _ {\ nu +1} (0)}$ ${\displaystyle \operatorname {cof} (\alpha )=\Omega _{\nu +1))$ $\alpha [\eta ]=\Omega _{\nu +1}[\eta ]=\eta$
Si , entonces y (nótese que: ), ${\ estilo de visualización \ alfa = \ psi _ {\ nu} (\ beta +1)}$ ${\ estilo de visualización \ nombre del operador {cof} (\ alfa) = \ omega}$ ${\ estilo de visualización \ alfa [\ eta] = \ psi _ {\ nu} (\ beta) \ cdot \ eta}$ ${\ estilo de visualización \ psi _ {\ nu} (0) = \ Omega _ {\ nu}}$
Si y , entonces y , ${\ estilo de visualización \ alfa = \ psi _ {\ nu} (\ beta)}$ ${\displaystyle \operatorname {cof} (\beta )\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu <\nu \))$ $\operatorname {cof} (\alpha)=\operatorname {cof} (\beta)$ ${\ estilo de visualización \ alfa [\ eta] = \ psi _ {\ nu} (\ beta [\ eta])}$
Si y , entonces y , dónde . ${\ estilo de visualización \ alfa = \ psi _ {\ nu} (\ beta)}$ ${\displaystyle \operatorname {cof} (\beta )\in \{\Omega _{\mu +1}\mid \mu \geq \nu \))$ ${\ estilo de visualización \ nombre del operador {cof} (\ alfa) = \ omega}$ ${\ estilo de visualización \ alfa [\ eta] = \ psi _ {\ nu} (\ beta [\ gamma [\ eta]])}$ $\left\{{\begin{array}{lcr}\gamma [0]=\Omega_{\mu}\\\gamma [\eta +1]=\psi_{\mu}(\beta [\gamma [\eta ]])\\\end{matriz}}\right.$

Una explicación de los principios de notación

Dado que Buchholz trabaja en el sistema Zermelo-Fraenkel , cada ordinal es igual al conjunto de todos los ordinales más pequeños, . La condición significa que el conjunto contiene todos los ordinales menores que o en otras palabras . $\alfa$ ${\ estilo de visualización \ alfa = \ {\ beta \ mid \ beta <\ alfa \))$ $C_{\nu }^{0}(\alpha )=\Omega _{\nu }$ $C_{\nu }^{0}(\alpha )$ $\Omega_\nu$ ${\displaystyle C_{\nu }^{0}(\alpha )=\{\beta \mid \beta <\Omega _{\nu }\))$

La condición significa que el conjunto contiene: $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 ) \cuña \mu \leq \omega \}$ $C_{\nu }^{n+1}(\alpha )$

todos los ordinales del conjunto anterior , $C_{\nu }^{n}(\alpha )$

todos los ordinales que se pueden obtener sumando aditivamente los ordinales principales del conjunto anterior , $C_{\nu }^{n}(\alpha )$

todos los ordinales que se pueden obtener usando ordinales (menores que ) del conjunto anterior como argumentos de funciones , donde . $\alfa$ $C_{\nu }^{n}(\alpha )$ ${\ estilo de visualización \ psi _ {\ mu}}$ ${\ estilo de visualización \ mu \ leq \ omega}$

Por lo tanto, esta condición se puede reescribir de la siguiente manera:

C_{\nu }^{n+1}(\alpha )=\{\beta +\gamma ,\psi _{\mu }(\eta )\mid \beta ,\gamma ,\eta \in C_{\nu }^{n}(\alpha )\cuña \eta <\alpha \cuña \mu \leq \omega \}.

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

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

Considere los siguientes ejemplos:

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

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

(ya que no hay valores de función para , y 0 + 0 = 0).

{\ estilo de visualización \ psi _ {\ nu}}

{\ estilo de visualización \ eta <0}

entonces _ ${\ estilo de visualización \ psi _ {0} (0) = 1}$

${\ estilo de visualización C_ {0} (1)}$ contiene todas las sumas posibles de números naturales. Por tanto, es el primer ordinal transfinito, que es mayor que todos los números naturales por definición. ${\ estilo de visualización \ psi _ {0} (0) = 1}$ ${\ estilo de visualización \ psi _ {0} (1) = \ omega}$

${\ estilo de visualización C_ {0} (2)}$ contiene todas sus sumas posibles. Por lo tanto, . ${\ estilo de visualización \ psi _ {0} (0) = 1, \ psi _ {0} (1) = \ omega}$ ${\ estilo de visualización \ psi _ {0} (2) = \ omega ^ {2}}$

Si , entonces y . ${\ estilo de visualización \ alfa = \ 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 ))$

Si , entonces y es el número épsilon más pequeño , es decir, el primer punto fijo . ${\ estilo de visualización \ alfa = \ 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))$ ${\ estilo de visualización \ alfa = \ omega ^ {\ alfa}}$

Si , entonces y . ${\ estilo de visualización \ alfa = \ 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))$ es el segundo número épsilon ,

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

, es decir, el primer punto fijo ,

{\ estilo de visualización \ alfa = \ varepsilon _ {\ alfa}}

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

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

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

– Ackermann ordinal ,

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

– Small Veblen ordinal ,

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

– Gran Veblen ordinal ,

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

Ahora veamos cómo funciona la función : $\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 \}

, es decir, contiene todos los ordinales contables. Por lo tanto, contiene todas las sumas posibles de todos los ordinales contables, y es el primer ordinal incontable que es mayor que todos los ordinales contables por definición, es decir, el ordinal más pequeño con cardinalidad .

{\ estilo de visualización C_ {1} (0)}

{\ estilo de visualización \ psi _ {1} (0) = \ Omega _ {1}}

\aleph_1

Si , entonces y . $\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

, donde es un número natural, ,

k

k\geq 2

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

Para el caso, el conjunto contiene funciones con todos los argumentos menores que , es decir, argumentos como ${\ estilo de visualización \ psi (\ psi _ {2} (0)) = \ psi (\ Omega _ {2})}$ $C_{0}(\Omega _{2})$ $\psi_{0}$ ${\ estilo de visualización \ omega _ {2}}$ $0,\psi_{1}(0),\psi_{1}(\psi_{1}(0)),\psi_{1}^{3}(0),\ldots, \psi _{1}^{\omega}(0)$

y entonces

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

En general:

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

Notas

↑ Buchholz, W. Un nuevo sistema de funciones ordinales teóricas de prueba (indefinido) // Annals of Pure and Applied Logic. - T. 32 .
↑ Jäger, G. -ordinales inaccesibles, funciones colapsadas y un sistema de notación recursivo // Archiv f. Matemáticas. Lógica y Grundlagenf. : diario. - 1984. - vol. 24 , núm. 1 . - P. 49-62 . $\rho$
↑ Buchholz, W.; Schütte, K. Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der -Separation und Bar-Induktion (alemán) // Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. clase: tienda. — 1983. ${\ estilo de visualización \ Pi _ {2} ^ {1}}$

Enlaces

Grandes números
Números	gogol Número de Shannon googolplex número de sesgos número de Moser número de graham ÁRBOL(3) Número de Rayo
Funciones	Función de Ackermann Función Veblen Funciones psi de Buchholz tetración pentación hiperoperador Jerarquía de rápido crecimiento Jerarquía de crecimiento lento Jerarquía resistente
Notaciones	Notación de Steinhaus-Moser Notación de flecha Knuth Notación de flecha de Conway Notación masiva de Bowers