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.

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.