O de Kleene

En teoría de conjuntos y teoría de computabilidad , el de Kleene ${\displaystyle {\mathcal {O}}}$ es un subconjunto canónico de los números naturales cuando se consideran como notaciones ordinales . Contiene notaciones ordinales para cada ordinal computable , es decir, ordinales por debajo del ordinal de Church-Kleene , . Dado que es el primer ordinal no representable en un sistema computable de notaciones ordinales, los elementos de pueden considerarse como notaciones ordinales canónicas. ${\displaystyle \omega _{1}^{\text{CK}}}$ ${\displaystyle \omega _{1}^{\text{CK}}}$ ${\displaystyle {\mathcal {O}}}$

Kleene (1938) describió un sistema de notación para todos los ordinales computables (aquellos menores que el ordinal de Church-Kleene ). Utiliza un subconjunto de los números naturales en lugar de cadenas finitas de símbolos. Desafortunadamente, 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 representen la suma, el producto y la potencia de los ordinales (ver aritmética ordinal ) de dos notaciones dadas en Kleene ; y dada cualquier notación para un ordinal, existe un conjunto de notaciones computablemente enumerables que contiene un elemento para cada ordinal más pequeño y está efectivamente ordenado. ${\displaystyle {\mathcal {O}}}$

Definición

La idea básica del sistema de notaciones ordinales de Kleene es construir ordinales de manera efectiva. Para los miembros de , el ordinal para el cual es una notación es . y (una ordenación parcial de Kleene ) son los conjuntos más pequeños tales que se cumple lo siguiente. ^{[ cita requerida ]} ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle p}$ ${\displaystyle |p|}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle <_{\mathcal {O}}}$ ${\displaystyle {\mathcal {O}}}$

• ${\displaystyle 0\in {\mathcal {O}}\land |0|=0}$.
• ${\displaystyle i\in {\mathcal {O}}\land |i|=\alpha \rightarrow 2^{i}\in {\mathcal {O}}\land |2^{i}|=\alpha +1\land i<_{\mathcal {O}}2^{i}}$
• Supongamos que es la función computable parcial -ésima . Si es total y , entonces ${\displaystyle \{e\}}$ ${\displaystyle e}$ ${\displaystyle e}$ ${\displaystyle {\textrm {range}}(\{e\})\subset {\mathcal {O}}\land \forall n(\{e\}(n)<_{\mathcal {O}}\{e\}(n+1))}$ ${\displaystyle 3\cdot 5^{e}\in {\mathcal {O}}\land \forall n,\{e\}(n)<_{\mathcal {O}}3\cdot 5^{e}\land |3\cdot 5^{e}|=\lim _{k}|\{e\}(k)|}$
• ${\displaystyle p<_{\mathcal {O}}q\land q<_{\mathcal {O}}r\rightarrow p<_{\mathcal {O}}r}$

Esta definición tiene las ventajas de que se pueden enumerar de forma computacional los predecesores de un ordinal dado (aunque no en el ordenamiento) y que las notaciones son cerradas hacia abajo, es decir, si hay una notación para y entonces hay una notación para . Hay definiciones alternativas, como el conjunto de índices de los ordenamientos (parciales) correctos de los números naturales. ^[1] ${\displaystyle <_{\mathcal {O}}}$ ${\displaystyle \gamma }$ ${\displaystyle \alpha <\gamma }$ ${\displaystyle \alpha }$

Explicación

Un miembro de Kleene se llama notación y está destinado a dar una definición del ordinal . ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle |p|}$

Las notaciones sucesoras son aquellas tales que es un ordinal sucesor . En Kleene , un ordinal sucesor se define en términos de una notación para el ordinal que lo precede inmediatamente. Específicamente, una notación sucesora tiene la forma de alguna otra notación , de modo que . ${\displaystyle |p|}$ ${\displaystyle \alpha +1}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle p}$ ${\displaystyle 2^{q}}$ ${\displaystyle q}$ ${\displaystyle |p|=|q|+1}$

Las notaciones límite son aquellas tales que es un ordinal límite. En Kleene , una notación para un ordinal límite equivale a una secuencia computable de notaciones para ordinales más pequeños que limitan a . Cualquier notación límite tiene la forma donde la 'ésima función parcial computable es una función total que enumera una secuencia infinita de notaciones, que son estrictamente crecientes bajo el orden . El límite de la secuencia de ordinales es . ${\displaystyle |p|}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle \beta }$ ${\displaystyle \beta }$ ${\displaystyle p}$ ${\displaystyle 3\cdot 5^{e}}$ ${\displaystyle e}$ ${\displaystyle \{e\}:\mathbb {N} \rightarrow \mathbb {N} }$ ${\displaystyle \langle q_{0},q_{1}...\rangle }$ ${\displaystyle <_{\mathcal {O}}}$ ${\displaystyle \langle |q_{0}|,|q_{1}|...\rangle }$ ${\displaystyle |p|}$

Aunque implica , no implica .​ ${\displaystyle q<_{\mathcal {O}}p}$ ${\displaystyle |q|<|p|}$ ${\displaystyle |q|<|p|}$ ${\displaystyle q<_{\mathcal {O}}p}$

Para que , se debe poder alcanzar desde mediante la aplicación repetida de las operaciones y para . En otras palabras, cuando se hace referencia a él en la definición de dada por . ${\displaystyle q<_{\mathcal {O}}p}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle 2^{n}\mapsto n}$ ${\displaystyle 3\cdot 5^{e}\mapsto \{e\}(i)}$ ${\displaystyle i\in \mathbb {N} }$ ${\displaystyle q<_{\mathcal {O}}p}$ ${\displaystyle q}$ ${\displaystyle |p|}$ ${\displaystyle p}$

Un orden computablemente enumerable que extiende el orden de Kleene

Para arbitrario , digamos que cuando se puede alcanzar desde aplicando repetidamente las operaciones y para . La relación concuerda con en , pero es computablemente enumerable : si , entonces un programa de computadora eventualmente encontrará una prueba de este hecho. ${\displaystyle p,q\in \mathbb {N} }$ ${\displaystyle q\prec p}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle 2^{n}\mapsto n}$ ${\displaystyle 3\cdot 5^{e}\mapsto \{e\}(i)}$ ${\displaystyle i\in dom(\{e\})}$ ${\displaystyle \prec }$ ${\displaystyle <_{\mathcal {O}}}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle \prec }$ ${\displaystyle q\prec p}$

Para cualquier notación , todas son en sí mismas notaciones en . ${\displaystyle p\in {\mathcal {O}}}$ ${\displaystyle q\prec p}$ ${\displaystyle {\mathcal {O}}}$

Para , es una notación de solo cuando se cumplen todos los criterios siguientes: ${\displaystyle p\in \mathbb {N} }$ ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}}$

• Para todos , es o bien , una potencia de , o bien, para algunos . ${\displaystyle q\preceq p}$ ${\displaystyle q}$ ${\displaystyle 0}$ ${\displaystyle 2}$ ${\displaystyle 3\cdot 5^{e}}$ ${\displaystyle e\in \mathbb {N} }$
• Para cualquier , si entonces es total y estrictamente creciente bajo ; es decir, para cualquier . ${\displaystyle q\preceq p}$ ${\displaystyle q=3\cdot 5^{e}}$ ${\displaystyle \{e\}}$ ${\displaystyle \prec }$ ${\displaystyle \{e\}(i)\prec \{e\}(i+1)}$ ${\displaystyle i\in \mathbb {N} }$
• El conjunto está bien fundado , por lo que no existen sucesiones descendentes infinitas . ${\displaystyle \{q\in \mathbb {N} :q\prec p\}}$ ${\displaystyle ...\prec q_{1}\prec q_{0}\prec p}$

Propiedades básicas de

• Si y y entonces ; pero lo inverso puede no ser válido. ${\displaystyle |i|=\alpha }$ ${\displaystyle |j|=\beta }$ ${\displaystyle i<_{\mathcal {O}}j\,,}$ ${\displaystyle \alpha <\beta }$
• ${\displaystyle <_{\mathcal {O}}}$induce una estructura de árbol en , por lo que está bien fundada . ${\displaystyle {\mathcal {O}}}$ ${\displaystyle {\mathcal {O}}}$
• ${\displaystyle {\mathcal {O}}}$sólo se ramifica en ordinales límite; y en cada notación de un ordinal límite, se ramifica infinitamente. ${\displaystyle {\mathcal {O}}}$
• Dado que cada función computable tiene un número contable de índices, cada ordinal infinito recibe un número contable de notaciones; los ordinales finitos tienen notaciones únicas, generalmente denotadas . ${\displaystyle n}$ ${\displaystyle n_{\mathcal {O}}}$
• El primer ordinal que no recibe una notación se llama ordinal de Church-Kleene y se denota por . Dado que solo hay un número contable de funciones computables, el ordinal es evidentemente contable. ${\displaystyle \omega _{1}^{\text{CK}}}$ ${\displaystyle \omega _{1}^{\text{CK}}}$
• Los ordinales con una notación en Kleene son exactamente los ordinales computables . (El hecho de que cada ordinal computable tenga una notación se desprende del cierre de este sistema de notaciones ordinales bajo límites sucesores y efectivos). ${\displaystyle {\mathcal {O}}}$
• ${\displaystyle <_{\mathcal {O}}}$no es computablemente enumerable , pero hay una relación computablemente enumerable que concuerda precisamente con en los miembros de . ${\displaystyle <_{\mathcal {O}}}$ ${\displaystyle {\mathcal {O}}}$
• Para cualquier notación , el conjunto de notaciones que se muestra a continuación es computablemente enumerable. Sin embargo, la notación de Kleene , cuando se toma en su totalidad, es (véase jerarquía analítica ) y no aritmética debido a lo siguiente: ${\displaystyle p}$ ${\displaystyle \lbrace q\mid q<_{\mathcal {O}}p\rbrace }$ ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle \Pi _{1}^{1}}$
• ${\displaystyle {\mathcal {O}}}$es -completo (es decir, es y cada conjunto es reducible a él en Turing) ^[2] y cada subconjunto de está efectivamente acotado en (un resultado de Spector). ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle \Sigma _{1}^{1}}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle {\mathcal {O}}}$
• De hecho, cualquier conjunto es reducible muchos-uno a . ^[2] ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle {\mathcal {O}}}$
• ${\displaystyle {\mathcal {O}}}$es el sistema universal de notaciones ordinales en el sentido de que cualquier conjunto específico de notaciones ordinales puede mapearse en él de una manera sencilla. Más precisamente, hay una función computable tal que si es un índice para un buen ordenamiento computable, entonces es un miembro de y es isomorfo en orden a un segmento inicial del conjunto . ${\displaystyle f}$ ${\displaystyle e}$ ${\displaystyle f(e)}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle <_{e}}$ ${\displaystyle \{p\mid p<_{\mathcal {O}}f(e)\}}$
• Existe una función computable , que, para los miembros de , imita la suma ordinal y tiene la propiedad de que . (Jockusch) ${\displaystyle +_{\mathcal {O}}}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle \max\{p,q\}\leq p+_{\mathcal {O}}q}$

Propiedades de las rutas en

Una ruta en es un subconjunto de que está totalmente ordenado por y está cerrado respecto de predecesores, es decir, si es un miembro de una ruta y entonces también es un miembro de . Una ruta es máxima si no hay ningún elemento de que esté por encima (en el sentido de ) de cada miembro de , de lo contrario no es máxima. ${\displaystyle {\mathcal {O}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle <_{\mathcal {O}}}$ ${\displaystyle p}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle q<_{\mathcal {O}}p}$ ${\displaystyle q}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle <_{\mathcal {O}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$

• Un camino no es máximo si y solo si es computablemente enumerable (ce). De las observaciones anteriores se deduce que cada elemento de determina un camino no máximo ; y cada camino no máximo está determinado de esa manera. ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle {\mathcal {P}}}$
• Hay caminos máximos a través de ; dado que son máximos, no son constantes. ${\displaystyle 2^{\aleph _{0}}}$ ${\displaystyle {\mathcal {O}}}$
• De hecho, existen caminos máximos dentro de una longitud de . (Crossley, Schütte) ${\displaystyle 2^{\aleph _{0}}}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle \omega ^{2}}$
• Para cada ordinal distinto de cero , existen caminos máximos dentro de una longitud . (Aczel) ${\displaystyle \lambda <\omega _{1}^{CK}}$ ${\displaystyle 2^{\aleph _{0}}}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle \omega ^{2}\cdot \lambda }$
• Además, si es un camino cuya longitud no es múltiplo de entonces no es máximo. (Aczel) ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \omega ^{2}}$ ${\displaystyle {\mathcal {P}}}$
• Para cada grado ce , existe un miembro de tal que el camino tiene muchos-uno de grado . De hecho, para cada ordinal computable , existe una notación con . (Jockusch) ${\displaystyle d}$ ${\displaystyle e_{d}}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle {\mathcal {P}}=\lbrace p\mid p<_{\mathcal {O}}e_{d}\rbrace }$ ${\displaystyle d}$ ${\displaystyle \alpha \geq \omega ^{2}}$ ${\displaystyle e_{d}}$ ${\displaystyle |e_{d}|=\alpha }$
• Existen caminos a través de los cuales se encuentran . Dada una progresión de teorías computablemente enumerables basadas en la iteración de la Reflexión Uniforme, cada uno de esos caminos es incompleto con respecto al conjunto de oraciones verdaderas. (Feferman y Spector) ${\displaystyle \aleph _{0}}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle \Pi _{1}^{0}}$
• Existen caminos a través de cada segmento inicial que no son meramente ce, sino computables. (Jockusch) ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle {\mathcal {O}}}$
• Se ha demostrado que existen otros caminos , cada uno con tipos específicos de propiedades de reducibilidad. (Ver referencias a continuación) ${\displaystyle {\mathcal {O}}}$

Véase también

• Ordinal computable
• Ordinal contable grande
• Notación ordinal

Referencias

1. SG Simpson, La jerarquía basada en el operador de salto, p. 269. El simposio de Kleene (Holanda del Norte, 1980)
2. Ash, Knight, *Estructuras computables y la jerarquía hiperaritmética* p.83. Estudios de lógica y fundamentos de las matemáticas vol. 144 (2000), ISBN 0-444-50072-3.

• Church, Alonzo (1938), "La segunda clase numérica constructiva", Bull. Amer. Math. Soc. , 44 (4): 224–232, doi : 10.1090/S0002-9904-1938-06720-1
• Kleene, SC (1938), "Sobre la notación de números ordinales", The Journal of Symbolic Logic , 3 (4), Association for Symbolic Logic: 150–155, doi :10.2307/2267778, JSTOR  2267778, S2CID  34314018
• Rogers, Hartley (1987) [1967], La teoría de las funciones recursivas y la computabilidad efectiva , primera edición de bolsillo de MIT Press, ISBN 978-0-262-68052-3
• Feferman, Solomon; Spector, Clifford (1962), "Incompletitud a lo largo de los caminos en las progresiones de teorías", Journal of Symbolic Logic , 27 (4): 383–390, doi :10.2307/2964544, JSTOR  2964544, S2CID  33892829