3
$\begingroup$

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:

enter image description here

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:
    enter image description here
    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):
    enter image description here

  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, ...

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mark S. Jan 6 '14 at 3:59
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Hans-Peter Stricker Dec 12 '13 at 9:20
  • $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Dec 12 '13 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.