Why is $\omega^{\omega}$ countable?

830 Views Asked by At

I'm confused as to why $|\omega^{\omega}| \neq \aleph_0^{\aleph_0}$. Since

\begin{align} \omega^{\omega} = \left\lbrace \sum_{i < \omega}^{1} (\omega^i \cdot n_i) + n_0 : n_i,n_0 \in \mathbb{N}_0 \right\rbrace \end{align}

wouldn't it follow that $|\omega^{\omega}|$ can be represented by an $\aleph_0$ tree with an $\aleph_0$ number of nodes? If so, then surely the $|\omega^{\omega}|$ must equal $\aleph_0^{\aleph_0}$.

NOTE: for the display equation, I had to swap the lower and upper limits, because for any two ordinal numbers $\alpha$, $\beta$, s.t. $\beta > \alpha$ and $\beta \geq \omega$, $\alpha + \beta = \beta$. Just to be clear

\begin{equation} \sum_{i < \omega}^{1} (\omega^i \cdot n_i) = \cdots \omega^2 \cdot n_2 + \omega \cdot n_1 \end{equation}

1

There are 1 best solutions below

0
On BEST ANSWER

No, $\omega^\omega$ is the set of those which can be represented as finite sequences. Namely, an ordinal below $\omega^\omega$ is a polynomial in $\omega$. So in effect $\omega^\omega$ is the natural way to represent $\Bbb N[x]$, which is of course countable.

So it does not correspond to the branches in a tree of height $\omega$, but rather to finite chains in that tree.