Countable ordinal

Question

I haven't done ordinal algebra for a long time and I can't remember how to prove that $\omega + \omega$ is a countable ordinal. Precisely what is the bijection between $\omega$ and $\omega \cdot 2$ ? Any hint would be much appreciated.

Answer 1

If I write $\omega= \{0,1,2,3,…\}$ and $\omega \cdot 2 = \{0,1,2,3,…,\omega, \omega+1,\omega+2,…\}$, then $$f : \omega \to \omega \cdot 2$$ defined by $f(n) = n/2$ if $n$ is even and $f(n) = \omega + \frac{n-1}{2}$ if $n$ is odd provides such a bijection.

Answer 2

Another way to prove this is the following:

Let $X_0 = \omega$ and for each $n < \omega$ let $X_{n+1} = X_n \cup \{\omega+n\}$. (In fact $X_{n+1} = \{0,1 \ldots, \omega, \omega+1, \ldots, \omega+n\} = \omega+n+1$.)

By a trivial induction on $n < \omega$, every $X_n$ is countable and $\omega + \omega = \bigcup_{n < \omega} X_n$ is a countable union of countable sets and therefore itself countable. (It may seem as if this relies on countable choice, but it actually doesn't.)

---

edit: Let me briefly address why this proof doesn't rely on countable choice:

In the absence of countable choice there might be countable sets $X_n$ for $n < \omega$ such that $\bigcup_{n < \omega} X_n$ is uncountable. In fact, there might be countably many, countable subsets of reals whose union is all of $\mathbb R$. So why then doesn't the proof above need some form of choice?

The reason for this is, that we can define a sequence $(f_n \mid n < \omega)$ of bijections $f_n \colon \omega \to X_n$ (let me remind you that in our case $X_n = \omega +n $). So not only does such an $f_n$ exist for each individual $n < \omega$, but the actual sequence exists. We may then define a surjection $g \colon \omega \to \bigcup_{n < \omega} X_n$ by $g(2^{n+1}\cdot3^{m+1}) = f_n(m)$ and $g(x) = 0$ if $x$ is not of the form $2^{n+1}\cdot 3^{m+1}$, witnessing that $\bigcup_{n < \omega} X_n$ is countable.

At this point, I should prove that such a sequence $(f_n \mid n < \omega)$ exists even in the absence of choice. Luckily, the recursion theorem doesn't rely on choice and therefore there is a function $G \colon \omega \to V$ such that $G(0) = \operatorname{id} \restriction \omega$ and $G(n+1) = (0,\omega + n) \cup \{ (k+1, G(n)(k)) \mid k < \omega \}$. In simpler words: $G(0)$ is just $\operatorname{id} \colon \omega \to \omega$ and given $G(n)$ we let $G(n+1)$ map $0$ to the unique element $\omega+n \in X_{n+1} \setminus X_n$ and then map every $0 < k < \omega$ to $G(n)(k-1)$. Now $G = (f_n \mid n < \omega)$ is as desired.