En lógica matemática y teoría de conjuntos , una notación ordinal es una función parcial que asigna el conjunto de todas las secuencias finitas de símbolos, miembros de un alfabeto finito, a un conjunto contable de ordinales . Una numeración de Gödel es una función que asigna el conjunto de fórmulas bien formadas (una secuencia finita de símbolos en la que se define la función de notación ordinal) de algún lenguaje formal a los números naturales. Esto asocia cada fórmula bien formada con un número natural único, llamado su número de Gödel. Si una numeración de Gödel es fija, entonces la relación de subconjunto en los ordinales induce un ordenamiento en fórmulas bien formadas que a su vez induce un buen ordenamiento en el subconjunto de números naturales. Una notación ordinal recursiva debe satisfacer las siguientes dos propiedades adicionales:
Existen muchos esquemas de notaciones ordinales, incluidos los de Wilhelm Ackermann , Heinz Bachmann , Wilfried Buchholz, Georg Cantor , Solomon Feferman , Gerhard Jäger, Isles, Pfeiffer, Wolfram Pohlers, Kurt Schütte , Gaisi Takeuti (llamados diagramas ordinales ) y Oswald Veblen . Stephen Cole Kleene tiene un sistema de notaciones, llamado O de Kleene , que incluye notaciones ordinales, pero no se comporta tan bien como los otros sistemas descritos aquí.
Generalmente, se procede definiendo varias funciones de ordinales a ordinales y representando cada una de ellas mediante un símbolo. En muchos sistemas, como el conocido sistema de Veblen, las funciones son funciones normales, es decir, son estrictamente crecientes y continuas en al menos uno de sus argumentos, y crecientes en otros argumentos. Otra propiedad deseable para tales funciones es que el valor de la función sea mayor que cada uno de sus argumentos, de modo que un ordinal siempre se describe en términos de ordinales más pequeños. Hay varias propiedades deseables de este tipo. Desafortunadamente, ningún sistema puede tenerlas todas, ya que se contradicen entre sí.
Como es habitual, debemos empezar con un símbolo constante para el cero, "0", que podemos considerar como una función de aridad cero. Esto es necesario porque no hay ordinales menores en función de los cuales se pueda describir el cero. El siguiente paso más obvio sería definir una función unaria, "S", que tome un ordinal hasta el ordinal más pequeño que sea mayor que él; en otras palabras, S es la función sucesora. En combinación con cero, sucesor permite nombrar cualquier número natural.
La tercera función podría definirse como aquella que asigna cada ordinal al ordinal más pequeño que aún no se puede describir con las dos funciones anteriores y los valores previos de esta función. Esto asignaría β a ω·β excepto cuando β es un punto fijo de esa función más un número finito, en cuyo caso se utiliza ω·(β+1).
La cuarta función asignaría α a ω ω ·α excepto cuando α es un punto fijo de ese más un número finito, en cuyo caso se usa ω ω ·(α+1).
Se podría continuar de esta manera, pero obtendríamos un número infinito de funciones. Por lo tanto, en lugar de eso, fusionaremos las funciones unarias en una función binaria. Mediante la recursión transfinita sobre α, podemos usar la recursión transfinita sobre β para definir ξ(α,β) = el ordinal γ más pequeño tal que α < γ y β < γ y γ no es el valor de ξ para ningún α más pequeño o para el mismo α con un β más pequeño.
Por lo tanto, definamos las notaciones ξ de la siguiente manera:
La función ξ está definida para todos los pares de ordinales y es biunívoca. Siempre da valores mayores que sus argumentos y su rango son todos los ordinales distintos de 0 y los números épsilon (ε=ω ε ) .
Se tiene ξ(α, β) < ξ(γ, δ) si y sólo si (α = γ y β < δ) o (α < γ y β < ξ(γ, δ)) o (α > γ y ξ(α, β) ≤ δ).
Con esta definición, las primeras notaciones ξ son:
En general, ξ(0,β) = β+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 un múltiplo de ω ω α+1 más un número finito.
En caso contrario, k = 0.
Las notaciones ξ se pueden usar para nombrar cualquier ordinal menor que ε 0 con un alfabeto de solo dos símbolos ("0" y "ξ"). Si estas notaciones se extienden agregando funciones que enumeran números épsilon, entonces podrán nombrar cualquier ordinal menor que el primer número épsilon que no pueda ser nombrado por las funciones agregadas. Esta última propiedad, agregar símbolos dentro de un segmento inicial de los ordinales da nombres dentro de ese segmento, se llama plenitud (en honor a Solomon Feferman ).
Existen muchos sistemas diferentes de notación ordinal introducidos por distintos autores. A menudo resulta bastante difícil realizar la conversión entre los diferentes sistemas.
Los "polinomios exponenciales" en 0 y ω dan un sistema de notación ordinal para los ordinales menores que ε 0 . Hay muchas formas equivalentes de escribirlos; en lugar de polinomios exponenciales, se pueden utilizar árboles con raíz, o paréntesis anidados, o el sistema descrito anteriormente.
Las funciones de Veblen de 2 variables (Veblen 1908) se pueden utilizar para dar un sistema de notación ordinal para ordinales menores que el ordinal de Feferman-Schutte . Las funciones de Veblen en un número finito o transfinito de variables dan 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 utilizar ordinales incontables para producir nuevos ordinales contables. Su sistema original era bastante complicado de utilizar, 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 muy poderoso de notación ordinal llamado "diagramas ordinales", que es difícil de entender pero que luego fue simplificado por Feferman.
Feferman introdujo las funciones theta, descritas en Buchholz (1986) de la siguiente manera. Para un ordinal α, θ α es una función que asigna 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, ω 1 , ω 2 , ..., ω ω , junto con los ordinales menores que β mediante las operaciones de adición 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 colapsables no son idénticas y, por lo tanto, 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:
Las funciones ψ v (α) para α un ordinal, v un ordinal como máximo ω, se definen por inducción sobre α de la siguiente manera:
donde C v (α) es el conjunto más pequeño tal que
Este sistema tiene aproximadamente la misma fuerza que el sistema de Feferman, en cuanto a v ≤ ω. Sin embargo, si bien este sistema es poderoso, no califica como una notación ordinal. Buchholz creó una notación ordinal asociada, pero es complicada: 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 un número natural representa un ordinal o si dos números representan el mismo ordinal. Sin embargo, se pueden encontrar notaciones que representan la suma, el producto y la potencia ordinales (ver aritmética ordinal ) de dos notaciones dadas en Kleene ; y dada cualquier notación para un ordinal, existe un conjunto de notaciones enumerables recursivamente que contiene un elemento para cada ordinal más pequeño y está efectivamente ordenado. Kleene denota un conjunto canónico (y muy no computable) de notaciones. Utiliza un subconjunto de los números naturales en lugar de cadenas finitas de símbolos y no es recursivo, por lo tanto, una vez más, no califica como una notación ordinal.
