Proving the class of countable ordinals is closed under ordinal exponentiation in ZF

Question

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

Answer 1

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!)

Answer 2

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 < \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.

Answer 3

Here is a terribly indirect of proving this.

Supoose $\alpha, \beta$ are countable ordinals. Therefore there is a function $f$ with domain $\omega$, such that the even integers are in bijection with $\alpha$ (using $f$) and the odd numbers with $\beta$. In $L[f]$ we have that:

1. $f$ is an element, so $\alpha$ $\beta$ are countable.
2. $\sf ZFC$ holds.
3. Ordinals and their arithmetic is the same as in $V$. It is easy to prove for addition, then use induction to get multiplication and exponentiation.

Therefore $\alpha^\beta$ is countable in $L[f]$, so the witness for countability lies there, and therefore in $V$.