¿Son isomorfos los pozos de la misma longitud recursiva?

Question

Si la longitud ordinal de $A$ y $B$ es el mismo ordinal recursivo, ¿se deduce que existe una correspondencia recursiva uno-uno que preserva el orden entre $A$ y $B$ ?

Answer 1

Considere un sistema de programación aceptable $(\phi_n)$ .

Considere $f$ de $\mathbb N$ a $\mathbb N$ tal que :

1. si $\phi_n(n)$ se detiene entonces $f(n)=2\times\left|\{i\le n\;|\;\phi_i(i)\mbox{ halts}\}\right|$
2. si $\phi_n(n)$ nunca se detiene entonces $f(n)=1+2\times\left|\{i\le n\;|\;\phi_i(i)\mbox{ never halts}\}\right|$

Por lo tanto, $f$ es una biyección.

Dejemos que $A$ sea $\mathbb N$ con el orden habitual, por lo que $A$ es un conjunto de longitud de orden $\omega$ ( $\omega$ es recursivo).

Dejemos que $B$ sea $\mathbb N$ con el pedido especial $x\le_B y$ si $f(x)\le_A f(y)$ Así que $B$ es también un conjunto de longitud de orden $\omega$ .

Pero $f$ es la biyección que preserva el orden de $B$ a $A$ y $f$ no es recursivo.