ordinal computable

En matemáticas , específicamente en computabilidad y teoría de conjuntos , un ordinal computable (o recursivo ) es un número ordinal que puede representarse como un buen ordenamiento computable de números naturales .

Un ordinal${\displaystyle \alpha }$Es computable si existe un buen ordenamiento computable .${\displaystyle \prec }$de un subconjunto computable${\displaystyle S}$de los números naturales que tienen el tipo de orden${\displaystyle \alpha }$⁠ . Esto significa que dado cualquier ⁠${\displaystyle x\in \mathbb {N} }$Es decidible si​​${\displaystyle x\in S}$⁠ , y dado cualquier ⁠${\displaystyle x,y\in S}$Es decidible si${\displaystyle x\prec y}$Alternativamente , esta condición puede caracterizarse con una única máquina de Turing que decide si${\displaystyle x\in S\land y\in S\land x\preceq y}$para cualquier​${\displaystyle x,y\in \mathbb {N} }$⁠ . ^{[ 1 ]}

Otra definición equivalente establece que${\displaystyle \alpha }$⁠ es computable si es finito o es el tipo de orden de un buen ordenamiento computable de todos los números naturales. ^{[ 2 ]} Esta equivalencia se cumple porque, si ⁠${\displaystyle S}$Si es infinito y computable, entonces se puede calcular una biyección .${\displaystyle f:\mathbb {N} \to S}$⁠ dejando ⁠${\displaystyle f(n)}$ser el​${\displaystyle n}$⁠ º elemento de ⁠${\displaystyle S}$en el orden habitual de los números naturales; la búsqueda siempre se detiene porque${\displaystyle S}$es infinito . Si${\displaystyle \langle S,\prec \rangle }$⁠ es un ordenamiento de pozo computable con tipo de orden ⁠${\displaystyle \alpha }$⁠ , luego definiendo ⁠${\displaystyle x\prec _{f}y}$⁠ si y solo si${\displaystyle f(x)\prec f(y)}$Proporciona un ordenamiento computable .${\displaystyle \langle \mathbb {N} ,\prec _ {f}\rangle }$con el mismo tipo de pedido .

Todos los ordinales computables son, por definición, contables . Recíprocamente, para muchos ordinales contables, los testigos "naturales" de la contableidad también son testigos de la computabilidad. Por ejemplo, el orden natural ⁠${\displaystyle <}$De todos los números naturales, cada uno tiene un tipo de orden .${\displaystyle \omega }$⁠ . Dado que existe unamáquina de Turingque decide ⁠${\displaystyle x<y}$⁠ , esto significa que ⁠${\displaystyle \omega }$es un ordinal computable.

Como otro ejemplo, la siguiente es la construcción "canónica" de un buen ordenamiento .${\displaystyle \prec }$de todos los números naturales con tipo de orden${\displaystyle \omega +\omega }$:​ $${\displaystyle {\begin{matrix}0&2&4&6&8&\dots &1&3&5&7&9&\dots \end{matrix}}}$$ Un algoritmo que decide${\displaystyle x\prec y}$⁠ puede ser de la siguiente manera: Devuelve verdadero si ⁠${\displaystyle x}$es par y${\displaystyle y}$es impar, falso si${\displaystyle x}$es extraño y${\displaystyle y}$es par, y de lo contrario devolver${\displaystyle x<y}$Por lo tanto${\displaystyle \omega +\omega }$También es computable. De hecho, con construcciones similares, se puede demostrar que el sucesor de un ordinal computable y la suma, el producto y la potencia de un par de ordinales computables son todos computables.

El conjunto de todos los ordinales computables es cerrado hacia abajo, es decir, si${\displaystyle \alpha }$es computable y${\displaystyle \beta <\alpha}$⁠ , entonces ⁠${\displaystyle \beta }$⁠ también es computable. ^{[ 2 ]} Esto se debe a que cualquier ordenamiento ⁠${\displaystyle \langle S,\prec \rangle }$con tipo de pedido${\displaystyle \alpha }$Tiene un segmento inicial .${\displaystyle \langle S',\prec \rangle }$con tipo de pedido${\displaystyle \beta }$, donde​${\displaystyle S'=\{x\in S\mid x\prec x_{\beta }\}}$( para algún valor fijo )${\displaystyle x_{\beta }\in S}$) es un subconjunto computable de${\displaystyle S}$si​​${\displaystyle \prec }$es computable.

El supremo de todos los ordinales computables se llama ordinal de Church-Kleene , el primer ordinal no recursivo, y se denota por${\displaystyle \omega _{1}^{\mathsf {CK}}}$. ^{[ 3 ]} El ordinal de Church-Kleene es un ordinal límite . Un ordinal es computable si y solo si es menor que${\displaystyle \omega _{1}^{\mathsf {CK}}}$. ^{[ 4 ]} Dado que solo hay una cantidad numerable de relaciones binarias computables, también hay solo una cantidad numerable de ordinales computables. Por lo tanto,${\displaystyle \omega _{1}^{\mathsf {CK}}}$es contable.

Los ordinales computables son exactamente los ordinales que tienen una notación ordinal en la notación de Kleene.${\displaystyle {\mathcal {O}}}$. ^{[ 5 ]}

• Jerarquía aritmética
• Ordinal contable grande
• Análisis ordinal
• Notación ordinal