Función Veblen

Función matemática en ordinales

En matemáticas , las funciones Veblen son una jerarquía de las funciones normales ( continua aumentando estrictamente funciones de los ordinales a los ordinales), introducido por Oswald Veblen en Veblen (1908) . Si φ ₀ es cualquier función normal, entonces para cualquier α ordinal distinto de cero, φ _α es la función que enumera los puntos fijos comunes de φ _β para β <α. Todas estas funciones son normales.

La jerarquía de Veblen

En el caso especial cuando φ ₀ (α) = ω ^α esta familia de funciones se conoce como la jerarquía de Veblen . La función φ ₁ es la misma que la función ε : φ ₁ (α) = ε _α . Si${\displaystyle \alpha <\beta \,,}$ luego ${\displaystyle \varphi _{\alpha }(\varphi _{\beta }(\gamma ))=\varphi _{\beta }(\gamma )\,.}$De esto y del hecho de que φ _β es estrictamente creciente, obtenemos el orden:${\displaystyle \varphi _{\alpha }(\beta )<\varphi _{\gamma }(\delta )}$ si y solo si (${\displaystyle \alpha =\gamma }$ y ${\displaystyle \beta <\delta }$) o (${\displaystyle \alpha <\gamma }$ y ${\displaystyle \beta <\varphi _{\gamma }(\delta )}$) o (${\displaystyle \alpha >\gamma }$ y ${\displaystyle \varphi _{\alpha }(\beta )<\delta }$).

Secuencias fundamentales para la jerarquía de Veblen

La secuencia fundamental para un ordinal con cofinalidad ω es una secuencia ω distinguida estrictamente creciente que tiene el ordinal como su límite. Si uno tiene secuencias fundamentales para α y todos los ordinales límite más pequeños, entonces se puede crear una biyección constructiva explícita entre ω y α, (es decir, una que no use el axioma de elección). Aquí describiremos secuencias fundamentales para la jerarquía de ordinales de Veblen. La imagen de n bajo la secuencia fundamental de α se indicará mediante α [ n ].

Una variación de la forma normal de Cantor utilizada en relación con la jerarquía de Veblen es: cada número ordinal α distinto de cero se puede escribir de forma única como${\displaystyle \alpha =\varphi _{\beta _{1}}(\gamma _{1})+\varphi _{\beta _{2}}(\gamma _{2})+\cdots +\varphi _{\beta _{k}}(\gamma _{k})}$, donde k > 0 es un número natural y cada término después del primero es menor o igual que el término anterior,${\displaystyle \varphi _{\beta _{m}}(\gamma _{m})\geq \varphi _{\beta _{m+1}}(\gamma _{m+1})\,,}$ y cada ${\displaystyle \gamma _{m}<\varphi _{\beta _{m}}(\gamma _{m})\,.}$ Si se puede proporcionar una secuencia fundamental para el último término, entonces ese término puede ser reemplazado por dicha secuencia para obtener ${\displaystyle \alpha [n]=\varphi _{\beta _{1}}(\gamma _{1})+\cdots +\varphi _{\beta _{k-1}}(\gamma _{k-1})+(\varphi _{\beta _{k}}(\gamma _{k})[n])\,.}$

Para cualquier β, si γ es un límite con ${\displaystyle \gamma <\varphi _{\beta }(\gamma )\,,}$ entonces deja ${\displaystyle \varphi _{\beta }(\gamma )[n]=\varphi _{\beta }(\gamma [n])\,.}$

No se puede proporcionar tal secuencia para ${\displaystyle \varphi _{0}(0)}$= ω ⁰ = 1 porque no tiene cofinalidad ω.

Para ${\displaystyle \varphi _{0}(\gamma +1)=\omega ^{\gamma +1}=\omega ^{\gamma }\cdot \omega \,,}$ nosotros elegimos ${\displaystyle \varphi _{0}(\gamma +1)[n]=\varphi _{0}(\gamma )\cdot n=\omega ^{\gamma }\cdot n\,.}$

Para ${\displaystyle \varphi _{\beta +1}(0)\,,}$ usamos ${\displaystyle \varphi _{\beta +1}(0)[0]=0}$ y ${\displaystyle \varphi _{\beta +1}(0)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(0)[n])\,,}$ es decir, 0, ${\displaystyle \varphi _{\beta }(0)}$, ${\displaystyle \varphi _{\beta }(\varphi _{\beta }(0))}$, etc.

Para ${\displaystyle \varphi _{\beta +1}(\gamma +1)}$, usamos ${\displaystyle \varphi _{\beta +1}(\gamma +1)[0]=\varphi _{\beta +1}(\gamma )+1}$ y ${\displaystyle \varphi _{\beta +1}(\gamma +1)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(\gamma +1)[n])\,.}$

Ahora suponga que β es un límite:

Si ${\displaystyle \beta <\varphi _{\beta }(0)}$, luego deja ${\displaystyle \varphi _{\beta }(0)[n]=\varphi _{\beta [n]}(0)\,.}$

Para ${\displaystyle \varphi _{\beta }(\gamma +1)}$, utilizar ${\displaystyle \varphi _{\beta }(\gamma +1)[n]=\varphi _{\beta [n]}(\varphi _{\beta }(\gamma )+1)\,.}$

De lo contrario, el ordinal no se puede describir en términos de ordinales más pequeños utilizando ${\displaystyle \varphi }$ y este esquema no se aplica a él.

La función Γ

La función Γ enumera los ordinales α tales que φ _α (0) = α. Γ ₀ es el ordinal de Feferman-Schütte , es decir, es el α más pequeño tal que φ _α (0) = α.

Para Γ ₀ , se podría elegir una secuencia fundamental para ser${\displaystyle \Gamma _{0}[0]=0}$ y ${\displaystyle \Gamma _{0}[n+1]=\varphi _{\Gamma _{0}[n]}(0)\,.}$

Para Γ _{β + 1} , sea${\displaystyle \Gamma _{\beta +1}[0]=\Gamma _{\beta }+1}$ y ${\displaystyle \Gamma _{\beta +1}[n+1]=\varphi _{\Gamma _{\beta +1}[n]}(0)\,.}$

Para Γ _β donde${\displaystyle \beta <\Gamma _{\beta }}$ es un limite, deja ${\displaystyle \Gamma _{\beta }[n]=\Gamma _{\beta [n]}\,.}$

Generalizaciones

Un número finito de variables

Para construir la función de Veblen de un número finito de argumentos (función de Veblen finitaria), deje que la función binaria ${\displaystyle \varphi (\alpha ,\gamma )}$ ser ${\displaystyle \varphi _{\alpha }(\gamma )}$ como se define arriba.

Dejar ${\displaystyle z}$ ser una cadena vacía o una cadena que consta de uno o más ceros separados por comas ${\displaystyle 0,0,...,0}$ y ${\displaystyle s}$ ser una cadena vacía o una cadena que consta de uno o más ordinales separados por comas ${\displaystyle \alpha _{1},\alpha _{2},...,\alpha _{n}}$ con ${\displaystyle \alpha _{1}>0}$. La función binaria${\displaystyle \varphi (\beta ,\gamma )}$ Se puede escribir como ${\displaystyle \varphi (s,\beta ,z,\gamma )}$ donde ambos ${\displaystyle s}$ y ${\displaystyle z}$son cadenas vacías. Las funciones finitarias de Veblen se definen de la siguiente manera:

• ${\displaystyle \varphi (\gamma )=\omega ^{\gamma }}$
• ${\displaystyle \varphi (z,s,\gamma )=\varphi (s,\gamma )}$
• Si ${\displaystyle \beta >0}$, luego ${\displaystyle \varphi (s,\beta ,z,\gamma )}$ denota el ${\displaystyle (1+\gamma )}$-th punto fijo común de las funciones ${\displaystyle \xi \mapsto \varphi (s,\delta ,\xi ,z)}$ para cada ${\displaystyle \delta <\beta }$

Por ejemplo, ${\displaystyle \varphi (1,0,\gamma )}$ es el ${\displaystyle (1+\gamma )}$-th punto fijo de las funciones ${\displaystyle \xi \mapsto \varphi (\xi ,0)}$, a saber ${\displaystyle \Gamma _{\gamma }}$; luego${\displaystyle \varphi (1,1,\gamma )}$ enumera los puntos fijos de esa función, es decir, de la ${\displaystyle \xi \mapsto \Gamma _{\xi }}$función; y${\displaystyle \varphi (2,0,\gamma )}$ enumera los puntos fijos de todos los ${\displaystyle \xi \mapsto \varphi (1,\xi ,0)}$. Cada instancia de las funciones de Veblen generalizadas es continua en la última variable distinta de cero (es decir, si se hace que una variable varíe y todas las variables posteriores se mantienen constantemente iguales a cero).

El ordinal ${\displaystyle \varphi (1,0,0,0)}$a veces se conoce como el ordinal de Ackermann . El límite de la${\displaystyle \varphi (1,0,...,0)}$donde el número de ceros varía sobre ω, a veces se lo conoce como el ordinal de Veblen “pequeño” .

Cada ordinal distinto de cero ${\displaystyle \alpha }$ menos que el ordinal de Veblen pequeño (SVO) se puede escribir de forma única en forma normal para la función de Veblen finitaria:

${\displaystyle \alpha =\varphi (s_{1})+\varphi (s_{2})+\cdots +\varphi (s_{k})}$

donde

• ${\displaystyle k}$ es un entero positivo
• ${\displaystyle \varphi (s_{1})\geq \varphi (s_{2})\geq \cdots \geq \varphi (s_{k})}$
• ${\displaystyle s_{m}}$ es una cadena que consta de uno o más ordinales separados por comas ${\displaystyle \alpha _{m,1},\alpha _{m,2},...,\alpha _{m,n_{m}}}$ donde ${\displaystyle \alpha _{m,1}>0}$ y cada ${\displaystyle \alpha _{m,i}<\varphi (s_{m})}$

Secuencias fundamentales para los ordinales límite de la función de Veblen finitaria

Para ordinales límite ${\displaystyle \alpha <SVO}$, escrito en forma normal para la función finitaria de Veblen:

• ${\displaystyle (\varphi (s_{1})+\varphi (s_{2})+\cdots +\varphi (s_{k}))[n]=\varphi (s_{1})+\varphi (s_{2})+\cdots +\varphi (s_{k})[n]}$,
• ${\displaystyle \varphi (\gamma )[n]=\left\{{\begin{array}{lcr}n\quad {\text{if}}\quad \gamma =1\\\varphi (\gamma -1)\cdot n\quad {\text{if}}\quad \gamma \quad {\text{is a successor ordinal}}\\\varphi (\gamma [n])\quad {\text{if}}\quad \gamma \quad {\text{is a limit ordinal}}\\\end{array}}\right.}$,
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[0]=0}$ y ${\displaystyle \varphi (s,\beta ,z,\gamma )[n+1]=\varphi (s,\beta -1,\varphi (s,\beta ,z,\gamma )[n],z)}$ Si ${\displaystyle \gamma =0}$ y ${\displaystyle \beta }$ es un sucesor ordinal,
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[0]=\varphi (s,\beta ,z,\gamma -1)+1}$ y ${\displaystyle \varphi (s,\beta ,z,\gamma )[n+1]=\varphi (s,\beta -1,\varphi (s,\beta ,z,\gamma )[n],z)}$ Si ${\displaystyle \gamma }$ y ${\displaystyle \beta }$ son ordinales sucesores,
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta ,z,\gamma [n])}$ Si ${\displaystyle \gamma }$ es un ordinal límite,
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta [n],z,\gamma )}$ Si ${\displaystyle \gamma =0}$ y ${\displaystyle \beta }$ es un ordinal límite,
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta [n],\varphi (s,\beta ,z,\gamma -1)+1,z)}$ Si ${\displaystyle \gamma }$ es un sucesor ordinal y ${\displaystyle \beta }$ es un ordinal límite.

Transfinitivamente muchas variables

De manera más general, Veblen demostró que φ puede definirse incluso para una secuencia transfinita de ordinales α _β , siempre que todos menos un número finito de ellos sean cero. Observe que si tal secuencia de ordinales se elige entre aquellos menores que un incontable cardinal regular κ, entonces la secuencia se puede codificar como un único ordinal menor que κ ^κ . Entonces uno está definiendo una función φ de κ ^κ a κ.

La definición se puede dar como sigue: sea α una secuencia transfinita de ordinales (es decir, una función ordinal con soporte finito) que termina en cero (es decir, tal que α₀ = 0), y sea α [0↦γ] la misma función donde el 0 final ha sido reemplazado por γ. Entonces γ↦φ ( α [0↦γ]) se define como la función que enumera los puntos fijos comunes de todas las funciones ξ↦φ ( β ) donde β varía sobre todas las secuencias que se obtienen al disminuir el valor distinto de cero indexado más pequeño de α y reemplazar algún valor indexado más pequeño con el indeterminado ξ (es decir, β = α [ι₀↦ζ, ι↦ξ] lo que significa que para el índice más pequeño ι₀ tal que α_ι₀ es distinto de cero, este último ha sido reemplazado por algún valor ζ <α _ι₀ y que para algunos índices más pequeños ι <ι₀, el valor α _ι = 0 ha sido reemplazado por ξ).

Por ejemplo, si α = (ω↦1) denota la secuencia transfinita con valor 1 en ω y 0 en cualquier otro lugar, entonces φ (ω↦1) es el punto fijo más pequeño de todas las funciones ξ↦φ (ξ, 0,… , 0) con un número finito de ceros finales (también es el límite de φ (1,0,…, 0) con un número finito de ceros, el ordinal pequeño de Veblen).

El ordinal más pequeño α tal que α es mayor que φ aplicado a cualquier función con soporte en α (es decir, que no se puede alcanzar "desde abajo" usando la función de Veblen de muchas variables transfinitivamente) se conoce a veces como el ordinal de Veblen "grande" .

Referencias

• Hilbert Levitz, Ordinales transfinitos y sus notaciones: para los no iniciados , artículo expositivo (8 páginas, en PostScript )
• Pohlers, Wolfram (1989), Teoría de la prueba , Lecture Notes in Mathematics, 1407 , Berlín: Springer-Verlag, doi : 10.1007 / 978-3-540-46825-7 , ISBN 978-3-540-51842-6, MR  1026933
• Schütte, Kurt (1977), Teoría de la prueba , Grundlehren der Mathematischen Wissenschaften, 225 , Berlín-Nueva York: Springer-Verlag, págs. Xii + 299, ISBN 978-3-540-07911-8, MR  0505313
• Takeuti, Gaisi (1987), Teoría de la prueba , Estudios de lógica y fundamentos de las matemáticas, 81 (Segunda ed.), Ámsterdam: North-Holland Publishing Co., ISBN 978-0-444-87943-1, MR  0882549
• Smorynski, C. (1982), "Las variedades de la experiencia arbórea", Math. Intelligencer , 4 (4): 182–189, doi : 10.1007 / BF03023553 contiene una descripción informal de la jerarquía de Veblen.
• Veblen, Oswald (1908), "Funciones crecientes continuas de ordinales finitos y transfinitos", Transactions of the American Mathematical Society , 9 (3): 280-292, doi : 10.2307 / 1988605 , JSTOR  1988605
• Miller, Larry W. (1976), "Funciones normales y notaciones ordinales constructivas", The Journal of Symbolic Logic , 41 (2): 439–459, doi : 10.2307 / 2272243 , JSTOR  2272243