We know that \(\omega\) and \(\varepsilon_0\) and \(\Gamma_0\) are coutable. In this blog, I will provide some actual injections from \(\mathbb{N}_0\) to these ordinals. These formulas aren't particularly groundbreaking, but they're a fun diversion.
I will use \(n\gamma\) as a shorthand for \(\gamma \times n\) throughout this blog.
Proof that \(|\omega| = \aleph_0\)[]
The mapping is just \(a \mapsto a\). Nothing to do here.
Proof that \(|2\omega| = \aleph_0\)[]
Every ordinal here is of the form \(a\) or \(\omega + a\). The mapping is \(a + 2b \mapsto a\omega + b\) where \(a\) is 0 or 1.
Proof that \(|\omega^2| = \aleph_0\)[]
An ordinal less than \(\omega^2\) is of the form \(a\omega + b\). Thus \(2^b3^a\) is a valid notation for all ordinals less up to \(\omega^2\). (The mapping I've made is only a partial function, but with infinite sets, partial surjections are equivalent to bijections.)
Proof that \(|\omega^\omega| = \aleph_0\)[]
All the ordinals we're looking for are polynomials in \(\omega\). There exists an injection from polynomials with coefficients in \(\mathbb{N}_0\) to prime factorizations of nonnegative integers:
\[2^{a_0}3^{a_1}5^{a_2} \ldots p_{n + 1}^{a_n} \mapsto a_n\omega^n + \cdots + a_1\omega + a_0\]
where \(p_n\) denotes the \(n\)th prime.