función de veblen

Función matemática en ordinales

En matemáticas , las funciones de Veblen son una jerarquía de funciones normales ( funciones continuas estrictamente crecientes de ordinales a ordinales), introducida 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 el que φ ₀ (α) = ω ^α , esta familia de funciones se conoce como jerarquía de Veblen . La función φ ₁ es la misma que la función ε : φ ₁ (α)= ε _α . ^[1] Si entonces . ^[2] De esto y del hecho de que φ _β es estrictamente creciente obtenemos el orden: si y sólo 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 para la jerarquía de Veblen

La secuencia fundamental para un ordinal con cofinalidad ω es una secuencia ω estrictamente creciente que tiene el ordinal como 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 utilice 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 α estará indicada por α[ 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 , 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 uno 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 usamos 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])\,.}$

Ahora supongamos que β es un límite:

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

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

Para Γ _β+1 , sean 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), deje que la función binaria sea 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 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 todos los . 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 a veces se conoce como ordinal de Ackermann . El límite donde el número de ceros supera ω, a veces se conoce como el ordinal de Veblen "pequeño" . ${\displaystyle \varphi (1,0,0,0)}$ ${\displaystyle \varphi (1,0,...,0)}$

Cada 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 finita de Veblen: ${\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 ${\displaystyle \alpha _{m,1},\alpha _{m,2},...,\alpha _{m,n_{m}}}$ ${\displaystyle \alpha _{m,1}>0}$ ${\displaystyle \alpha _{m,i}<\varphi (s_{m})}$

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

Para 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)}$if es un ordinal sucesor y es un ordinal límite. ${\displaystyle \gamma }$ ${\displaystyle \beta }$

Transfinitas 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. Tenga en cuenta 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). Entonces uno está definiendo una función φ de κ ^κ a κ.

La definición se puede dar 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 disminuyendo 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 α _{ι 0} sea distinto de cero, este último ha sido reemplazado por algún valor ζ<α _{ι 0} y que para algún índice menor ι<ι ₀ , el valor α _ι =0 ha sido reemplazado por ξ).

Por ejemplo, si α =(1@ω) denota la secuencia transfinita con valor 1 en ω y 0 en todos los demás lugares, 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 del φ(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" usando la función de Veblen de un número infinito de variables) a veces se conoce como el ordinal de Veblen "grande" . o "gran" número de Veblen. ^[3]

Otras ampliaciones

En Massmann & Kwon (2023), la función Veblen se extendió aún más a un sistema algo técnico conocido como Veblen dimensional . En esto, se pueden tomar puntos fijos o números de fila, lo que significa que expresiones como φ(1@(1,0)) son válidas (que representan el ordinal de Veblen grande), 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 de todos los ordinales por debajo del ordinal de Veblen grande eran estéticamente las mismas que en el sistema original.

Valores

La función adquiere varios valores destacados:

• ${\displaystyle \varphi (1,0)=\varepsilon _{0}}$es el ordinal de la teoría de la prueba de la aritmética de Peano y el límite de los ordinales que se pueden representar 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 ruta recursiva 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-Schutte es igual a . ^[6] ${\displaystyle \Gamma _{0}}$ ${\displaystyle \varphi (1,0,0)}$
• El ordinal de Veblen pequeño 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, señor  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, SEÑOR  0505313
• Takeuti, Gaisi (1987), Teoría de la prueba , Estudios de lógica y fundamentos de las matemáticas, vol. 81 (Segunda ed.), Ámsterdam: North-Holland Publishing Co., ISBN 978-0-444-87943-1, señor  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 crecientes continuas de ordinales finitos y transfinitos", Transacciones de la Sociedad Matemática Estadounidense , 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 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 cardenal débilmente Mahlo, (1990, p.251). Consultado el 16 de agosto de 2022.
3. M. Rathjen, "El arte del análisis ordinal" (2006), que aparece en Actas del Congreso Internacional de Matemáticos 2006.
4. N. Dershowitz, M. Okada, Técnicas teóricas de prueba para la teoría de la reescritura de términos (1988). p.105
5. Avigad, Jeremy (23 de mayo de 2001). "Un análisis ordinal de la teoría de conjuntos admisible mediante recursividad en notaciones ordinales" (PDF) . Revista de Lógica Matemática . 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 tipo flexible para el pequeño ordinal de Veblen" (PDF) . Archivo de Lógica Matemática . 58 (5–6): 711–751. doi :10.1007/s00153-019-00658-x. S2CID  253675808.