Skip to main content
1 of 5
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

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$. 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.

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

Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k