Se puede implementar $\omega^{CK}_1$ $\omega^{CK}_1+1$ como un oráculo?

Question

Deje $\omega^{CK}_1$ denotar al menos de forma no recursiva ordinal. Supongamos que tenemos un desconocido buen orden de $\mathbb{N}$ de la clase de orden $\omega^{CK}_1+1$ como oracle. Es posible escribir un algoritmo que utiliza este oráculo, que implementa un buen orden de $\mathbb{N}$ de la clase de orden $\omega^{CK}_1$?

Answer 1

Colin dio una respuesta que muestra que para cualquier particular oracle codificación de una relación de orden tipo de $\omega_1^{ck}+1$, se puede producir un orden de tipo $\omega_1^{ck}$, simplemente moviendo la parte superior ordinal a la parte inferior. En los comentarios, objetaron que podría no ser posible para encontrar el elemento de la parte superior. Colin respondió que para cualquier particular oracle, existe un algoritmo concreto que sabe que es el elemento de la parte superior.

Así que permítanme tratar el caso general, donde queremos un algoritmo que no depende de la oracle, pero funciona con cualquier oracle codificación de una relación de orden tipo de $\omega_1^{ck}+1$.

Supongamos que tenemos un oráculo para una relación $\prec$ $\mathbb{N}$ con tipo de orden $\omega_1^{ck}+1$. Vamos a calcular una relación $\lhd$ con tipo de orden $\omega_1^{ck}$. La idea es que vamos a utilizar esencialmente el mismo orden como $\prec$, pero permitir como elementos sólo los nodos para los que también hemos encontrado un sucesor de un nodo. Este, en efecto, la tira de la parte superior del elemento de $\prec$. Y ya que usted quiere que su relación con el ser en $\mathbb{N}$, vamos a volver a índice de la relación, así como a utilizar todos $\mathbb{N}$. Concretamente, dado un oráculo para una relación $\prec$ $\mathbb{N}$ de tipo de orden $\omega_1^{ck}+1$, podemos definir una relación $\lhd$ $\mathbb{N}$ como sigue: si $k_n$ si $n^{th}$ elemento $\mathbb{N}$ encontrado para tener un sucesor con respecto a $\prec$, luego definimos $n\lhd m$ sólo en caso de $k_n\prec k_m$. Este es uniformemente computable en el oracle para $\prec$. Además, el orden $\langle\mathbb{N},\lhd\rangle$ es isomorfo a la colección de elementos de $\langle\mathbb{N},\prec\rangle$ tener sucesores, y este tiene el tipo de la orden, precisamente,$\omega_1^{ck}$, como se desee.

Lo que el argumento muestra, es que podemos calcular de manera uniforme una relación isomorfo a cortar el elemento maximal fuera de cualquier orden lineal la relación en $\mathbb{N}$ que tiene uno. Es decir, el algoritmo calcula una relación de orden tipo de $\alpha$ de manera uniforme desde cualquier oracle codificación de una relación de orden tipo de $\alpha+1$.

Answer 2

Podemos acaba de pegar el último elemento en el principio? Deje $<$ ser un pedido de $\mathbb{N}$ con tipo de orden $\alpha+1$ para algunos ordinal $\alpha$. Deje $n$ $<$- máximo del elemento. Para todos los $x,y\neq n$ deje $x<'y\iff x<y$, y también le $n<'x$. A continuación, $<'$ es de orden tipo de $\alpha$.