Proving the class of countable ordinals is closed under ordinal exponentiation in ZF I managed to prove that given the axiom of choice, the class (or is it a set?) of countable ordinals is closed under exponentiation, since the axiom of choice implies that the countable union of countable sets is countable (although this is not true in ZF).  

I managed to prove that $\omega^\omega$ is countable in ZF by comparing it to the set of polynomials in $\omega$ with natural coefficients, but am struggling to extend it to more general ordinals. 

Any help would be most welcome. Thank you in advance
You're right that in ZF, the countable union of countable sets need not be countable. However, the countable union of counted sets is always countable: that is, if I have countably many sets $A_i$, and a set of injections $f_i: A_i\rightarrow \omega$, then $\bigcup A_i$ is indeed countable. The weird examples come when I have (in some model of ZF) a countable collection $\{A_i\}$ of countable sets, but I don't have a set of injections of the $A_i$s into $\omega$.

So the goal is to make $\alpha^\beta$ explicitly counted. Specifically:


  Can you find an injection from $\alpha^\beta$ to $\omega$, given injections $f: \alpha\rightarrow\omega$ and $g:\beta\rightarrow\omega$?


HINT: it will be easier to do this if you work with the "explicit" description of ordinal exponentiation - that $\alpha^\beta$ is the set of all maps $\beta\rightarrow\alpha$ which are nonzero at only finitely many values, ordered lexicographically . . .

Note that the "given $f$ and $g$" can't be done away with: it is consistent with ZF that there is no map $H$ from $\{$countable ordinals$\}$ such that $H(\alpha)$ is an injection from $\alpha$ into $\omega$, that is, there's no "canonical" way to count each countable ordinal. (Indeed, such an $H$ existing implies that the union of countably many countable ordinals is countable - that is, that $\omega_1$ is regular!)
The following argument is overkill and probably not helpful to you. However, I thought I'd add it anyways - just for the heck of it.

It's easy to verify that ordinal arithmetic (i.e. addition, multiplication, exponentiation) is absolute between transitive models of $\operatorname{ZF}^{-}$. In particular, for any $\alpha, \beta &lt; \omega_{1}$, we may calculate $\alpha^\beta$ in $L_{\omega_1}$ and obtain the correct value. Since $L_{\omega_1} \cap \operatorname{On}= \omega_1$, this implies that $\alpha^\beta$ is countable.