Is there a general explicit way to construct bijections between countable ordinals?

Question

Is there a general - and possibly easy! - explicit way to "create" bijective functions between countable ordinals? I mean for example a bijection between $\omega$ and $\omega+\omega$, or a bijection between $\omega k$ and $\epsilon_0$ etc. Thanks.

Answer 1

As Chris Eagle said in the comment, we cannot do that explicitly.

The reason is that if we have a countable sequence of $(A_i,f_i)$ where $f_i$ is a bijection between $A_i$ and $\omega$ then the union of $\bigcup_{i=1}^\infty A_i$ is countable.

It is also consistent with ZF that $\omega_1$ is a countable union of countable ordinals, but it does not mean that $\omega_1$ is countable. It is never countable.

In fact even assuming that $\omega_1$ is not a countable union of countable ordinals is not enough to generate these "canonical" bijections, as Solovay's model tells us. If we could, then we could define $\aleph_1$ many real numbers, which is impossible without pretty much the assumption that $\aleph_1$ many real numbers exist.

For explicit bijection between $\omega$ and "small" countable ordinals, for example $\omega$ with $\omega^2+\omega+5$:

• Partition $\omega$ into three parts, two infinite and one with five elements.

• Take a bijection of the first part with $\omega^2$, a bijection of the second part with $\omega$ and the last part with $5$.

  This can be done simply by composing the needed bijections, and if the partitions are made of sets simple enough then this can be done by a relatively simple formula.

• Combine the three parts in the proper ordering: The first part is smaller than the other two, and the finite part is larger than the infinite one.

Note that $\epsilon_0$ is a bit too large for this kind of manipulation, as it relies on a Cantor normal form being "simple". However you can probably stretch this method a bit further by considering infinite partitions, I doubt a nice formula can be expected in that case, though.

---

To Read More:

1. Sequence of surjections imply choice