En la teoría descriptiva de conjuntos , el orden de Kleene-Brouwer o el orden de Lusin-Sierpiński [1] es un orden lineal en secuencias finitas sobre algún conjunto ordenado linealmente, que difiere del orden lexicográfico más comúnmente utilizado en cómo maneja el caso cuando una secuencia es un prefijo de la otra. En el orden Kleene-Brouwer, el prefijo es posterior a la secuencia más larga que lo contiene, en lugar de anterior.
El orden de Kleene-Brouwer generaliza la noción de un recorrido postorder desde árboles finitos a árboles que no son necesariamente finitos. Para árboles sobre un conjunto bien ordenado, el orden Kleene-Brouwer es en sí mismo un buen ordenamiento si y solo si el árbol no tiene una rama infinita. Lleva el nombre de Stephen Cole Kleene , Luitzen Egbertus Jan Brouwer , Nikolai Luzin y Wacław Sierpiński .
Definición
Si y son secuencias finitas de elementos de , Nosotros decimos eso cuando hay un tal que o bien:
- y está definido pero no está definido (es decir se extiende correctamente ), o
- ambas cosas y están definidos, , y .
Aquí, la notación se refiere al prefijo de hasta pero sin incluir . En lenguaje sencillo, cuando sea es un prefijo de (es decir termina antes , y son iguales hasta ese punto) o está a la "izquierda" de en primer lugar difieren. [1]
Interpretación de árboles
Un árbol , en la teoría descriptiva de conjuntos, se define como un conjunto de secuencias finitas que se cierra bajo operaciones de prefijo. El padre en el árbol de cualquier secuencia es la secuencia más corta formada al eliminar su elemento final. Por lo tanto, cualquier conjunto de secuencias finitas puede aumentarse para formar un árbol, y el orden de Kleene-Brouwer es un orden natural que se le puede dar a este árbol. Es una generalización a árboles potencialmente infinitos del recorrido postorder de un árbol finito: en cada nodo del árbol, los subárboles secundarios reciben su orden de izquierda a derecha, y el nodo en sí viene después de todos sus hijos. El hecho de que el orden de Kleene-Brouwer sea un ordenamiento lineal (es decir, que sea transitivo además de total) se sigue inmediatamente de esto, ya que tres secuencias cualesquiera en las que se va a probar la transitividad forman (con sus prefijos) un finito árbol en el que el orden Kleene-Brouwer coincide con el postorder.
La importancia del pedido de Kleene-Brouwer proviene del hecho de que si está bien ordenado , luego un árbol sobreestá bien fundamentado (no tiene ramas infinitamente largas) si y solo si el ordenamiento de Kleene-Brouwer es un ordenamiento correcto de los elementos del árbol. [1]
Teoría de la recursividad
En la teoría de la recursividad , el orden de Kleene-Brouwer se puede aplicar a los árboles de cálculo de implementaciones de funcionales recursivos totales . Un árbol de cálculo está bien fundado si y solo si el cálculo realizado por él es totalmente recursivo. Cada Estadoen un árbol de cálculo se le puede asignar un número ordinal , el supremo de los números ordinales dónde abarca a los hijos de en el árbol. De esta manera, los propios funcionales recursivos totales se pueden clasificar en una jerarquía, de acuerdo con el valor mínimo del ordinal en la raíz de un árbol de cálculo, minimizado sobre todos los árboles de cálculo que implementan el funcional. El orden Kleene-Brouwer de un árbol de cálculo bien fundado es en sí mismo un ordenamiento recursivo bien, y al menos tan grande como el ordinal asignado al árbol, de lo que se sigue que los niveles de esta jerarquía están indexados por ordinales recursivos . [2]
Historia
Este ordenamiento fue utilizado por Lusin & Sierpinski (1923) , [3] y luego nuevamente por Brouwer (1924) . [4] Brouwer no cita ninguna referencia, pero Moschovakis sostiene que pudo haber visto a Lusin & Sierpinski (1923) , o haber sido influenciado por trabajos anteriores de los mismos autores que llevaron a este trabajo. Mucho más tarde, Kleene (1955) estudió el mismo orden y se lo atribuyó a Brouwer. [5]
Referencias
- ^ a b c Moschovakis, Yiannis (2009), Teoría de conjuntos descriptivos (2ª ed.), Rhode Island: American Mathematical Society, págs. 148-149, 203-204, ISBN 978-0-8218-4813-5
- ^ Schwichtenberg, Helmut ; Wainer, Stanley S. (2012), "2.8 Funcionales recursivos de tipo 2 y fundamento", Pruebas y cálculos , Perspectivas en lógica, Cambridge: Cambridge University Press, págs. 98-101, ISBN 978-0-521-51769-0, Señor 2893891.
- ^ Lusin, Nicolas ; Sierpinski, Waclaw (1923), "Sur un ensemble nonmensurable B" , Journal de Mathématiques Pures et Appliquées , 9 (2): 53–72, archivado desde el original el 14 de abril de 2013.
- ^ Brouwer, LEJ (1924), "Beweis, dass jede volle Funktion gleichmässig stetig ist", Koninklijke Nederlandse Akademie van Wetenschappen, Proc. Sección de Ciencias , 27 : 189-193. Como lo cita Kleene (1955) .
- ^ Kleene, SC (1955), "Sobre las formas de los predicados en la teoría de los ordinales constructivos. II", American Journal of Mathematics , 77 : 405–428, doi : 10.2307 / 2372632 , JSTOR 2372632 , MR 0070595. Véase en particular la sección 26, "Una digresión sobre los ordenamientos lineales recursivos", págs. 419–422.