Notación ordinal

Se podría continuar de esta manera, pero nos daría un número infinito de funciones. Así que, en su lugar, fusionemos las funciones unarias en una función binaria. Mediante recursión transfinita en${\displaystyle \alpha }$, podemos usar recursión transfinita en${\displaystyle \beta }$definir${\displaystyle \xi (\alpha,\beta)}$ser el ordinal más pequeño${\displaystyle \gamma }$de tal manera que${\displaystyle \alpha <\gamma}$y${\displaystyle \beta <\gamma}$y${\displaystyle \gamma }$no es el valor de${\displaystyle \xi }$para cualquier más pequeño${\displaystyle \alpha }$o por el mismo${\displaystyle \alpha }$con uno más pequeño${\displaystyle \beta }$.

Por lo tanto, defina${\displaystyle \xi }$-notaciones como sigue:

• "${\displaystyle 0}$" es un${\displaystyle \xi }$-notación para cero.
• Si "A" y "B" se reemplazan por${\displaystyle \xi }$-notaciones para${\displaystyle \alpha }$y${\displaystyle \beta }$en "ξAB", entonces el resultado es un${\displaystyle \xi }$-notación para${\displaystyle \xi (\alpha,\beta)}$.
• No hay otros${\displaystyle \xi }$-notaciones.

La función${\displaystyle \xi }$está definido para todos los pares de ordinales y es biyectivo. Siempre da valores mayores que sus argumentos y su rango son todos los ordinales distintos de 0 y los números épsilon .

Uno tiene${\displaystyle \xi (\alpha,\beta)<\xi (\gamma,\delta)}$cuando

• ${\displaystyle \alpha =\gamma }$y${\displaystyle \beta <\delta}$, o
• ${\displaystyle \alpha <\gamma}$y${\displaystyle \beta <\xi (\gamma,\delta)}$, o
• ${\displaystyle \alpha >\gamma }$y${\displaystyle \xi (\alpha ,\beta )\leq \delta }$.

Con esta definición, las primeras notaciones ξ son:

"0" para 0. "ξ00" para 1. "ξ0ξ00" para ξ(0,1)=2. "ξξ000" para ξ(1,0)=ω. "ξ0ξ0ξ00" para 3. "ξ0ξξ000" para ω+1. "ξξ00ξ00" para ω·2. "ξξ0ξ000" para ω ^ω . "ξξξ0000" para${\displaystyle \omega ^{\omega ^{\omega }}.}$

En general,${\displaystyle \xi (0,\beta )=\beta +1}$. Mientras que ξ(1+α,β) = ω ^{ω α} ·(β+k) para k = 0 o 1 o 2 dependiendo de situaciones especiales: k = 2 si α es un número épsilon y β es finito. En caso contrario, k = 1 si β es múltiplo de ω ^{ω α+1} más un número finito. De lo contrario, k = 0.

Eso es:

${\displaystyle \alpha +1=\xi (0,\alpha).}$

${\displaystyle 1\leq \gamma <\omega ^{\omega ^{\beta +1}}\land n<\omega \implies \omega ^{\omega ^{\beta +1}}\cdot \alpha +\omega ^{\omega ^{\beta }}\cdot (\omega \cdot \gamma +n)=\xi (1+\beta ,\omega ^{\omega ^{\beta +1}}\cdot \alpha +(\omega \cdot \gamma +n)).}$

${\displaystyle (0<\alpha \lor \beta <\omega ^{\beta })\land n<\omega \implies \omega ^{\omega ^{\beta +1}}\cdot \alpha +\omega ^{\omega ^{\beta }}\cdot (n+1)=\xi (1+\beta ,\omega ^{\omega ^{\beta +1}}\cdot \alpha +n).}$

${\displaystyle \beta =\omega ^{\beta }\land n<\omega \implies \omega ^{\omega ^{\beta }}\cdot (n+2)=\xi (\beta ,n).}$

Las notaciones ξ permiten nombrar cualquier ordinal menor que _ε₀ con un alfabeto de solo dos símbolos ("0" y "ξ"). Si se amplían estas notaciones añadiendo funciones que enumeren los números épsilon, podrán nombrar cualquier ordinal menor que el primer número épsilon que no pueda ser nombrado por las funciones añadidas. Esta última propiedad, que consiste en añadir símbolos dentro de un segmento inicial de los ordinales para obtener nombres dentro de ese segmento, se denomina completitud (en honor a Solomon Feferman ).

Los "polinomios exponenciales" en 0 y ω proporcionan un sistema de notación ordinal para los ordinales menores que ε ₀ . Existen muchas formas equivalentes de escribirlos; en lugar de polinomios exponenciales, se pueden usar árboles con raíz, paréntesis anidados o el sistema descrito anteriormente.

Las funciones de Veblen de dos variables ( Veblen, 1908 ) pueden utilizarse para proporcionar un sistema de notación ordinal para ordinales menores que el ordinal de Feferman-Schütte . Las funciones de Veblen en un número finito o transfinito de variables proporcionan sistemas de notación ordinal para ordinales menores que los ordinales de Veblen pequeños y grandes .

Ackermann (1951) describió un sistema de notación ordinal bastante más débil que el sistema descrito anteriormente por Veblen. El límite de su sistema se denomina a veces ordinal de Ackermann .

Bachmann (1950) introdujo la idea clave de usar ordinales no numerables para generar nuevos ordinales numerables. Su sistema original era bastante engorroso, ya que requería elegir una secuencia especial que convergiera a cada ordinal. Los sistemas de notación posteriores, introducidos por Feferman y otros, evitaron esta complicación.

Takeuti (1987) describió un sistema de notación ordinal conocido como "diagramas ordinales", cuyo límite es el ordinal Takeuti-Feferman-Buchholz . ^{[ 1 ]} El sistema fue posteriormente simplificado por Feferman.

Feferman introdujo las funciones theta, descritas en Buchholz (1986) de la siguiente manera. Para un ordinal α , θ _α es una función que mapea ordinales a ordinales. A menudo, θ _α ( β ) se escribe como θ α β . El conjunto C ( α , β ) se define por inducción sobre α como el conjunto de ordinales que se pueden generar a partir de 0, ω ₁ , ω ₂ , ..., ω _ω , junto con los ordinales menores que β mediante las operaciones de suma de ordinales y las funciones θ _ξ para ξ < α . Y la función θ _γ se define como la función que enumera los ordinales δ con δ ∉ C ( γ , δ ). El problema con este sistema es que las notaciones ordinales y las funciones de colapso no son idénticas, por lo que esta función no califica como una notación ordinal. No se conoce una notación ordinal asociada.

Buchholz (1986) describió el siguiente sistema de notación ordinal como una simplificación de las funciones theta de Feferman. 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 ( α ) es cerrado bajo la adición ordinal
• C _v ( α ) es cerrado bajo las funciones ψ _u (para u ≤ ω ) aplicadas a argumentos menores que α .

Este sistema tiene aproximadamente la misma fuerza que el sistema de Fefermans, ya que${\displaystyle \theta \varepsilon _{\Omega _{v}+1}0=\psi _{0}(\varepsilon _{\Omega _{v}+1})}$para v ≤ ω . Sin embargo, aunque este sistema es potente, no se considera una notación ordinal. Buchholz creó una notación ordinal asociada, pero es compleja: la definición se encuentra en el artículo principal.

Kleene (1938) describió un sistema de notación para todos los ordinales recursivos (aquellos menores que el ordinal de Church-Kleene ). Desafortunadamente, a diferencia de los otros sistemas descritos anteriormente, en general no hay una manera efectiva de determinar si algún número natural representa un ordinal, o si dos números representan el mismo ordinal. Sin embargo, se pueden encontrar notaciones efectivas que representan la suma, el producto y la potencia ordinales (véase aritmética ordinal ) de cualesquiera dos notaciones dadas en el sistema de Kleene.${\displaystyle {\mathcal {O}}}$y dada cualquier notación para un ordinal, existe un conjunto recursivamente enumerable de notaciones que contiene un elemento para cada ordinal más pequeño y que está efectivamente ordenado.${\displaystyle {\mathcal {O}}}$Denota un conjunto canónico (y muy difícil de computar) de notaciones. Utiliza un subconjunto de los números naturales en lugar de cadenas finitas de símbolos y no es recursiva; por lo tanto, una vez más, no califica como una notación ordinal recursiva.