[Math] Naturally occurring orderings

gm.general-mathematicsordinal-numbers

The are many orderings that naturally occur in interesting but seemingly unrelated circumstances. Here are some examples:

  1. The volume spectrum of orientable hyperbolic 3-manifolds has order type $\omega^\omega$.

  2. Ordinals that play important roles in Conway's $\mathbf {On_2}$, most notably $\omega^{\omega^\omega}$, the algebraic closure of $2$. See Lenstra's papers 1 2, Conway's ONAG, and Lieven's blog posts.

  3. The set of fusible numbers has order type $\epsilon_0$ (quite likely but not proven, see my note).

  4. The Sharkovsky ordering of natural numbers, which does not have order type of an ordinal.

  5. There are proof theoretical ordinals, which I know little about.

Do you know any other examples or see any connection among aforementioned examples? Most of the examples above are ordinals, but other interesting examples are welcome.

Best Answer

Alright, I'll put my comment as an answer and hopefully get this off the no-upvoted-answers queue. :)

Here's another nice-but-surprising way to get $\omega^\omega$: Let $\|n\|$ denote the smallest number of 1's needed to write n using any combination of addition and multiplication, e.g., $\|7\|=6$ as shortest way for 7 is $7=(1+1+1)(1+1)+1$. (This is known as the "integer complexity" of n; it's sequence A005245.)

Now, for any n, we have the lower bound $\|n\|\ge 3log_3 n$. So subtract this off and consider $\delta(n):=\|n\|-3log_3 n$. Then the set of all values of $\delta$ is a well-ordered subset of $\mathbb{R}$, with order type $\omega^\omega$.

For a proof, I refer you to my preprint: http://arxiv.org/abs/1310.2894