1
$\begingroup$
  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!

  • 0
    Does ordinal belong to number theory?2011-05-27
  • 0
    Not usually (except, of course, for the finite ones...)2011-05-27

1 Answers 1

5

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.

  • 0
    @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).2011-05-27
  • 0
    @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?2011-05-27
  • 0
    @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.2011-05-27
  • 0
    @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$.2011-05-27
  • 0
    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.2011-05-27
  • 0
    @Arturo: What Chris says is true, if you already chose the bijections (or injections, and so on) then it is possible. Otherwise it is not. The problem is, as The Architect quotes Neo in *The Matrix: Reloaded*, choice. :-)2011-05-27
  • 0
    @Asaf: Yes, that is what I was trying to do when I said "countable well-ordered" (as opposed to just "countable"), but what I *really* had in mind was that they were well-ordered like $\omega$, not just any old countable well-order.2011-05-27
  • 0
    @Arturo: This is slightly stronger though. You require that there exists some sequence of bijections with $\omega$, which might not be extracted from the mere fact that each set has a bijection (not without the axiom of countable choice, anyway).2011-05-27