Give a bijection from $\Bbb N\to\omega^{\omega}$ based upon counting consecutive similar digits of binary strings

Question

Question

Give a bijection from $\omega^{\omega}\to\Bbb N$ based upon counting consecutive similar digits of binary strings: There is a near-bijection given in attempt 1 below; the aim is to fix it to give a bijection with near order-isomorphism to the original function.

$\omega^{\omega}$ is the set of ordinals expressible in Cantor normal form as:

$$\sum_{i=k}^0\omega^i\cdot a_i:a_i\in\Bbb N_{\geq0}$$

Step 1

A near-bijection is to let $a_i$ count the number of consecutive ones and twos in an integer's binary representation:

$27=11011_2\mapsto\omega^2\cdot2+\omega+2$

But since there are no zero-length sequences of ones or twos in binary representations, this is unable to represent any ordinal having a finitely long sequence of consecutive zero coefficients. For example $\omega^2+2$ has no binary string representation.

Step 2

One can then reduce each coefficient by $1$ like this:

$27=11011_2\mapsto\omega^2+1$

This now represents zero coefficients, but it fails to inject because it gives the same ordinal $0$ for all the following numbers:

$S_n=1,2,5,10,21,42,85,\ldots$.

Attempt

The task is to fix this approach with a near order-isomorphism. I'm not sure how to proceed but I have a rough hunch we might be able to add or multiply a number (which may not truly be an ordinal) of the following form or similar:

$$\beta=\sum_{i=0}^\infty\omega^{2i+k}\cdot$$

Also, perhaps we can count up the number of $S_n$ having a representation shorter than any given integer and increase the ordinal by that many. But I'm unclear precisely how to complete the job.

Answer 1

I don't know why you insist on talking about ordinals when Noah told you it is nothing more than an unnecessary distraction, since a bijection from naturals to finite sequences of naturals will do. Here is one bijection based on the binary representation and blocks of consecutive similar digits:

• Map $0$ to $⟨⟩$.
• For each positive natural $n$, write down the binary representation of $n$, and split it into blocks each of which starts with a "$1$" and has only "$0$"s after that, and count the number of zeroes in each block, and map $n$ to that sequence of counts. For example, $1101_2$ is mapped to $⟨0,1,0⟩$.

Note that every positive natural is mapped to a unique non-empty tuple, and that every non-empty tuple is mapped to from some positive natural.

To biject from finite sequences to finite sequences where the first term (if any) is non-zero, simply add one to that first term.

Alternatively (as said in comments), to biject from naturals to $ω^ω$, pad the binary representation with infinitely many zeroes to its left, and map it to the finite sum $\sum_{k=0}^∞ ω^k·a_k$ where $a_k$ is the number of ones after the $(k+1)$-th rightmost zero but before the $k$-th rightmost zero (or the rightmost end if $k=0$). This also handles $0$ correctly. Obviously, you can also compute the mapping without doing the padding.