Return to Answer

I understand your question as asking: given two isomorphic computable well-orders, must there be a computable isomorphism?

The answer is no.

For a counterexample, let the first order be the natural numbers with the usual ordering $\langle\mathbb{N},<\rangle$, which has order type  $\omega$. Let the second order be constructed in the following computable manner. Put the Turing machines in order in type $\omega$ and for each machine $p$, create two points $a_p$ and $b_p$ and specify $a_p<b_p$, with each pair being ordered by the machine order. Now, begin simulating all programs, and whenever a new program halts, add a new point $c_p$ with $a_p<c_p<b_p$. This specifies a computable order with order type $\omega$, and we can arrange that these points exhaust $\mathbb{N}$. But there can be no computable isomorphism between this order and the first order, because if there were, we could computably determine whether or not $b_p$ was a successor of $a_p$ or not, and thereby computable solve the halting problem, which is impossible.

Conclusion: there are computable copies of $\omega$, with no computable order-isomorphism between them.

But perhaps you meant to ask whether one can always compute the isomorphism from an oracle for Tot, which is $\Pi_2$-complete and hence equivalent to an oracle for $0''$. In this case, the answer is also negative.

Let's start with the $0'$ case.

Theorem. There are two computable orders that are isomorphic, but the isomorphism is not computable from $0'$.

Proof. Let the first order be a natural copy of $\omega^2$, for which we can compute the function $(n,k)\mapsto\omega\cdot n+k$. Let the second order be as follows. Order the Turing machines $p$ in order type $\omega$. Create an interval in our new order associated with $p$. The interval will either be finite or infinite (but infinitely many of them will be infinite, and so the order overall will have type  $\omega^2$). We simulate all programs on input $0$, input $1$, input $2$ and so on. Every time a program halts on the next input, we add another point to its interval block. Thus, the total programs will lead to infinite intervals, but the non-total programs will lead to finite intervals, since they will be waiting for their next input to halt.

  There can be no $0'$-computable isomorphism from the first interval to the next, since from any such isomorphism, we could tell from $0'$ whether or not an interval was infinite or not, and thereby come to solve the $\Pi_2$-complete problem, which is not possible using only $0'$.  $\Box$

Let's now aim for the $0''$ argument.

Theorem. There are two isomorphic computable well-orders, which have no isomorphism computable from $0''$.

Proof. Consider any complete  $\Sigma_3$ relation $A(w)\iff \exists x\forall y\exists z\ R(w,x,y,z)$, where $R$ is $\Delta_0$. And consider the following computable order. We will have one interval for each $w$, with those intervals ordered according to $w$. Inside each such interval, associated with $w$, we will have a subinterval for each $x$, starting out with one point each. Inside each subinterval, we add a new point every time we find another $y$ that has a $z$ for which $R(w,x,y,z)$. That is, the subinterval associated with $(w,x)$ is allowed to grow every time it finds a little more evidence that it will work for all $y$. If there is an $x$ for which $\forall y\exists z$, then that one will grow infinitely often, and so the overall interval associated with $w$ will have order type strictly exceeding  $\omega$. But if there is no such $x$, then the overall interval associated with $w$ will have order type $\omega$. The order type overall of this order is bounded by $\omega^3$ and so we may fix a computable order of that type, for which the map $(n,m,k)\mapsto \omega^2\cdot n+\omega\cdot m+k$ is computable. But now there can be no isomorphism of this order with the order we constructed that is computable from $0''$, since using such an isomorphism we will be able to determine the size of the interval associated with $w$ and therefore we will be able to tell whether or not $\exists x\forall y\exists z\ R(w,x,y,z)$, which was supposed to be $\Sigma_3$-complete and therefore not computable from $0''$. $\Box$

I believe that this method can be pushed much further up the arithmetic hierarchy, but I would have to think more about it to say what the best result is.

Your question is about the oracle strength needed to compute an isomorphism between two isomorphic computable well-orders. In general, $0''$ is not necessarily enough to compute such an isomorphism, unless the order-types are sufficiently small, and the general phenomenon is that the strength needed to compute the isomorphisms rises with the length of the order types being considered.

Let's begin by pointing out what various oracles can compute about a computable well-order relation.

Theorem. Suppose that $\langle\mathbb{N},\lhd\rangle$ is a computable well-order relation.

1. Oracle $0'$ can compute the adjacency relation.
2. Oracle $0''$ can identify limit ordinal nodes.
3. Oracle $0'''$ can compute the "next limit" relation, i.e. where $a\lhd b$ and $b$ is a limit, with no limits between.
4. Oracle $0''''$ can identify limits-of-limits.
5. Oracle $0^{(5)}$ can compute the next-limit-of-limits.

Proof. Given $a\lhd b$, the oracle $0'$ can tell if we'll ever find $c$ such that $a\lhd c\lhd b$ and thereby know whether or not $a$ and $b$ are adjacent.

Node $b$ is a limit ordinal node, if every $a\lhd b$ does have such a $c$ between, and this is a $\Pi_2$ question to which $0''$ knows the answer. So oracle $0''$ can identify the limit ordinal nodes.

Similarly, $b$ is the next limit after $a$, if $a\lhd b$ and every $c$ between them has a predecessor, which is a $\Pi_3$ question that $0'''$ can answer. So $0'''$ can compute the next-limit relation.

A node $b$ is a limit-of-limits, if every smaller node has another limit node between. This is a $\pi_4$ assertion that $0''''$ can answer.

And so on. $\Box$

We can use this to find upper bounds on the strength needed to compute isomorphisms for various small order-types.

Corollary.

1. For any two computable well-orders of the same order-type less than $\omega^2$, oracle $0'$ can compute the isomorphism.
2. For any two computable well-orders of the same order-type less than $\omega^3$, oracle $0'''$ can compute the isomorphism.
3. For any two computable well-orders of the same order-type less than $\omega^4$, oracle $0^{(5)}$ can compute the isomorphism.

Proof. If the orders have type less than $\omega^2$, then they have only finitely many limit ordinal nodes, which can be hard-coded into the program. And then the rest of the isomorphism amounts to finding adjacencies, which can be computed from $0'$.

If the orders have type less than $\omega^3$, then they have at most finitely many limits-of-limits, which can be hard-coded into the program. And the rest of the isomorphism amounts to finding the next-limit and the corresponding adjacencies, which can be computed from $0'''$.

And so on. $\Box$

Meanwhile, we can show that for certain small order-types, one does in fact need strength.

Theorem. There are two computable order relations on $\mathbb{N}$ of order type $\omega$, with no computable isomorphism.

Proof. Let the first order be the natural numbers with the usual ordering $\langle\mathbb{N},<\rangle$, which has order type  $\omega$. Let the second order be constructed in the following computable manner. Put the Turing machines in order in type $\omega$ and for each machine $p$, create two points $a_p$ and $b_p$ and specify $a_p<b_p$. Now, begin simulating all programs, and whenever a new program halts, add a new point $c_p$ with $a_p<c_p<b_p$. This specifies a computable order with order type $\omega$. But there can be no computable isomorphism between this order and the first order, because if there were, we could computably determine whether or not $b_p$ was a successor of $a_p$ or not, and thereby computable solve the halting problem, which is impossible. $\Box$

Theorem. There are two computable relations with order-type $\omega^2$, having no $0'$-computable isomorphism relation.

Proof. Let the first order of type $\omega^2$ be a computable ordering for which the map $(n,k)\mapsto\omega\cdot n+k$ is computable. We build the second order by the following computable procedure. Order the Turing machines $p$ in order type $\omega$. Create an interval in our new order associated with each $p$. The interval will either be finite or infinite (but infinitely many of them will be infinite, and so the order overall will have type  $\omega^2$). We simulate all programs on input $0$, input $1$, input $2$ and so on. Every time a program halts on the next input, we add another point to its interval block. Thus, the total programs will lead to infinite intervals, but the non-total programs will lead to finite intervals, since they will be waiting for their next input to halt. There can be no $0'$-computable isomorphism from the first order to the second, since from any such isomorphism, we could tell whether or not an interval was infinite or not, and thereby come to solve the $\Pi_2$-complete problem of totality, which is not possible using only $0'$ as an oracle.  $\Box$

Theorem. There are two computable relations with order-type $\omega^3$, having no $0''$-computable isomorphism relation.

Proof. For the first order, we can use a standard ordinal denotation for which the function $(n,m,k)\mapsto \omega^2\cdot n+\omega\cdot m+k$ is computable. We build the second order by the following computable procedure. Consider any complete  $\Sigma_3$ relation $A(w)\iff \exists x\forall y\exists z\ R(w,x,y,z)$, where $R$ is $\Delta_0$. We may assume that infinitely many $w$ have such an $x$, that every $(w,x)$ has infinitely many $y$ with some $z$ for which $R(w,x,y,z)$, and that when there is an $x$ for $w$, then there are infinitely many such $x$. For each $(w,x)$, we create a node in the lexical order, and then we begin inspecting the various $y$ in turn, searching for a $z$ for which $R(w,x,y,z)$ (but waiting for each $y$ to finish before considering the next). Every time we find that $(w,x)$ admits the next $y$ having such a $z$, then we add another node to the interval associated with $(w,x)$. Thus, this $x$ will be an acceptable witness for $w$ if this interval grows infinitely often, and otherwise it will have only finitely many points. So $w$ will satisfy the property $\exists x\forall y\exists z\ R(w,x,y,z)$ if and only if the interval associated with $w$ (ranging over all possible $x$) has order type strictly exceeding  $\omega$, and otherwise it will have order type $\omega$. It follows from our assumptions on the relation $R$ that this relation has order type $\omega^3$. But finally, any isomorphism of this relation to the standard notations for ordinals below $\omega^3$ will tell us the length of the interval associated with $w$. So if $0''$ could compute the isomorphism, then it could solve the $\Sigma_3$ relation with which we began, and this is impossible. Since that relation was $\Sigma_3$-complete, there can be no such isomorphism computable from $0''$. $\Box$

I believe that these methods can be pushed harder, and one might expect to prove the optimal results.

I'll update more later with the $0''$ argument.

Let's now aim for the $0''$ argument.

Theorem. There are two isomorphic computable well-orders, which have no isomorphism computable from $0''$.

Proof. Consider any complete $\Sigma_3$ relation $A(w)\iff \exists x\forall y\exists z\ R(w,x,y,z)$, where $R$ is $\Delta_0$. And consider the following computable order. We will have one interval for each $w$, with those intervals ordered according to $w$. Inside each such interval, associated with $w$, we will have a subinterval for each $x$, starting out with one point each. Inside each subinterval, we add a new point every time we find another $y$ that has a $z$ for which $R(w,x,y,z)$. That is, the subinterval associated with $(w,x)$ is allowed to grow every time it finds a little more evidence that it will work for all $y$. If there is an $x$ for which $\forall y\exists z$, then that one will grow infinitely often, and so the overall interval associated with $w$ will have order type strictly exceeding $\omega$. But if there is no such $x$, then the overall interval associated with $w$ will have order type $\omega$. The order type overall of this order is bounded by $\omega^3$ and so we may fix a computable order of that type, for which the map $(n,m,k)\mapsto \omega^2\cdot n+\omega\cdot m+k$ is computable. But now there can be no isomorphism of this order with the order we constructed that is computable from $0''$, since using such an isomorphism we will be able to determine the size of the interval associated with $w$ and therefore we will be able to tell whether or not $\exists x\forall y\exists z\ R(w,x,y,z)$, which was supposed to be $\Sigma_3$-complete and therefore not computable from $0''$. $\Box$

I believe that this method can be pushed much further up the arithmetic hierarchy, but I would have to think more about it to say what the best result is.

I understand your question as asking: given two isomorphic computable well-orders, must there be a computable isomorphism?

The answer is no.

For a counterexample, let the first order be the natural numbers with the usual ordering $\langle\mathbb{N},<\rangle$, which has order type $\omega$. Let the second order be constructed in the following computable manner. Put the Turing machines in order in type $\omega$ and for each machine $p$, create two points $a_p$ and $b_p$ and specify $a_p<b_p$, with each pair being ordered by the machine order. Now, begin simulating all programs, and whenever a new program halts, add a new point $c_p$ with $a_p<c_p<b_p$. This specifies a computable order with order type $\omega$, and we can arrange that these points exhaust $\mathbb{N}$. But there can be no computable isomorphism between this order and the first order, because if there were, we could computably determine whether or not $b_p$ was a successor of $a_p$ or not, and thereby computable solve the halting problem, which is impossible.

Conclusion: there are computable copies of $\omega$, with no computable order-isomorphism between them.

I understand your question as asking: given two isomorphic computable well-orders, must there be a computable isomorphism?

The answer is no.

For a counterexample, let the first order be the natural numbers with the usual ordering $\langle\mathbb{N},<\rangle$, which has order type $\omega$. Let the second order be constructed in the following computable manner. Put the Turing machines in order in type $\omega$ and for each machine $p$, create two points $a_p$ and $b_p$ and specify $a_p<b_p$, with each pair being ordered by the machine order. Now, begin simulating all programs, and whenever a new program halts, add a new point $c_p$ with $a_p<c_p<b_p$. This specifies a computable order with order type $\omega$, and we can arrange that these points exhaust $\mathbb{N}$. But there can be no computable isomorphism between this order and the first order, because if there were, we could computably determine whether or not $b_p$ was a successor of $a_p$ or not, and thereby computable solve the halting problem, which is impossible.

Conclusion: there are computable copies of $\omega$, with no computable order-isomorphism between them.

But perhaps you meant to ask whether one can always compute the isomorphism from an oracle for Tot, which is $\Pi_2$-complete and hence equivalent to an oracle for $0''$. In this case, the answer is also negative.

Let's start with the $0'$ case.

Theorem. There are two computable orders that are isomorphic, but the isomorphism is not computable from $0'$.

Proof. Let the first order be a natural copy of $\omega^2$, for which we can compute the function $(n,k)\mapsto\omega\cdot n+k$. Let the second order be as follows. Order the Turing machines $p$ in order type $\omega$. Create an interval in our new order associated with $p$. The interval will either be finite or infinite (but infinitely many of them will be infinite, and so the order overall will have type $\omega^2$). We simulate all programs on input $0$, input $1$, input $2$ and so on. Every time a program halts on the next input, we add another point to its interval block. Thus, the total programs will lead to infinite intervals, but the non-total programs will lead to finite intervals, since they will be waiting for their next input to halt.

There can be no $0'$-computable isomorphism from the first interval to the next, since from any such isomorphism, we could tell from $0'$ whether or not an interval was infinite or not, and thereby come to solve the $\Pi_2$-complete problem, which is not possible using only $0'$. $\Box$

I'll update more later with the $0''$ argument.