How to show countability of $\omega^\omega$ or $\epsilon_0$ in ZF?

Question

I know that with choice, the countable union of countable sets is countable, making $\omega^\omega$ and $\epsilon_0$ both countable. Can we show this without choice? E.g. in the case that $\omega_1$ is a countable union of countable sets.

Answer 1

For $\omega^\omega$ this is easy. You can note that this is just the order type of $\Bbb N[x]$, the polynomials with natural numbers coefficients, ordered lexicographically by length.

In general, if $\langle A_n\mid n\in\Bbb N\rangle$ is a sequence of countable sets such that there is a uniformly definable bijection between $A_n$ to $\Bbb N$, then without the axiom of choice we can show that $\bigcup A_n$ is countable.

In the case of $\varepsilon_0$ we can show, without much difficulty that if $\alpha$ is a countable ordinal, then $\omega^\alpha$ is a countable ordinal as well (note that this is ordinal exponentiation). This means that by recursion we can uniformly define bijection between $\Bbb N$ and $\omega,\omega^\omega,\omega^{\omega^\omega},\ldots$ and therefore $\varepsilon_0=\sup\{\omega,\omega^\omega,\ldots\}$ is countable as well.

In general, if $\omega_1$ is a countable union of countable sets, it means that it is a limit cardinal in $L$ (or any other inner model satisfying choice), so it has to be at least $\aleph_\omega$. If you check, you will see that $\varepsilon_0$, and many other "large countable ordinals" have absolute definitions, so they cannot change from $L$ to $V$. So if they are countable in $L$, they will be countable in $V$ as well.