Let $\leq\_1$ and $\leq\_2$ be recursive well-orderings of $\omega$ that have the same order type. Is there necessarily a recursive bijection $f$ such that $f(x)\leq\_1f(y)\iff x\leq\_2y$? If this does not hold in general, are there natural assumptions under which it does, such as if the well-orderings are primitive recursive?



Are two recursive well-orderings with the same order type recursively isomorphic?
The answer is no, not even for relations with order type $\omega$, and not even for primitive recursive relations.


To see this, let $\leq$ be the usual order relation on the natural numbers. And let $\unlhd$ be the order arising from the following computable procedure. We order the even numbers as usual. Next, we start
simulating all Turing machine programs on input $0$. At any stage,
if program $e$ halts at that stage, then take the next available odd number and
place it between $2e$ and $2(e+1)$. Eventually, all the odd numbers
will be placed between the halting Turing machine programs.


The relation $\unlhd$ is a computable relation, since for any two numbers, even or odd, we can
simply wait until they both appear in the construction, and then we'll know the order.
And the order type is $\omega$. But there can be no computable way
to tell if there will or will not eventually be an element between
$2e$ and $2(e+1)$, since then we could solve the halting problem. So there can be no computable function that forms the isomorphism between $\langle\mathbb{N},\leq\rangle$ and $\langle\mathbb{N},\unlhd\rangle$, since from such a function we could compute the immediate successor relation.


The relations $\leq$ and $\unlhd$ for this example are actually primitive recursive, since one can design programs that halt in a designated known amount of time, and so the procedure will use up odd numbers at a sufficient rate that in order to know whether $n\unlhd k$ or not, there will be a known primitive recursive bound on the length of time we will need to wait. So the example is actually primitive recursive.


The main thing that makes the argument work is that in general, one cannot compute the successor of an element with respect to a computable relation $\unlhd$. One can tell that a number is *not* a successor of another, but if you haven't yet found something between, it doesn't mean that you won't later on find an element between them.


But I believe that one can modify the argument even to allow a computable successor function, simply by coding things into the numbers representing limit ordinals. That is, the number $2e$ will represent a limit ordinal just in case $e$ never halts, but if it does halt, then we create an immediate predecessor for it, and otherwise continually add successors to whatever we have so far, making an order-type of $\omega^2$, and this also can be primitive recursive. 


