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.
Is there a general explicit way to construct bijections between countable ordinals?
-
2If it were so easy, then there would be no non-recursive countable ordinals... – 2012-05-27
1 Answers
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: