# Understanding countable ordinals (as trees, step by step)

Even though ordinal numbers – considered as transitive sets – are perfect non-trees, it is worth (and natural) to visualize them as trees, starting from the finite ones which are given as non-branching trees of finite height:

There are some crucial steps in the process of "understanding" larger ordinals, resp. when considering them as trees1.

1. The first crucial step – supposedly – is to truly understand the first limit ordinal $\omega$, i.e. the one object to be put beyond (and greater than) all finite ordinals, which corresponds to the first non-branching tree of infinite height:

Having understood $\omega$, one rather easily understands all ordinals $\alpha$ with a "tame" Cantor normal form (where the largest exponent of $\omega$ is finite). One can visualize these ordinals as $\omega$-branching trees of finite height, e.g. $\omega^3$ as the $\omega$-branching tree $\mathsf{T}(\omega^3)$ of height 3 $(= \log_\omega(\omega^3)$, informally):

2. The second crucial step – supposedly – is to understand $\omega^\omega$ which corresponds to the $\omega$-branching tree $\mathsf{T}(\omega^\omega)$ of height $\omega$. It's the first $\omega$-branching tree of infinite height (i.e. the root cannot be reached from the leaves). This is essentially the same kind of step as the first one (where $\omega$ cannot be reached from 0). Note, that $\mathsf{T}(\omega^\omega)$ is nevertheless a "tame" tree because its breadth is strictly greater than its height (as for finite ordinals and cardinals). Informally: $\omega^\omega > \omega = \log_\omega(\omega^\omega)$ .

And so, one somehow "understands" all ordinals $\alpha$ greater than $\omega^\omega$ as long as the breadth $\alpha$ of their trees is strictly greater than their height $\log_\omega(\alpha)$ – “as it has to be for ‘normal’ trees”.

3. The third crucial step is to understand the first ordinal $\alpha$ with $\omega^\alpha = \alpha$ (a.k.a. $\epsilon_0$ or $\omega \uparrow \omega$), which corresponds to the first $\omega$-branching tree with the same breadth as height.

These three steps

1. $\omega$
2. $\omega^\omega$
3. $\omega \uparrow \omega$

represent somehow specific, but also arbitrary conceptual hurdles that have to be passed. From a formal point of view (e.g. based on a hyperoperation sequence) they seem even more arbitrary, because the "natural" member $\omega^2$ seems to miss, and recognizing that step 1 and 2 are essentially the same, even $\omega^\omega$ should miss. So the "natural" first two steps should eventually be

1. $\omega$

2. $\omega \uparrow \omega\quad$?

My question is in any case:

What is the best (natural/conceptual) next step after $\omega \uparrow \omega\$? 2

1 In the following, trees are supposed to be full and complete.

2 I am aware, that $\epsilon_0$$=\omega \uparrow \omega$ plays a dominant role in proof theory, (first-order) Peano arithmetic, Gentzen, ...

• As an aside (and as written on the Wikipedia page for $\epsilon_0$ you linked to), your usage of $\uparrow$ is not consistent with Knuth's up-arrow notation. Every instance of $\uparrow$ in your question should really be $\uparrow\uparrow$ to be consistent with Knuth's usage. – Mark S. Jan 6 '14 at 3:59

## 1 Answer

The complete $\omega$-ary tree of height $\omega$ has uncountably many branches, so they clearly cannot be ordered in the type of the countable ordinal $\omega^\omega$. In fact with the ordering that you have in mind they are order-isomorphic to a co-countable subset of $[0,1)$ with the usual order.

There are also a couple of minor problems. Your picture for $\omega$ shows a tree of height $\omega+1$, not height $\omega$. Your trees are ordered, rooted trees; they are in general neither full nor complete.

• You steal my thunder, but thanks anyway. Does this mean, that my visualization of ordinals as trees works only up to $\omega^n$ for finite $n$ - if at all? And beyond $\omega^\omega$ ordinals cannot be depicted as $\omega$-ary trees? – Hans-Peter Stricker Dec 12 '13 at 9:20
• @Hans: I don’t see any natural way to do so, anyhow. It seems to me that the tree structure that you’re imposing on the ordinals below $\omega^\omega$ is a somewhat accidental consequence of the way that they’re ordered. If you really want a concrete realization of $\omega^\omega$ (and higher powers), you might look at the answers to this question and at the explicit working out here for $\omega^\omega$. – Brian M. Scott Dec 12 '13 at 20:49