# Is there a canonical mapping between countable transfinite ordinals and $\omega$? What about recursive ordinals?

Consider $$\omega^2$$. We can build a simple bijection between the ordinal and $$\omega$$ similarly to how the bijection between $$\mathbb{Q}$$ and $$\mathbb{N}$$ can be built.

I was wondering if there is a way to get such a bijection between all countable transfinite ordinals and $$\omega$$. In the title I used the word canonical. Perhaps a way of defining this is: can we build a function $$F$$ which, given a transfinite ordinal $$\tau$$, returns a bijection $$f$$ with $$\omega$$, without using the axiom of choice?

I'm also satisfied if this is true only for recursive ordinals.

Thank you.

It is consistent with $$\mathsf{ZF}$$ that no such $$F$$ exists (this will happen in any model where $$\omega_1$$ is singular), so the axiom of choice is necessary here. This is basically the same as this answer of mine to an MSE question of yours from a while back.
On the other hand, we can definitely get such an $$F$$ for the computable (infinite) ordinals: for $$\alpha$$ computable let $$n_\alpha$$ be the smallest index of a Turing machine building a copy of $$\alpha$$ with domain $$\mathbb{N}$$, and then just use the (unique) isomorphism between $$\alpha$$ and this copy.
(More generally, here's a method that works in $$\mathsf{ZF}$$ alone for all ordinals $$<\omega_1^L$$ - which is vastly bigger than $$\omega_1^{CK}$$, and indeed is $$\mathsf{ZFC}$$-consistently equal to $$\omega_1$$. Given $$\alpha<\omega_1^L$$, let $$f$$ be the $$\le_L$$-least bijection between $$\alpha$$ and $$\omega$$. Here $$\le_L$$ is the canonical well-ordering of $$L$$; on reals, this is $$\Delta^1_2$$. Note that if no $$F$$ as in your question exists in $$V$$, then this process still works up to $$\omega_1^L$$ but we have $$\omega_1^L<\omega_1$$ in this case.)
• Just to check my understanding: the $F$ in your last-paragraph is well-defined, but not computable itself, correct?) Commented Oct 11, 2023 at 1:46
• @StevenStadnicki Yes on both counts. It's actually quite complicated: it is properly $\Sigma_1$ over $L_{\omega_1^{CK}}$, which puts it vastly above e.g. the halting problem. Commented Oct 11, 2023 at 2:16