A proof that $\omega^\alpha$ is countable for every countable ordinal $\alpha$?

Question

I am working on a problem that requires this statement but I am struggling to prove it, I have tried transfinite induction but I am stuck. Any help?

Answer 1

As you noted, there are two cases; one is when $\alpha$ is a successor ordinal, say $\alpha=\beta+1$, and one is when $\alpha$ is a limit ordinal. In the former case, you have $\omega^\alpha=\omega\cdot\omega^\beta$ and you should be able to 'compose' the map $\omega^\beta\mapsto\omega$ that you have with a map $\omega\times\omega\mapsto\omega$ to get the requisite mapping.

In the limit case, because $\alpha$ is a countable ordinal, you have an $\omega$-sequence for it, $\alpha=\bigcup_{n\in\omega}\alpha_n$. In this case $\omega^\alpha=\bigcup_{n\in\omega}\omega^{\alpha_n}$; can you see how to combine your mappings $\omega^{\alpha_n}\mapsto\omega$ (which you 'know' you have, by induction) to get the requisite $\omega^\alpha\mapsto\omega$? (Hint: there are $\omega$ of them. More specifically, you can think of the rank of any element $a$ of $\alpha$, which is to say the smallest $n$ for which $a\in\alpha_n$. Consider how to find an $m\in\omega$ for each $a\in \omega^\alpha$ by looking at the pair $\langle n,f_n(a)\rangle$, where $n$ is the rank of $a$ and $f_n$ is the map from $\omega^{\alpha_n}\mapsto\omega$.)