How far does Cantor-Bendixson rank counting let us build computable isomorphisms between ordinals?

Question

This is tangentially related to this old question of mine.

Say that a clean well-ordering is a computable well-ordering $\triangleleft$ of $\mathbb{N}$ such that the following additional data is computable as well:

• The $\triangleleft$-successor relation.

• The map sending the pair $(a,b)$ to the $a_\triangleleft$th element (in the sense of $\triangleleft$) which is a $b_\triangleleft$-limit-point (and outputting some fixed value, say $17$, if no such element exists).

Here "$x_\triangleleft$" is the ordertype of $\triangleleft$ up to but not including $x$, and the notion of "$b$-limit-point" is defined recursively as follows:

• A $0$-limit-point is just an element with no immediate predecessor.

• A $\theta+1$-limit-point is a $\theta$-limit-point which is itself a limit of $\theta$-limit-points.

• If $\lambda$ is a nonzero limit ordinal, a $\lambda$-limit-point is an element which is a $\theta$-limit-point for all $\theta<\lambda$.

It's a bit tedious but not hard to show that every computable ordinal does in fact have a clean copy. More interestingly, for "small" $\alpha$ any two clean well-orderings of ordertype $\alpha$ are computably isomorphic, i.e. the unique isomorphism between them is itself computable. I'm curious how far this phenomenon persists:

What is the smallest $\alpha$ such that there are non-computably-isomorphic clean copies of $\alpha$?

My current guess is $\epsilon_\omega$, but I don't see how to prove this.

Answer 1

The answer is indeed $ε_ω$. The $a$th $b$-limit point is $ω^b a$, or depending on the convention but immaterial for the computational power, $ω^{1+b} a$ or $ω^b (1+a)$ or $ω^{1+b} (1+a)$. The ability to compute this is equivalent to the ability to represent the ordinals in CNF (Cantor normal form) base $ω$ (see below). $ω$ is the smallest ordinal with computably non-isomorphic computable representations (if we have only ordering and not successor), which yields $ω$th fixpoint of $x→ω^x$ as the answer.

Two computably non-isomorphic representations of $ω$ are the standard one, and (for example) the set of $(i,j)$ such that the $i$th Turing machine halts on the empty tape in exactly $j$ steps, with $(i_1,j_1) < (i_2,j_2) ⇔ i_1 < i_2$. The set of such $(i,j)$ is computable, as required.

For ordinals past $ε_0$, CNF base $ω$ (aka CNF) is defined as usual, except that all fixpoints of $x→ω^x$ are treated as constants. Addition, multiplication, and exponentiation in CNF base $ω$ depends only on the ordering of these constants and not their exact values, so we can plug in constant names, and convert from computably non-isomorphic representations of $ω$ to the $ε_ω$ answer here.

For converting $x$ in a (what you call) clean well-ordering to CNF base $ω$, identify $b$ such that $x$ is $b$-limit point but not $b+1$-limit point, i.e. $x = ω^b a$ but $∃a' \, ω^{b+1} a' < x < ω^{b+1} (a'+1)$. Recursively proceed to parse $a$ and $b$, until reaching 0 and fixpoints of exponentiation base $ω$, which then yields (using ordinal arithmetic) CNF base $ω$ representation.