Let $\omega$ be the ordinal of the well ordered set $\mathbb{N}$, what does means $\omega^\omega$?

Question

Let $\omega$ be the ordinal of the well ordered set $\mathbb{N}$, then we can define the ordered sum and product, and so the sum and product of ordinal.

Is easy to see that $\omega+\omega+\cdots+\omega+\cdots=\omega\cdot\omega=\omega^2$

The $\omega^2$ means the ordered product defined by $(n_1,m_1)\leq(n_2,m_2)\in\mathbb{N}\times\mathbb{N}$ if $m_1<m_2$ and if $m_1=m_2$, then $n_1\leq n_2$.

And my question is, what does means $\omega^\omega$?.

I dont know since its elements are infinite sequences and I can't compare its last coordinate.

Answer 1

The ordinal $\omega^{\omega}$ may be represented as the set of finite sequences in $\mathbb N$ compared first by length (i.e. longer sequences are greater) and then, if the lengths are equal, by the lexicographic order like in the product. To get here, you can note that when we speak of things like $$\omega+\omega+\omega+\ldots = \omega^2$$ we really mean that $\omega^2$ is the smallest ordinal greater than $\omega$ and $\omega+\omega$ and $\omega+\omega+\omega$ and so on - equivalently, it is the union of all the ordinals of the form $n\omega$ for $n<\omega$.

Similarly, $\omega^{\omega}$ equals the union of $\omega^n$ for all $n<\omega$. Knowing that $\omega^n$ is the set of sequences of natural numbers length $n$ ordered lexicographically yields the above characterization of $\omega^{\omega}$.

As a technical concern, it that this method suggests the equivalent characterization given by Cameron Buie more naturally - there, each ordinal $\omega^n$ is given an embedding into a single set and the union occurs naturally in the condition of "finitely many terms other than $1$". To be formal about my characterization, one should note that we have done a disjoint union, as, in treating the sequences as having different lengths, we have not considered $\omega^{n}$ to be a subset of $\omega^{n+1}$, even though it is. That is, we are using the identity: $$\omega^{\omega}=\omega+\omega^2+\omega^3+\omega^4+\ldots$$ This is justified when we note that $\omega^n=\omega+\omega^2+\omega^3+\ldots+\omega^n$, which may be proved inductively from the easier statement $\omega^{n+1}=\omega^n+\omega^{n+1}$.

Answer 2

It is the ordinal of the set of sequences of natural numbers such that all but finitely-many of the sequence entries have a value of $1,$ ordered in a slightly different fashion.

Answer 3

Consider it to be the order type of all polynomials with nonnegative integer coefficients; i.e. something like $x^5+4x^2+1$.

The ordering is by "eventual domination"; if $f(x)>g(x)$ holds for all $x$ bigger than some number $N$, then we'll say $f$ comes after $g$ in our ordering.

There is an easy bijection between these and $\omega^\omega$. I'll illustrate it with an example: $$x^5+4x^2+1\\\mapsto\omega^5+\omega^24+1$$ That is, just substitute in $\omega$ for $x$.