Orden de Kleene-Brouwer

En la teoría descriptiva de conjuntos , el orden de Kleene–Brouwer u orden de Lusin–Sierpiński ^[1] es un orden lineal en secuencias finitas sobre un conjunto ordenado linealmente , que difiere del orden lexicográfico más comúnmente usado en cómo maneja el caso cuando una secuencia es un prefijo de la otra. En el orden de Kleene–Brouwer, el prefijo es posterior a la secuencia más larga que lo contiene, en lugar de anterior. ${\displaystyle (X,<)}$

El orden de Kleene-Brouwer generaliza la noción de un recorrido de postorden desde árboles finitos a árboles que no son necesariamente finitos. Para árboles sobre un conjunto bien ordenado, el orden de Kleene-Brouwer es en sí mismo un buen ordenamiento si y solo si el árbol no tiene ramas infinitas. Recibe su nombre en honor a Stephen Cole Kleene , Luitzen Egbertus Jan Brouwer , Nikolai Luzin y Wacław Sierpiński .

Definición

Si y son secuencias finitas de elementos de , decimos que cuando existe un tal que: ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle X}$ ${\displaystyle t<_{KB}s}$ ${\displaystyle n}$

• ${\displaystyle t\upharpoonright n=s\upharpoonright n}$y está definido pero no está definido (es decir, se extiende correctamente ), o ${\displaystyle t(n)}$ ${\displaystyle s(n)}$ ${\displaystyle t}$ ${\displaystyle s}$
• Tanto y están definidos, , y . ${\displaystyle s(n)}$ ${\displaystyle t(n)}$ ${\displaystyle t(n)<s(n)}$ ${\displaystyle t\upharpoonright n=s\upharpoonright n}$

Aquí, la notación se refiere al prefijo de hasta pero sin incluir . En términos simples, siempre que sea un prefijo de (es decir, termina antes de , y son iguales hasta ese punto) o esté a la "izquierda" de en el primer lugar en el que difieren. ^[1] ${\displaystyle t\upharpoonright n}$ ${\displaystyle t}$ ${\displaystyle t(n)}$ ${\displaystyle t<_{KB}s}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle s}$

Interpretación de árboles

Un árbol , en la teoría descriptiva de conjuntos, se define como un conjunto de secuencias finitas que está cerrado 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 se puede aumentar para formar un árbol, y el orden de Kleene-Brouwer es un orden natural que se puede dar a este árbol. Es una generalización a árboles potencialmente infinitos del recorrido de postorden de un árbol finito: en cada nodo del árbol, los subárboles hijos reciben su orden de izquierda a derecha, y el nodo mismo viene después de todos sus hijos. El hecho de que el orden de Kleene-Brouwer sea un orden 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 árbol finito en el que el orden de Kleene-Brouwer coincide con el postorden.

La importancia del ordenamiento de Kleene-Brouwer proviene del hecho de que si está bien ordenado , entonces un árbol sobre está bien fundado (no tiene ramas infinitamente largas) si y solo si el ordenamiento de Kleene-Brouwer es un buen ordenamiento de los elementos del árbol. ^[1] ${\displaystyle X}$ ${\displaystyle X}$

Teoría de la recursión

En la teoría de la recursión , el orden de Kleene-Brouwer puede aplicarse 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. A cada estado de un árbol de cálculo se le puede asignar un número ordinal , el supremo de los números ordinales donde se extiende sobre los hijos de en el árbol. De esta manera, los funcionales recursivos totales pueden clasificarse 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 de Kleene-Brouwer de un árbol de cálculo bien fundado es en sí mismo un buen ordenamiento recursivo, y al menos tan grande como el ordinal asignado al árbol, de lo que se deduce que los niveles de esta jerarquía están indexados por ordinales recursivos . ^[2] ${\displaystyle x}$ ${\displaystyle ||x||}$ ${\displaystyle 1+||y||}$ ${\displaystyle y}$ ${\displaystyle x}$

Historia

Este orden fue utilizado por Lusin y Sierpinski (1923), ^[3] y luego por Brouwer (1924). ^[4] Brouwer no cita ninguna referencia, pero Moschovakis sostiene que puede haber visto a Lusin y Sierpinski (1923), o haber sido influenciado por trabajos anteriores de los mismos autores que condujeron a este trabajo. Mucho más tarde, Kleene (1955) estudió el mismo orden y se lo atribuyó a Brouwer. ^[5]

Referencias

1. 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
2. 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, pp. 98–101, ISBN 978-0-521-51769-0, Sr.  2893891.
3. Lusin, Nicolás ; Sierpinski, Waclaw (1923), "Sur un ensemble non measurable B", Journal de Mathématiques Pures et Appliquées , 9 (2): 53–72, archivado desde el original el 14 de abril de 2013.
4. Brouwer, LEJ (1924), "Beweis, dass jede volle Funktion gleichmässig stetig ist", Koninklijke Nederlandse Akademie van Wetenschappen, Proc. Sección de Ciencias , 27 : 189–193Como lo cita Kleene (1955).
5. 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 ordenamientos lineales recursivos", págs. 419-422.