En lógica matemática y teoría de conjuntos , una notación ordinal es una función parcial del conjunto de todas las secuencias finitas de símbolos de un alfabeto finito a un conjunto contable de ordinales , y una numeración de Gödel es una función del conjunto de fórmulas bien formadas ( una fórmula bien formada es 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 orden en fórmulas bien formadas que a su vez induce un buen orden en el subconjunto de números naturales. ALa notación ordinal recursiva debe satisfacer las siguientes dos propiedades adicionales:
- el subconjunto de números naturales es un conjunto recursivo
- el ordenamiento bien inducido en el subconjunto de números naturales es una relación recursiva
Existen muchos de estos esquemas de notaciones ordinales, incluidos los esquemas 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 ), 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í.
Por lo general, se procede definiendo varias funciones de ordinales a ordinales y representando cada función 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 es mayor que cada uno de sus argumentos, por lo 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 tenerlos todos, ya que se contradicen entre sí.
Un ejemplo simplificado usando una función de emparejamiento
Como de costumbre, debemos comenzar con un símbolo constante para cero, "0", que podemos considerar como una función de aridad cero. Esto es necesario porque no hay ordinales más pequeños en términos de los cuales se pueda describir el cero. El siguiente paso más obvio sería definir una función unaria, "S", que lleva un ordinal al ordinal más pequeño mayor que él; en otras palabras, S es la función sucesora. En combinación con cero, el sucesor permite nombrar cualquier número natural.
La tercera función podría definirse como una 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 anteriores de esta función. Esto mapearía β a ω · β excepto cuando β es un punto fijo de esa función más un número finito, en cuyo caso se usa ω · (β + 1).
La cuarta función mapearía α a ω ω · α excepto cuando α es un punto fijo de eso más un número finito, en cuyo caso se usa ω ω · (α + 1).
notación ξ
Se podría seguir así, pero nos daría una infinidad de funciones. Así que, en cambio, fusionemos las funciones unarias en una función binaria. Por recursión transfinita en α, podemos usar la recursividad transfinita en β para definir ξ (α, β) = el γ ordinal más pequeño tal que α <γ y β <γ y γ no es el valor de ξ para cualquier α más pequeño o para el mismo α con una β más pequeña.
Por lo tanto, defina las notaciones ξ de la siguiente manera:
- "0" es una notación ξ para cero.
- Si "A" y "B" se reemplazan por notaciones ξ para α y β en "ξAB", entonces el resultado es una notación ξ para ξ (α, β).
- No hay otras notaciones ξ.
La función ξ está definida para todos los pares de ordinales y es uno a uno. Siempre da valores más grandes que sus argumentos y su rango son todos ordinales distintos de 0 y los números épsilon (ε = ω ε ).
Uno tiene ξ (α, β) <ξ (γ, δ) si y solo si (α = γ y β <δ) o (α <γ y β <ξ (γ, δ)) o (α> γ y ξ (α, β) ≤ δ).
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
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.
De lo contrario, k = 1 si β es un múltiplo de ω ω α + 1 más un número finito.
De lo 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 amplían 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, la adición de símbolos dentro de un segmento inicial de los ordinales da nombres dentro de ese segmento, se llama plenitud (en honor a Solomon Feferman ).
Sistemas de notación ordinal
Hay muchos sistemas diferentes para la notación ordinal introducidos por varios autores. A menudo es bastante difícil convertir entre los diferentes sistemas.
Cantor
Los "polinomios exponenciales" en 0 y ω dan un sistema de notación ordinal para ordinales menores que épsilon cero . Hay muchas formas equivalentes de escribirlas; en lugar de polinomios exponenciales, se pueden utilizar árboles enraizados, paréntesis anidados o el sistema descrito anteriormente.
Veblen
Las funciones de Veblen de 2 variables ( Veblen 1908 ) se pueden usar 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 notaciones ordinales para ordinales menores que los ordinales de Veblen pequeños y grandes .
Ackermann
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 a veces se denomina ordinal de Ackermann .
Bachmann
Bachmann (1950) introdujo la idea clave de usar ordinales incontables para producir nuevos ordinales contables. Su sistema original era bastante complicado de usar, ya que requería elegir una secuencia especial que convergiera en cada ordinal. Los sistemas de notación posteriores introducidos por Feferman y otros evitaron esta complicación.
Takeuti (diagramas ordinales)
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.
Funciones θ de Feferman
Feferman introdujo las funciones theta, descritas en Buchholz (1986) como sigue. La función para un ordinal α, θ α es una función de 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 β por las operaciones de suma ordinal y las funciones θ ξ para ξ <α. Y la función θ γ se define como la función que enumera los ordinales δ con δ∉ C (γ, δ).
Buchholz
Buchholz (1986) describió el siguiente sistema de notación ordinal como una simplificación de las funciones theta de Feferman. Definir:
- Ω ξ = ω ξ si ξ> 0, Ω 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 (α) se cierra bajo adición ordinal
- C v (α) se cierra bajo las funciones ψ u (para u ≤ω) aplicadas a argumentos menores que α.
Este sistema tiene aproximadamente la misma fuerza que el sistema Fefermans, ya que para v ≤ ω.
De Kleene
Kleene (1938) describió un sistema de notación para todos los ordinales recursivos (aquellos menores que el ordinal Church-Kleene ). Utiliza un subconjunto de números naturales en lugar de cadenas finitas de símbolos. Desafortunadamente, a diferencia de los otros sistemas descritos anteriormente, en general no existe una forma eficaz de saber si algún número natural representa un ordinal o si dos números representan el mismo ordinal. Sin embargo, se pueden encontrar efectivamente notaciones que representen la suma ordinal, el producto y la potencia (ver aritmética ordinal ) de dos notaciones dadas cualesquiera en el método de Kleene; y dada cualquier notación para un ordinal, existe un conjunto de notaciones recursivamente enumerables que contiene un elemento para cada ordinal más pequeño y está efectivamente ordenado. De Kleene denota un conjunto canónico (y muy no computable) de notaciones.
Ver también
Referencias
- Ackermann, Wilhelm (1951), "Konstruktiver Aufbau eines Abschnitts der zweiten Cantorschen Zahlenklasse", Matemáticas. Z. , 53 (5): 403–413, doi : 10.1007 / BF01175640 , MR 0039669
- Buchholz, W. (1986), "Un nuevo sistema de funciones ordinales de la teoría de la demostración", Ann. Pure Appl. Lógica , 32 (3): 195–207, doi : 10.1016 / 0168-0072 (86) 90052-7 , MR 0865989
- "Sistemas de notación ordinal constructiva" por Fredrick Gass
- Kleene, SC (1938), "Sobre la notación para números ordinales", The Journal of Symbolic Logic , 3 (4): 150-155, doi : 10.2307 / 2267778 , JSTOR 2267778
- "Conjuntos de índices hiperaritméticos en la teoría de la recursividad" por Steffen Lempp
- Hilbert Levitz, Ordinales transfinitos y sus notaciones: para los no iniciados , artículo expositivo, 1999 (8 páginas, en PostScript )
- 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
- 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
- Rogers, Hartley (1987) [1967], The Theory of Recursive Functions and Effective Computability , Primera edición de bolsillo de prensa del MIT, ISBN 978-0-262-68052-3
- 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
- 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