Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

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 answerJoel'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$.

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

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

added 533 characters in body
Source Link
Hans-Peter Stricker
  • 9.7k
  • 5
  • 54
  • 113

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

 

(And maybe[Addendum:] For example this well-ordering looks like $2,4,6,8,\dots,3,5,7,9,\dots$ is the most naturallimit of a sequence of "natural" well-orderingorderings of type $\omega + \omega\ $?$\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$.

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

(And maybe like $2,4,6,8,\dots,3,5,7,9,\dots$ is the most natural well-ordering of type $\omega + \omega\ $?)

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

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

Source Link
Hans-Peter Stricker
  • 9.7k
  • 5
  • 54
  • 113

Prime numbers and limit ordinals

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

(And maybe like $2,4,6,8,\dots,3,5,7,9,\dots$ is the most natural well-ordering of type $\omega + \omega\ $?)

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