Prime numbers and limit ordinals

Question

As a set, i.e. as a von Neumann ordinal, the $\omega$-th limit ordinal $\omega^2$ is fairly complex and not so easy to visualize (for the novice). But as an explicit well-ordering of $\mathbb{N}$, there is a chance, and even more: all limit ordinals less than $\omega^2$ come as good old natural numbers.

Let $\pi:\mathbb{N}\rightarrow \mathbb{N}$ be the function that maps each natural number to its smallest prime factor. Consider the following well-ordering of $\mathbb{N}$:

$$n \preceq m :\equiv \begin{cases} n &\leq m &\mbox{if } &\pi(n) = \pi(m) \\ \pi(n) &< \pi(m) &\mbox{if } &\pi(n) \neq \pi(m) \end{cases} $$

This ordering is of type $\omega^2$ and it well-orders $\mathbb{N}$ like this:

$$2,4,6,8,\dots,3,9,15,\dots,5,25,35,\dots,7,49,\dots,11,121,\dots$$

Note, that the limit ordinals less than $\omega^2$, i.e. $\omega,\omega\cdot 2,\omega \cdot 3,\dots$ correspond exactly to the (odd) prime numbers.

I wonder if this specific well-ordering of order-type $\omega^2$ is by any means distinguished - as the most simple or the most natural one - like the natural ordering of $\mathbb{N}$ is the most natural well-ordering of type $\omega$.

---

[Addendum:] For example this well-ordering looks like the limit of a sequence of "natural" well-orderings of type $\omega\cdot k$:

$\omega\cdot 2 = 2,4,6,8,\dots,3,5,7,9,\dots$
the multiples of $2$, followed by the rest

$\omega\cdot 3 = 2,4,6,8,\dots,3,9,15,\dots,5,7,11,13,\dots$
the multiples of $2$, followed by the multiples of $3$ (that are not multiples of $2$), followed by the rest

In comparsion, orderings of type $\omega^2$ based on arbitrary pairing functions (see Joel's answer) come somehow out of the blue.

---

And I am looking for comparably easy to understand explicit well-orderings of $\mathbb{N}$ of types significantly larger than $\omega^2$, e.g. $\omega^\omega$ or $\epsilon_0$.

Answer 1

The ordinals below $\omega^2$ are exactly those of the form $\omega\cdot n+k$ for natural numbers $n$ and $k$. Thus, these are the ordinals having two digits in base $\omega$, and counting to $\omega^2$ is much like counting to one hundred in this regard.

To order $\mathbb{N}$ in order type $\omega^2$, therefore, is essentially the same as to have a pairing function on the natural numbers, where $\langle n,k\rangle$ is the number that will be assigned to $\omega\cdot n+k$.

There are a huge variety of pairing functions, many of which are simpler than others by various measures.

• My favorite is the Cantor pairing function $\langle n,k\rangle = \frac{(n+k)(n+k+1)}2 +k$, which has the advantage that it is a polynomial, easy to compute and invert, and has a simple definition.

• Another simple pairing function is $\langle n,k\rangle = 2^n(2k+1)-1$, which has the advantage that it is easily seen to be bijective, and is also easy to compute, invert and define.

The pairing function that is implicit in your order, in contrast, is not so simple on the computational criteria, since it requires us to factor numbers into primes, which can be difficult.

Lastly, let me say that I don't find your question to be mathematically meaningful without a clearer criteria for simplicity or naturality. Shall we minimize the size of the Turing machine that computes the order? Shall we find a smallest defining arithmetic formula? Shall we minimize the logical complexity of the definition? Or what?

Answer 2

I wonder whether you are familiar with the Sarkovskii ordering, which goes like this: first, the odd numbers (except 1) in increasing order, then the twice-an-odd numbers, then the 4-times-an-odd numbers, and so on, and finally the powers of 2, in decreasing order; $$3,5,7,9,\dots,6,10,14,18,\dots,12,20,28,36,\dots,16,8,4,2,1.$$

This ordering is very significant in the theory of discrete dynamical systems; if $m$ precedes $n$ in the Sarkovskii ordering, then any continuous function $f:[0,1]\to[0,1]$ that has an $m$-cycle also has an $n$-cycle, but there exist $f$ with an $n$-cycle but no $m$-cycle. Here an $n$-cycle is a list of $n$ distinct numbers $x_1,x_2,\dots,x_n$ such that $f(x_j)=x_{j+1}$ for $j=1,2,\dots,n-1$, and $f(x_n)=x_1$.

As a special case, if a continuous function on an interval has a 3-cycle, then it has an $n$-cycle for every $n$.

Answer 3

You can encode using recursive functions fairly large ordinals. But you are trying a bit too hard, I think, to encode $\omega^2$. Perhaps a simpler method would be as follows:

Let $\pi$ be a bijection between $\Bbb{N\times N\to N}$, and write $(k)_0,(k)_1$ as the integers such that $k=\pi((k)_0,(k)_1))$. For example if $\pi(m,n)=2^m(2n+1)-1$, then $(2)_0=0,(2)_1=1$.

Using this we can now encode $\omega^2$ as the lexicographic ordering on $\Bbb{N\times N}$: $$k\prec k'\iff (k)_0<(k')_0 \lor\Big((k)_0=(k')_0\land(k)_1<(k')_1\Big)$$

But we can go even further with that. Pick an encoding of all the finite sequences (=eventually zero) from $\Bbb N$. For example $(k)_i$ is the maximal power of the $i$-th prime that divide $k$; and write $|k|$ as the index of the first prime which doesn't divide $k$, and no prime with a larger index divides $k$ either. That is, $|k|$ is the length of the sequence that $k$ is encoding.

We can do all the encoding and decoding recursively (note that this entire calculation is bounded by $k$). So it works out fine.

Now we can define the following order on $\Bbb N$ which ultimately encodes $\omega^\omega$. $$k\prec k'\iff\begin{cases} |k|<|k'| & |k|\neq|k'|\\\text{The least } i\text{ such that }(k)_i\neq(k')_i,\ (k)_i<(k')_i & |k|=|k'|\end{cases}$$

So we first ask which of the numbers encodes a shorter sequence, if they encode sequences of the same length, we ask about the first time the sequences differ, and we ask which one is smaller.

Answer 4

I find ordinal notations based on diagrams to be more natural than these numeric encodings, and they can go pretty high, like up to the Bachmann-Howard ordinal, while remaining intuitively understandable. Herman Ruge Jervell had some very nice presentations about how to do these diagrams, but they seem to be offline now. It's possible they are in his new book, which I haven't seen a copy of yet.