Mapping between Notations

Question

$\DeclareMathOperator{\address}{address}$ As in my other question, it is assumed that the (total) function describing a given notation is denoted as $\address:p \rightarrow \Bbb{N}$ and assumed to be bijective.

Suppose we are given two notations $N_1$ and $N_2$ for some $p \in \omega_{CK}$ (Church-Kleene). Denote the mapping from $N_1$ to $N_2$ as $P_{12}:\Bbb{N} \rightarrow \Bbb{N}$.

If we wanted to be more formal, we could say that consider the two functions $\address1:p\rightarrow \Bbb{N}$ and $\address2:p\rightarrow \Bbb{N}$ corresponding to $N_1$ and $N_2$ respectively. Then $P_{12}$ is defined by:

$$P_{12}(\address1(x))=\address2(x) \quad \text{for all} \quad x < p$$

Now assume that the less-than relations corresponding to $N_1$ and $N_2$ are computable. My question simply is the following: Is the function $P_{12}$ always Total-computable? That is, computable using an oracle-program that has access to the set representing "indexes of total recursive functions".

If no, then what would be the example for it (also generally, what would be the suitable upper-bound in that case). If yes, then can someone give a reference where a complete or partial proof(if there is one) for a reasonable upper-bound(or lack of it) is provided.

P.S. I posted this same question on Math.SE. After no replies/comments since few days after posting it, I am posting it here. Hopefully that isn't a problem.

Answer 1

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.

Answer 2

The following is a confirmation of Andreas Blass's conjecture in his comment to Joel Hamkins's answer above, i.e. that for for each $\gamma<\omega_1^{\mathrm{ck}}$, there are computable wellorders $R,S$ of of $\omega$, having the same ordertype, but such that the isomorphism between $R$ and $S$ is not in $L_\gamma$. (As he remarked there, certainly the isomorphism is in $L_{\omega_1^{\mathrm{ck}}}$. See Blass's comment of Aug 5, 2017 at 21:01.) The topic is related to this question.

To see this, fix $\alpha<\omega_1^{\mathrm{ck}}$ with $\alpha>\omega$. Let $\beta<\alpha$. We will observe that there are two computable wellorders of $\omega$ of the same ordertype, such that the isomorphism between them is not in $L_\beta$; this suffices. So, recall that since $\alpha<\omega_1^{\mathrm{ck}}$, $L_\alpha$ is pointwise definable, so is determined by its own theory. Moreover, there is a $\Sigma_1$ formula $\psi$ of one free variable such that $L_\alpha\models$"$\forall n<\omega\ [\psi(n)]$", but there is no $\alpha'<\alpha$ such that $L_{\alpha'}\models$"$\forall n<\omega\ [\psi(n)]$". For a formula $\varphi$ of the language of set theory, let $T_\varphi\subseteq {^{<\omega}\omega}$ be the usual tree searching for a countable model $M$ for the language of set theory, coded as a subset of $\omega$, such that $M$ has wellfounded $\omega$, and $M\models\ \varphi$ + "$V=L$" + "$\forall n<\omega\ [\psi(n)]$" + "There is no ordinal $\alpha'$ such that $L_{\alpha'}\models\forall n<\omega\ [\psi(n)]$". Let $T^*_\varphi$ be the linear ordering of $\omega$ consisting of the elements in ${^{<\omega}\omega}\setminus T_\varphi$ forming an initial segment of $T^*_\varphi$ of ordertype $\omega$, in a canonical computable form, followed by the Kleene-Brouwer ordering of $T_\varphi$. So $T^*_\varphi$ is a linear order, with an initial segment of ordertype $\omega$.

Then iff $L_\alpha\models\varphi$ iff $T_\varphi$ is illfounded iff $T^*_\varphi$ is illfounded iff $T^*_{\varphi}$ is not a wellorder (use Ville's Lemma). So exactly one of $T^*_\varphi$ and $T^*_{\neg\varphi}$ is wellfounded.

Note that for each $\varphi$, there is an isomorphism $\pi\in L_{\omega_1^{\mathrm{ck}}}$ from some initial segment of $T^*_{\varphi}$ to some initial segment of $T^*_{\neg\varphi}$, which is maximal, in that either

(i) $\mathrm{dom}(\pi)=\omega$, or

(ii) $\mathrm{range}(\pi)=\omega$, or

(iii) $\mathrm{dom}(\pi)\neq\omega\neq\mathrm{range}(\pi)$ and either (a) there is a $T^*_\varphi$-least $x\in\omega\setminus\mathrm{dom}(\pi)$ but no $T^*_{\neg\varphi}$-least $x\in\omega\setminus\mathrm{range}(\pi)$, or (b) vice versa.

Moreover, $L_\alpha\models\neg\varphi$ iff $T^*_\varphi$ is wellfounded iff (i) or (iii)(a) holds, and $L_\alpha\models\varphi$ iff $T^*_{\neg\varphi}$ is wellfounded iff (ii) or (iii)(b) holds.

Let $T$ be the first order theory of $L_\alpha$ (in no parameters). Then $T\notin L_\alpha$. But on the other hand, if we can compute which option of (i), (ii), (iii)(a) and (iii)(b) holds for each $\varphi$, then we can compute $T$. So if there is $\beta<\alpha$ such that all proper segments $\pi'$ of the isomorphisms $\pi$ witnessing the options above are in $L_\beta$, then we can define $T$ over $L_\beta$, so $T\in L_\alpha$, a contradiciton. So the proper segments $\pi'$ can only appear cofinally in $L_\alpha$, if in $L_\alpha$ at all. Each of these proper segments $\pi'$ corresponds to an isormoprhism between some computable wellorders of $\omega$ having the same ordertype, so we are done.