# Intuition for $\omega^\omega$

I'm trying to understand the ordinal number $\omega^\omega$ and I'm having a hard time. I think I understand what $\omega^2$ is. It's what I would get if I took countably many copies of $\omega$ and order the set of those copies like $\omega.$ $\omega^3$ is a bit more difficult because I need to take countably many copies of $\omega^2$ now and do the same with them. I understand that the next ones are made in the same way, recursively. But understanding that the definition has meaning doesn't help me very much with visualizing $\omega^{10}$. And I become completely helpless when I try to tell myself what $\omega^\omega$ is in plain words. Is some explanation possible that is not just the definition (which I know)?

-
Perhaps this image might help illustrate it: upload.wikimedia.org/wikipedia/commons/e/e6/… –  Andrew Salmon Mar 20 '13 at 23:32

I think of $\omega^n$ as the set of all $n$-element sequences of naturals (not just increasing ones as in Andres's answer), ordered lexicographically.

There are two possible ways to extend this image to $\omega^\omega$. One is to say that $\omega^\omega$ is the set of all finite sequences of naturals, ordered with shorter sequences first, and them lexicographically between sequences of the same length.

The other is to say that an element of $\omega^\omega$ is an "infinite-to-the-left" sequence $(\ldots,a_n,\ldots,a_3,a_2,a_1,a_0)$ such that only finitely many elements of the sequence are nonzero. These sequences are then ordered lexicographically.

These "infinite-to-the-left" sequences perhaps look less strange if we write them as $$\cdots + a_nX^n + \cdots + a_3X^3+a_2X^2+a_1X + a_0$$ that is, they are just the set of formal polynomials with coefficients in $\mathbb N$. (The usual definition of "formal polynomial" takes care of the requirement that cofinitely many of the elements must be zero).

We can even write $\omega$ instead of the formal variable $X$: $$\cdots + \omega^n\cdot a_n + \cdots + \omega^3\cdot a_3+\omega^2\cdot a_2+ \omega \cdot a_1 + a_0$$ and written this way, the elements are exactly the actual ordinals below $\omega^\omega$. Because of the non-commutative nature of ordinal multiplication, we have to write the coefficients to the right of the power of $\omega$, though.

(Be careful not to take this too far, however: the usual rules for adding and multiplying polynomials do not correspond to ordinal addition and multiplication).

-
Or you could do what I do and just use the reverse lexicographic order on the set of sequences that are eventually $0$. –  Brian M. Scott Mar 20 '13 at 23:57

This may help:

One can identify $\omega^2$ with the set of subsets of $\omega$ of size $2$ or, equivalently, with the set of increasing sequences of length $2$ (ordered lexicographically), and $\omega^3$ with the set of subsets of $\omega$ of size $3$ or, equivalently, the set of increasing sequences of length $3$, etc. And $\omega^\omega$ is then identified with the set of all finite subsets of $\omega$ or, equivalently, the set of all finite increasing sequences of numbers, where the longer of two sequences of different length comes last.

(Now, we can identify finite sequences with numbers. For example, we can associate to the sequence $(2,6,20)$ the number $2^2\, 3^6\, 5^{20}$. This gives us an explicit representation of $\omega^\omega$ as a set of natural numbers, which may make it easier to visualize.)

Note that using increasing sequences (or equivalently, finite sets) as opposed to all sequences makes no difference. But there are advantages in certain contexts, for example, in the partition calculus of small countable ordinals, it is useful to consider finite sets of naturals (or increasing sequences) rather than elements of $\omega^\omega$.

I first mentioned a short version of this answer as a comment to a post by John Baez on Google+. John has a series of posts he calls "Bigness" intended to illustrate a "large" initial segment of the ordinals. You may find it useful (and as usual with John, entertaining).

-
This representation is somewhat misleading, however, because it doesn't preserve the ordering of the numbers. –  Henning Makholm Mar 20 '13 at 23:41
(Obviously no representation into numbers is going to preserve the ordering of numbers.) –  Andres Caicedo Mar 21 '13 at 0:58
The map $a + b \omega \mapsto (1 - 2^{-a}) + b$ is order preserving on $\omega^2$. IIRC, every countable ordinal has an order-preserving injection into $\mathbb{Q}$. –  Hurkyl Mar 21 '13 at 1:24
@Hurkyl Yes, of course. By "number" I meant "natural", which is in the same sense as Henning meant it. –  Andres Caicedo Mar 21 '13 at 1:36

This is a visualization which I like. Imagine tree structure in the following picture - you start in the root and in each node you have countably many branches (you can number them by natural numbers).

We order all nodes from left to right and in each layer from bottom to top. (The nodes can be identified with finite sequences of natural numbers. So our ordering is that if some sequence is longer, it will be the bigger one, and if two sequences are of the same length then we look at the first position where they differ. We see that this is one of the orderings mentioned in Henning Makholm's post.) This ordering is pretty similar to lexicographical ordering and verification that we get a well-ordered set is similar as for the lexicographic order.

Note that if we stop after fist column, we just get $\omega$. If take the first two two columns, we get $\omega^2$ (since $\omega+\omega^2=\omega^2$.) So the ordinal of the whole set is certainly at least $\omega=\sup\limits_{n<\omega}\omega^n$. But this set is precisely the union of the segments, which consists of initial $n$ columns, so it is precisely equal to $\sup\limits_{n<\omega}\omega^n=\bigcup\limits_{n<\omega}\omega^n$.

-

Here's how I visualize it. Consider this subset of $[0,1]$:

$$E_1 \;\; = \;\; \left\{\frac{1}{2}, \;\; \frac{2}{3}, \;\; \frac{3}{4}, \;\; \frac{4}{5}, \;\; \frac{5}{6}, \;\; \frac{6}{7}, \;\; \ldots \right \}$$

This is $\omega$.

More precisely, when ordered by the usual ordering for real numbers, $E_1$ becomes a representation for the order type $\omega.$

Now consider the union of $E_1$ and its $1$-unit translate (a subset of $[1,2]$), which will be a subset of $[0,2]$.

This is $2 \omega$.

By taking the unions of various appropriate integer translates of $E_1$, we get $3 \omega, \; 4 \omega, \; 5 \omega, \; \ldots$

By putting an integer translate of $E_1$ into the interval $[n, \; n+1],$ for each non-negative integer $n,$ and taking the union of these countable many translates of $E_1,$ we get $\omega \omega = {\omega}^2.$

If we take this last set, the set representing ${\omega}^2$, and scale/translate it into the interval $[0,1]$ (do this in a way the preserves order, which will be the case if you use a positive scale factor), we'll have a representation of ${\omega}^2$ that is a subset of $[0,1].$ Call this last set $E_2.$

The union of $E_2$ with it's $1$-translate will be $2 {\omega}^2$.

By taking the unions of various appropriate integer translates of $E_2$, we get $3 {\omega}^2, \; 4 {\omega}^2, \; 5 {\omega}^2, \; \ldots$

You can also get things like $3 {\omega}^2 + 2 \omega + 4$ by taking the union of a set in $[0,3]$ that represents $3{\omega}^2$ with a set in $[4,5]$ that represents $\omega$ with a set in $[5,6]$ that represents $\omega$ with the set $\left\{6 + \frac{1}{2}, \; 6 + \frac{2}{3}, \; 6 + \frac{3}{4}, \; 6 + \frac{4}{5} \right\}.$

By putting an integer translate of $E_2$ into the interval $[n, \; n+1],$ for each non-negative integer $n,$ and taking the union of these countable many translates of $E_2,$ we get $\omega {\omega}^2 = {\omega}^3.$

If we take this last set, the set representing ${\omega}^3$, and scale/translate it into the interval $[0,1]$ (do this in a way the preserves order, which will be the case if you use a positive scale factor), we'll have a representation of ${\omega}^3$ that is a subset of $[0,1].$ Call this last set $E_3.$

Keep going in this manner, obtaining $E_4 \subseteq [0,1]$ that is a representation of ${\omega}^4,$ $E_5 \subseteq [0,1]$ that is a representation of ${\omega}^5,$ $E_6 \subseteq [0,1]$ that is a representation of ${\omega}^6, \; \ldots$

Then ${\omega}^{\omega}$ can be represented by

$$E_1 \; \cup \; \left(E_2 + 1 \right) \; \cup \; \left(E_3 + 2 \right)\; \cup \; \left(E_4 + 3 \right)\; \cup \; \left(E_5 + 4 \right) \; \cup \; \ldots,$$

where $E_{n+1} + n$ represents the $n$-translate of $E_{n+1}$ for $n = 1, \; 2, \; 3, \; \ldots$

-