Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 21 / 4 / i / Solution

Yes. There is a computable isomorphism, obtained by an effective back-and-forth construction. Decidability of the two orders makes the usual existence argument into an algorithm.

Maintain a finite order-preserving partial isomorphism of structures $f_s$ from $(\mathbb{N},{<}_A)$ to $(\mathbb{N},{<}_B)$, starting with the empty map. At a forth step, take the least ordinary natural number $a$ outside its domain. Look at the finitely many mapped elements below and above $a$ in ${<}_A$. Their images impose an open interval in ${<}_B$: it lies above all the lower images and below all the upper images, with a missing bound interpreted as an unbounded side.

This interval contains a fresh element. If both bounds exist they are ordered correctly by the induction hypothesis; density supplies an element strictly between them. If there is just one bound, the absence of endpoints supplies an element beyond it; if there are no bounds, choose any element. Density and the absence of endpoints moreover give infinitely many points in every such open interval, so finitely many already used images can always be avoided.

Enumerate $b=0,1,2,\dots$ in the ordinary presentation order, test whether $b$ is unused and satisfies every required ${<}_B$ inequality, and choose the first successful candidate. All tests are decidable, and the existence argument proves termination. Extend $f_s$ by $a\mapsto b$.

At a back step, take the least natural number outside the range, interchange the roles of $A$ and $B$, and carry out exactly the same search for a fresh preimage. Alternate forth and back steps. Every stage is an effective terminating finite computation, and every stage remains an order-preserving partial isomorphism of structures.

Let $f={\bigcup }_s{f}_s$. The least-unused scheduling puts every element of $A$ into the domain and every element of $B$ into the range. For example, after $n+1$ forth steps, all ordinary presentation numbers at most $n$ have been included, since each step removes the least missing one. Thus $f$ is a bijection preserving and reflecting the orders. To compute $f(n)$, simulate the construction until $n$ appears in its domain; this terminates. The corresponding range search computes its inverse. HenceThe searches use the decidable presentations, rather than a possibly ineffective choice of points in an abstract dense linear order without endpoints.