Función de Veblen

Función matemática sobre ordinales

En matemáticas , las funciones de Veblen son una jerarquía de funciones normales ( funciones continuas estrictamente crecientes de ordinales a ordinales), introducidas 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.

Jerarquía de Veblen

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

Secuencias fundamentales de la jerarquía de Veblen

La secuencia fundamental para un ordinal con cofinalidad ω es una ω-secuencia estrictamente creciente distinguida que tiene al ordinal como su límite. Si uno tiene secuencias fundamentales para α y todos los ordinales límite más pequeños, entonces uno 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 para α se indicará por α [ n ].

Una variación de la forma normal de Cantor utilizada en conexión con la jerarquía de Veblen es: cada número ordinal distinto de cero α se puede escribir de forma única como , 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, y cada Si se puede proporcionar una secuencia fundamental para el último término, entonces ese término se puede reemplazar por dicha secuencia para obtener ${\displaystyle \alpha =\varphi _{\beta _{1}}(\gamma _{1})+\varphi _{\beta _{2}}(\gamma _{2})+\cdots +\varphi _{\beta _{k}}(\gamma _{k})}$ ${\displaystyle \varphi _{\beta _{m}}(\gamma _{m})\geq \varphi _{\beta _{m+1}}(\gamma _{m+1})\,,}$ ${\displaystyle \gamma _{m}<\varphi _{\beta _{m}}(\gamma _{m}).}$ ${\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 entonces sea ${\displaystyle \gamma <\varphi _{\beta }(\gamma )\,,}$ ${\displaystyle \varphi _{\beta }(\gamma )[n]=\varphi _{\beta }(\gamma [n])\,.}$

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

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

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

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

Supongamos ahora que β es un límite:

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

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

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

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 que sea y ${\displaystyle \Gamma _{0}[0]=0}$ ${\displaystyle \Gamma _{0}[n+1]=\varphi _{\Gamma _{0}[n]}(0)\,.}$

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

Para Γ _β donde es un límite, sea ${\displaystyle \beta <\Gamma _{\beta }}$ ${\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 finita), sea la función binaria como se definió anteriormente. ${\displaystyle \varphi (\alpha ,\gamma )}$ ${\displaystyle \varphi _{\alpha }(\gamma )}$

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

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

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

El ordinal se conoce a veces como ordinal de Ackermann . El límite de donde el número de ceros es mayor que ω se conoce a veces como ordinal de Veblen "pequeño" . ${\displaystyle \varphi (1,0,0,0)}$ ${\displaystyle \varphi (1,0,...,0)}$

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

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

dónde

• ${\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 donde y cada uno ${\displaystyle \alpha _{m,1},\alpha _{m,2},...,\alpha _{m,n_{m}}}$ ${\displaystyle \alpha _{m,1}>0}$ ${\displaystyle \alpha _{m,i}<\varphi (s_{m})}$

Sucesiones fundamentales para ordinales límite de la función finita de Veblen

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

• ${\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 si y es un ordinal sucesor, ${\displaystyle \varphi (s,\beta ,z,\gamma )[n+1]=\varphi (s,\beta -1,\varphi (s,\beta ,z,\gamma )[n],z)}$ ${\displaystyle \gamma =0}$ ${\displaystyle \beta }$
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[0]=\varphi (s,\beta ,z,\gamma -1)+1}$y si y son ordinales sucesores, ${\displaystyle \varphi (s,\beta ,z,\gamma )[n+1]=\varphi (s,\beta -1,\varphi (s,\beta ,z,\gamma )[n],z)}$ ${\displaystyle \gamma }$ ${\displaystyle \beta }$
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta ,z,\gamma [n])}$Si es un ordinal límite, ${\displaystyle \gamma }$
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta [n],z,\gamma )}$si y es un ordinal límite, ${\displaystyle \gamma =0}$ ${\displaystyle \beta }$
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta [n],\varphi (s,\beta ,z,\gamma -1)+1,z)}$si es un ordinal sucesor y es un ordinal límite. ${\displaystyle \gamma }$ ${\displaystyle \beta }$

Transfinitamente muchas variables

En términos más generales, Veblen demostró que φ puede definirse incluso para una secuencia transfinita de ordinales α _β , siempre que todos ellos, salvo un número finito, sean cero. Nótese que si dicha secuencia de ordinales se elige entre aquellos menores que un cardinal regular incontable κ, entonces la secuencia puede codificarse como un único ordinal menor que κ ^κ (exponenciación ordinal). Por lo tanto, se está definiendo una función φ de κ ^κ en κ.

La definición puede darse de la siguiente manera: 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 β abarca todas las secuencias que se obtienen al disminuir el valor distinto de cero de índice más pequeño de α y reemplazar algún valor de índice más pequeño con el indeterminado ξ (es decir, β = α [ζ@ι ₀ ,ξ@ι] lo que significa que para el índice más pequeño ι ₀ tal que α _{ι 0} es distinto de cero, este último ha sido reemplazado por algún valor ζ<α _{ι 0} y que para algún índice más pequeño ι<ι ₀ , el valor α _ι =0 ha sido reemplazado por ξ).

Por ejemplo, si α =(1@ω) denota la secuencia transfinita con valor 1 en ω y 0 en el resto, entonces φ(1@ω) es el punto fijo más pequeño de todas las funciones ξ↦φ(ξ,0,...,0) con un número finito de ceros finales (es también el límite de φ(1,0,...,0) con un número finito de ceros, el pequeño ordinal 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" utilizando la función de Veblen de un número transfinito de variables) a veces se conoce como el ordinal de Veblen "grande" o el número de Veblen "grande". ^[3]

Más extensiones

En Massmann & Kwon (2023), la función de Veblen se amplió aún más a un sistema algo técnico conocido como Veblen dimensional . En este, se pueden tomar puntos fijos o números de fila, lo que significa que son válidas expresiones como φ (1@(1,0)) (que representan el ordinal grande de Veblen), visualizadas como matrices multidimensionales. Se demostró que todos los ordinales por debajo del ordinal de Bachmann-Howard podían representarse en este sistema, y ​​que las representaciones para todos los ordinales por debajo del ordinal grande de Veblen eran estéticamente iguales que en el sistema original.

Valores

La función asume varios valores destacados:

• ${\displaystyle \varphi (1,0)=\varepsilon _{0}}$es el ordinal demostrativo-teórico de la aritmética de Peano y el límite de qué ordinales pueden representarse en términos de la forma normal de Cantor y ordinales más pequeños.
• ${\displaystyle \varphi (\omega ,0)}$, un límite en los tipos de orden de los ordenamientos de rutas recursivas con un número finito de símbolos de función, y el ordinal más pequeño cerrado bajo funciones ordinales recursivas primitivas . ^{[4] [5]}
• El ordinal de Feferman–Schütte es igual a . ^[6] ${\displaystyle \Gamma _{0}}$ ${\displaystyle \varphi (1,0,0)}$
• El ordinal pequeño de Veblen es igual a . ^[7] ${\displaystyle \varphi {\begin{pmatrix}1\\\omega \end{pmatrix}}}$

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, vol. 1407, Berlín: Springer-Verlag, doi :10.1007/978-3-540-46825-7, ISBN 978-3-540-51842-6, Sr.  1026933
• Schütte, Kurt (1977), Teoría de la prueba , Grundlehren der Mathematischen Wissenschaften, vol. 225, Berlín-Nueva York: Springer-Verlag, págs. xii+299, ISBN 978-3-540-07911-8, Sr.  0505313
• Takeuti, Gaisi (1987), Teoría de la prueba , Estudios de lógica y fundamentos de las matemáticas, vol. 81 (segunda edición), Ámsterdam: North-Holland Publishing Co., ISBN 978-0-444-87943-1, Sr.  0882549
• Smorynski, C. (1982), "Las variedades de la experiencia arbórea", Math. Intelligencer , 4 (4): 182–189, doi :10.1007/BF03023553contiene una descripción informal de la jerarquía de Veblen.
• Veblen, Oswald (1908), "Funciones de crecimiento continuo 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
• Massmann, Jayde Sylvie; Kwon, Adrian Wang (20 de octubre de 2023), Ampliación de la función de Veblen, arXiv : 2310.12832{{citation}}: CS1 maint: date and year (link)

Citas

1. Stephen G. Simpson , Subsistemas de aritmética de segundo orden (2009, p. 387)
2. M. Rathjen, Notaciones ordinales basadas en un cardinal débilmente Mahlo, (1990, p.251). Consultado el 16 de agosto de 2022.
3. M. Rathjen, "El arte del análisis ordinal" (2006), publicado en Actas del Congreso Internacional de Matemáticos de 2006.
4. N. Dershowitz, M. Okada, Técnicas teóricas de prueba para la teoría de reescritura de términos (1988). p.105
5. Avigad, Jeremy (23 de mayo de 2001). "Análisis ordinal de la teoría de conjuntos admisibles mediante recursión en notaciones ordinales" (PDF) . Journal of Mathematical Logic . 2 : 91-112. doi :10.1142/s0219061302000126.
6. D. Madore, "Un zoológico de ordinales" (2017). Consultado el 2 de noviembre de 2022.
7. Ranzi, Florian; Strahm, Thomas (2019). "Un sistema de tipos flexible para el ordinal Veblen pequeño" (PDF) . Archivo de Lógica Matemática . 58 (5–6): 711–751. doi :10.1007/s00153-019-00658-x. S2CID  253675808.