Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
If there were an explicit way that worked for any countable ordinal, then ZF would prove that $\omega_1$ is regular, which it does not. –  Chris Eagle May 27 '12 at 10:42
2  
If it were so easy, then there would be no non-recursive countable ordinals... –  Zhen Lin May 27 '12 at 12:52

1 Answer 1

up vote 3 down vote accepted

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.