1. I was wondering how a bijection between two ordinal numbers with the same cardinality is constructed generally? if there is no general solution, some examples please?
  2. Since any well-ordered set is order-isomorphic to a unique ordinal, is it correct that any bijection between two ordinals with the same cardinality cannot be an order-isomorphism?

Thanks and regards!

  • $\begingroup$ Does ordinal belong to number theory? $\endgroup$ – Tim May 27 '11 at 5:15
  • $\begingroup$ Not usually (except, of course, for the finite ones...) $\endgroup$ – Arturo Magidin May 27 '11 at 5:22

For (2), you need to exclude the case where the two ordinals are equal; but if $\alpha\neq \beta$ are ordinals, then no bijection between them can be an order isomorphism.

For (1), there's lots of ways. For instance, there are uncountably many bijections of $\omega+\omega$ with $\omega$: for each infinite subset $A$ of $\omega$ with infinite complement (there are $2^{\aleph_0}$ of them), both $A$ and $\omega\setminus A$ are well-ordered by the induced order, each of them isomorphic to $\omega$. So map $\omega+\omega$ to $\omega$ by mapping the first copy to $A$ and the second copy to $\omega\setminus A$. You can biject $\omega\times\omega$ with $\omega$ by using the zig-zag mapping that one often uses to show that there is a surjection from $\mathbb{Q}$ to $\mathbb{N}$ (or that one uses to show that a countable union of copies of $\mathbb{N}$ is countable). Etc.

  • $\begingroup$ @Arturo: the countable union of countable sets needs not be countable. :-) In fact there is a model that the real numbers are a countable union of countable sets, and another (much more complicated) by Gitik in which all limit ordinals are of cofinality $\omega$ (this assumes some very strong axioms in addition though). $\endgroup$ – Asaf Karagila May 27 '11 at 4:51
  • $\begingroup$ @Asaf: I was trying to get around that by saying "well-ordered" (as opposed to just "countable") so that you don't need to pick a bijection, but I really should have said "copies of $\omega$"... Unless I'm mistaken, to prove that a countable union of copies of $\omega$ is countable, you don't need Choice. Right? $\endgroup$ – Arturo Magidin May 27 '11 at 5:04
  • $\begingroup$ @Arturo: I'm not sure anymore... (I've been working in one of the aforementioned models recently and all my intuition is off. You just start to assume that you can't really do anything ;-)) I'll get back to you with an answer later today. $\endgroup$ – Asaf Karagila May 27 '11 at 5:15
  • $\begingroup$ @Asaf: Fair enough: but, $\mathbb{N}\times\mathbb{N}$ is countable. If you have a countable set of copies of $\mathbb{N}$, say $\{\mathbb{N}\times\{i\}\}_{i\in I}$, then pick an injection from $I$ to $\mathbb{N}$ (no choice needed, since the set of such injections is nonempty), and then embed the disjoint union to $\mathbb{N}\times\mathbb{N}$ by mapping $x$ from the $i$th copy to $(x,f(i))$. You can embed the union to the disjoint union also using $f$. $\endgroup$ – Arturo Magidin May 27 '11 at 5:21
  • $\begingroup$ One way I've seen of putting this is that you can prove without choice that a countable union of counted sets is countable, where a counted set is a set equipped with an injection into $\mathbb{N}$. All you need choice for is to show you can turn your countably many countable sets into countably many counted sets, by simultaneously choosing an injection for each one. $\endgroup$ – Chris Eagle May 27 '11 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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