Mapping Between Notations - 2

Question

As the name implies, this question is somewhat similar in spirit to the previous question I asked with same title. This question is also about existence (or lack thereof) of certain possibilities concerning two different recursive well-orders with same order-type.

In my original question (Mapping between Notations) I mentioned a result (in the comments below the original question) that is necessary to pose this particular question. I will use similar terminology as in the original question.

The idea behind this question goes as follows. Suppose we have two different well-orders of $\mathbb{N}$ with same order-type. Define the isomorphism function from the first well-order to second one as $P_{\,12}:\mathbb{N} \rightarrow \mathbb{N}$ (and $P_{\,21}:\mathbb{N} \rightarrow \mathbb{N}$ for the analogous function in the opposite direction).

Suppose that both $P_{\,12}$ is non-recursive but is $0'$computable. Then one of the following possibilities can hold:

1. $P_{\,12}$ is recursively bounded and $P_{\,21}$ is $0'$computably bounded (but not recrusively bounded)
2. $P_{\,12}$ is $0'$computably bounded (but not recrusively bounded) and $P_{\,21}$ is recursively bounded
3. $P_{\,12}$ is $0'$computably bounded (but not recrusively bounded) and $P_{\,21}$ is $0'$computably bounded (but not recrusively bounded)

The possibility of $P_{\,12}$ and $P_{\,21}$ being both recursively bounded is ruled out because it would contradict $P_{\,12}$ being non-recursive.

In a similar manner, suppose that $P_{\,12}$ is not $0'$ computably, but is $0''$ computable. Then only one of the following possibilities can hold:

1. $P_{\,12}$ is recursively bounded and $P_{\,21}$ is $0''$computably bounded (but not $0'$ computably bounded)
2. $P_{\,12}$ is $0''$computably bounded (but not $0'$ computably bounded) and $P_{\,21}$ is recursively bounded
3. $P_{\,12}$ is $0'$ computably bounded (but not recursively bounded) and $P_{\,21}$ is $0''$computably bounded (but not $0'$ computably bounded)
4. $P_{\,12}$ is $0''$computably bounded (but not $0'$ computably bounded) and $P_{\,21}$ is $0'$ computably bounded (but not recursively bounded)
5. $P_{\,12}$ is $0''$computably bounded (but not $0'$ computably bounded) and $P_{\,21}$ is $0''$computably bounded (but not $0'$ computably bounded)

For example, here the possibility of both $P_{\,12}$ and $P_{\,21}$ being $0'$ computably bounded is ruled out on the simple ground that a very simple generalisation of the result I have mentioned below shows that this would imply $P_{\,12}$ being $0'$ computable.

I guess there is a somewhat general pattern that emerges from this. So I guess the general question is that (for some natural number $n$) when $P_{\,12}$ is $0^{(n)}$ computable but not $0^{(n-1)}$ computable, then which of the possibilities (amongst the $2n+1$) can or can't occur?

P.S. Adding link to the argument for the mentioned result (and justifying the exclusion of possibilities ignored in the question): (i) Main Argument (ii) Program Implementation

The functions that are used in program implementation: (iii) Interface/List of Elementary Functions (iv) Implementation

It is link (i) that is really relevant here (and to some extent (ii) possibly). I am posting links (iii) and (iv) just for the case if someone might be interested in following (ii) .... so the interface and/or implementation of specific functions can be looked up in a transparent way if necessary.

I wrote (i) and (ii) about nine months ago and (iii) and (iv) about little over one and a half years ago. So the writing might not be without mistakes (though at that time I did re-check (i) a couple of times .... especially for more substantial argument-breaking mistakes). Also there are occasions of slightly odd terminology, which I didn't define. Clarifying it here: (a) $PS$ means $\omega_{CK}$ (b) I have written $N_1/p$ and $N_2/p$ for "recursive numberings". What that simply means is two different recursive well-orders for $\mathbb{N}$ with order-type $p+1$. Only condition is that the number $0$ must be assigned to $p$ (that is $address1(p)=0$ and $address2(p)=0$).

Edit: Updated document(i) by adding explanation of the (naive) program/algorithm, and also correcting a few mistakes. Main question remains unchanged.

Answer 1

First, a pedantic note: the impossibility of both isomorphisms being computably bounded while one (equivalently, both) is noncomputable is not actually true as stated: let $<$ be the usual order on $\mathbb{N}$, and $\triangleleft$ be the order on $\mathbb{N}$ given by swapping $2i$ and $2i+1$ iff $i\in \emptyset'$ and making no other changes. Then $(\mathbb{N},<)\cong(\mathbb{N},\triangleleft)$ and the isomorphisms in both directions are computably bounded (indeed, bounded by $x\mapsto x+1$), but there is no computable isomorphism between the two.

We can avoid this if we demand that both well-orderings be computable. The key is the following:

$(*)\quad$ Suppose $\mathcal{A},\mathcal{B}$ are computable structures with domain $\mathbb{N}$ and $f:\mathcal{A}\rightarrow\mathcal{B}$ and $g:\mathcal{B}\rightarrow\mathcal{A}$ are isomorphisms which are each computably bounded by $h_0$ and $h_1$, respectively. Then there is an infinite computable finitely-branching tree $T_{\mathcal{A},\mathcal{B},h_0,h_1}$ such that $(i)$ the "width function" (sending $i$ to the number of nodes at level $i$) is computable and $(ii)$ every path through $T_{\mathcal{A},\mathcal{B},h_0,h_1}$ "is" an isomorphism between $\mathcal{A}$ and $\mathcal{B}$.

By the Low Basis Theorem, we get low isomorphisms. If $\mathcal{A},\mathcal{B}$ are well-orderings, we do even better: since two well-orderings have at most one isomorphism between them the tree $T_{\mathcal{A},\mathcal{B},h_0,h_1}$ has a unique path, and since for any computable finitely-branching tree with a computable width function and a unique path that unique path is computable we get a computable isomorphism.

---

Now to your question (with the added assumption of computability). I'll show that at "level one," all three possibilities can occur - even for well-orderings of type $\omega$.

First, note that $P_{12}\equiv_TP_{21}$ since any bijection $\mathbb{N}\rightarrow\mathbb{N}$ is Turing-equivalent to its inverse. So possibilities $(1)$ and $(2)$ are equivalent.

Next, note that any two computable copies of the usual order on $\mathbb{N}$ are $0'$-computably isomorphic.

Fix a computable injective enumeration $(k_i)_{i\in\omega}$ of $0'$, and consider the ordering $\triangleleft$ on $\omega$ where:

• The even numbers are in their usual order.

• Each odd number $2i+1$ is put between $2k_i$ and $2k_i+2$.

The isomorphism from $\triangleleft$ to $<$ is computably bounded, but a computable bound on the isomorphism from $<$ to $\triangleleft$ would let us compute $0'$.

Possibility (3) is messier, but similar - one idea is the following:

• Both $\triangleleft_1$ and $\triangleleft_2$ have the even numbers in their usual order.

• We use the odd numbers as "interval stuffers" as before, but this time as we see things enter $0'$ we enlarge alternate intervals in each well-order: namely, when we see $i$ enter $0'$ we make $[4i, 4i+2]$ bigger in $\triangleleft_1$ and make $[4i+2, 4i+4]$ bigger in $\triangleleft_2$.

---

Now what about higher levels?

Well, one surprising observation is that the complexity of isomorphisms is a bit weird:

• There are two computable copies of $\omega^2$ such that the unique isomorphism between them has degree $0'''$. (This is a bit messy but not too hard.)

• However, if $\alpha<\omega^2$, then for any two computable copies of $\alpha$ the unique isomorphism has degree $\le_T 0'$. The key is that we can non-uniformly tell what the finitely many limit points are; then, given $n$, we first (computably) ask which of the finitely many "blocks" between the limit points $n$ sits in, and then ($0'$-computably) find its position within that block.

So $0''$ gets "skipped" in an odd way. This means that an aspect of the problem that was trivial in the level-one case ceases being trivial higher up. That said, I suspect the answer is ultimately the same by doing some more simple (but tedious) coding.

• This weird skipping phenomenon, incidentally, goes away to some extent when we introduce some more uniformity: it takes exactly $0''$ to uniformly compute isomorphisms between computable copies of $\omega\cdot 2$, in the sense that if $F$ is a partial function such that whenever $e_0,e_1$ are indices for computable copies of $\omega\cdot 2$ we have that $F(e_0,e_1,-)$ is the unique isomorphism between them, then $F\ge_T0''$ (where we identify $F$ with its graph).