How is $\epsilon_0$ countable?
This is a notational nightmare in set theory. $\omega$ is both an ordinal and a cardinal; and the cardinal exponentiation as well ordinal exponentiation have the same notation.
It is often understood from context which of the two is used, but it can still be quite confusing to people new to this. Cardinal exponentiation $\omega^\omega$ means we take the cardinality of all the functions from $\omega$ to $\omega$, this is of course of size continuum, which is of an uncountable cardinality.
On the other hand, $\omega^\omega$ in ordinal exponentiation means that we take some order type which is a supremum of countable ordinals. What are those ordinals? These are ordinals which defined themselves as limit of smaller ordinals are $\omega^n$, and so we can continue to unfold the definitions of ordinal arithmetics until we have that $\omega^\omega$ is a supremum of some much "simpler" set (It is actually much more complicated that just $\omega^n$, though)
This "simpler" set contains only countable ordinals, and itself is countable. We know that the countable union of countable sets is countable, therefore $\omega^\omega$ is countable.
What does all that have to do with $\epsilon_0$? Well, by induction we have that $\omega,\omega^\omega,\omega^{\omega^\omega},\ldots$ are all countable, and there are only countably many of those. From this we have that $\epsilon_0$ is also countable. It is a large countable ordinal. Now we can continue by induction, what is $\epsilon_1$? We repeat the same process only we start from $\epsilon_0+1$ instead of $\omega$.
This is again a countable process, so it must end at a countable ordinal as before; by induction we can see that:
- if $\alpha$ is countable then $\epsilon_\alpha$ is countable, if $\alpha$ is limit then it is just the union of countably many countable $\epsilon$ numbers (the induction hypothesis is that $\epsilon_\beta$ for $\beta<\alpha$ is countable) and therefore $\epsilon_\alpha$ is countable.
- If $\alpha=\beta+1$ then $\epsilon_\beta$ is countable and as with $\epsilon_1$ we end up in a countable ordinal.
What happens with $\epsilon_{\omega_1}$? Well, for every $\alpha<\omega_1$ we have that $\epsilon_\alpha$ is countable, and if $\alpha<\beta$ then $\epsilon_\alpha<\epsilon_\beta$. Therefore we have $\aleph_1$ many distinct ordinals below $\epsilon_{\omega_1}$, therefore it is not a countable ordinal anymore. In fact $\epsilon_{\omega_1}$ is the limit of all those $\epsilon_\alpha$ for countable $\alpha$, and one can see that the the supremum of uncountably many countable ordinals cannot be other than $\omega_1$. (If $\delta>\omega_1$ is cannot be the supremum of a set of countable ordinals!)
Let us repeat the definitions of ordinal arithmetics:
- $\alpha+0 = \alpha;\ (\alpha+\beta)+1 = \alpha+(\beta+1)$; and for $\beta$ limit, $\alpha+\beta=\sup\{\alpha+\gamma\mid\gamma<\beta\}$,
- $\alpha\cdot0 = 0;\ \alpha\cdot(\beta+1)=\alpha\cdot\beta+\alpha$; and for $\beta$ limit, $\alpha\cdot\beta=\sup\{\alpha\cdot\gamma\mid\gamma<\beta\}$,
- $\alpha^0 = 1;\ \alpha^{\beta+1} = \alpha^\beta\cdot\alpha$; and for $\beta$ limit, $\alpha^\beta=\sup\{\alpha^\gamma\mid\gamma<\beta\}$.
Some more reading material:
- A number system (Definitions of ordinal arithmetics)
- How far do known ordinal notations span? (Discussion on Cantor Normal Form of ordinals, and $\epsilon$-numbers)
Wikipedia gives the answer, in fact: it's the union of a countable set of countable ordinals $\left\{\omega,\omega^\omega,\omega^{\omega^\omega},\ldots\right\}$
As written on Wikipedia, it's because it's a countable union of countable sets. Let $u_0 = 1$ and $u_{n+1} = \omega^{u_n}$. It is easily shown by induction that $u_n$ is countable for all $n$:
- $u_0$ is obviously countable;
- it is a general fact that if $\alpha$ is countable, then $\omega^\alpha$, the finite sequences of elements of $\alpha$ is countable too. To see that, let $s_n$ be the sequences of elements of $\alpha$ of length exactly $n$ (ie. the $n$th element is nonzero and all the elements after that are zero), then (by definition) $\omega^\alpha = \bigcup_{n < \omega} s_n$, and $|s_n| = \aleph_0^n = \aleph_0$, so $|\omega^\alpha| = \aleph_0$. (In fact you can try to show that if $\alpha, \beta$ are countable, then so is $\alpha^\beta$).
Finally, you have (by definition) $\epsilon_0 = \bigcup_{n < \omega} u_n$, a countable union of countable sets.