Uncountably many ordering of natural numbers

Question

How do I construct uncountably many non isomorphic ordering of natural numbers?

Answer 1

The set of binary sequences $a_1, a_2, \dots$ is uncountable. (There is an obvious surjection onto $[0,1]$.) Here is how we can generate a unique permutation of $ℕ$ (here $0\in ℕ$) from such a sequence:

This is a recursive construction and we need memory of a number $s \in ℕ$ which is set to $s_0 = 0$ in the beginning and define $π_{-1} : \emptyset → ℕ$. (There is only one such function $π_{-1}$.) Recursively define for all $j \geq 0$: $$π_j : \{0,\cdots,j\} → ℕ, i ↦ \begin{cases} π_{j-1}(i), & \text{if }i<j \\ j+1, & \text{if }i=j \text{ and } a_j = 1 \\ s_j, & \text{if }i=j \text{ and } a_j = 0\text{.} \end{cases}$$ Where $$s_j = \begin{cases} s_{j-1}, & \text{if }a_j=1 \\ j+1, & \text{if }a_j = 0 \end{cases}$$ stores the last skipped value.

The limit defines an injective map $π: ℕ → ℕ, j ↦ π_j(j)$. Note that one value $s_∞ := s_N$ may be skipped if for some $N\in ℕ$ all $a_{n\geq N}=1$, otherwise $π$ is pretty much surjective. This can be extended into a permutation $\overline{π}:ℤ→ℤ$ which either acts trivially on negative numbers or shifts them all forwards by one, mapping $-1$ to the one skipped value $s_∞$ just mentioned.

A permutation of $ℤ$ induces an ordering on $ℤ$.

Answer 2

The easiest way requires knowing a little about ordinal numbers — specifically, that there are uncountably many countably infinite ordinal numbers, each corresponding to a different order type.

Here’s another way that does not require that knowledge, but it’s still not very straightforward if you’re just beginning to work with such things. I’m going to assume that you know that there are uncountably many infinite sequences of zeroes and ones. For each such sequence $\sigma=\langle b_n:n\in\Bbb N\rangle$ and each $n\in\Bbb N$ I’m going to define a subset $A_\sigma(n)$ of $\Bbb R$ as follows:

• if $b_n=0$, then $A_\sigma(n)=[4n,4n+1]\cap\Bbb Q\big)\cup\{4n+2\}$, and
• if $b_n=1$, then $A_\sigma(n)=\big([4n+2,4n+3]\cap\Bbb Q\big)\cup\{4n+2,4n+3\}$.

($\Bbb Q$ is the set of rational numbers.) Then for each binary sequence $\sigma$ I’ll let $A_\sigma=\bigcup_{n\in\Bbb N}A_\sigma(n)$.

For instance, if $\sigma=\langle 0,0,0,\ldots\rangle$, then $A_\sigma$ contains all non-negative multiples of $4$ and the rational numbers between $0$ and $1$ inclusive, between $4$ and $5$, between $8$ and $9$, and so on.

The idea is that each $A_\sigma=A_\sigma(0)\cup A_\sigma(1)\cup A_\sigma(2)\cup\ldots$ is a union of blocks that are all of one of just two different kinds. Every $A_\sigma(n)$ runs from some integer $4n$ to $4n+3$ and contains the integer all of the rational numbers between $4n$ and $4n+1$ inclusive, and the integer $4n+2$. When the $n$-th term of the sequence $\sigma$ is $0$, that’s all that $A_\sigma(n)$ contains; when it’s $1$, $A_\sigma(n)$ also contains the integer $4n+3$.

The set $(4n,4n+1)\cap\Bbb Q$ is densely ordered: it looks just like the rational numbers between $0$ and $1$, for instance. No two of its members are adjacent: between any two there’s always another. It does, however, have a first element, $4n$, and a last, $4n+1$. Each piece $A_\sigma(n)$ of the set $A_\sigma$ contains one of these densely ordered ‘chunks’ and one isolated point after it but before the next chunk; and if $b_n=1$, that $A_\sigma(n)$ also contains a second isolated point after the densely ordered part.

I’m not sure whether you can prove it with what you’ve studied so far, but the sets $A_\sigma$ in their natural orders as subsets of $\Bbb R$ are mutually non-isomorphic: the sequence of single versus double isolated points between dense chunks is unique a specific $A_\sigma$.

So what does this have to do with linear orders on $\Bbb N$? Each $A_\sigma$ is the union of countably many countably infinite sets, so each $A_\sigma$ is countably infinite. That means that there is a bijection $f_\sigma:\Bbb N\to A_\sigma$, and we can use $f_\sigma$ to define a linear order $\preceq_\sigma$ on $\Bbb N$ that is isomorphic to the natural order that $A_\sigma$ inherits from $\Bbb R$. For $m,n\in\Bbb N$ we define $m\preceq_\sigma n$ if and only if $f_\sigma(m)\le f_\sigma(n)$. If nothing else, you should try to verify that this really does define a linear order on $\Bbb N$; that much really is very straightforward.

If I think of anything simpler, I’ll come back and add it; for now this is the best I can do. (This, believe it or not, is a considerable simplification of the first idea along these lines that occurred to me.)

Added: (Apparently the idea that I discarded is actually given as a hint, so here it is.)

Another version of this idea starts by partitioning $\Bbb N$ into infinitely many infinite subsets $S_n$ for $n\in\Bbb N$. For instance, if $p_n$ is the $n$-th prime number, we could let $S_n=\{p_n^k:k\in\Bbb Z^+\}$, the set of powers of $p_n$ (other than $p_n^0=1$). Then we could let $S_0$ be the set of all natural numbers that are not prime powers, and we’d have our partition.

Now let $A$ be any subset of $\Bbb N$; I’ll define a linear order $\preceq_A$ on $\Bbb N$ as follows. For $m,n\in\Bbb N$, $m\preceq_A n$ if and only if

• there is a $k\in A$ such that $m,n\in S_k$ and $m\le n$, or
• there is a $k\in\Bbb N\setminus A$ such that $m,n\in S_k$ and $n\le m$, or
• there are $k,\ell\in\Bbb N$ such that $m\in A_k$, $n\in A_\ell$, and $k<\ell$.

It may take a bit of thought, but once you sort this out you’ll see that it amounts to arranging the sets $S_n$ in order, so that everything in $S_0$ comes before everything in $S_1$, which comes before everything in $S_2$, and so on, but reverseing the ordering of the numbers within some of the blocks $S_n$. Specifically, if $n\in A$, we order $S_n$ normally; if $n\notin A$, however, we turn $S_n$ around. Thus, if $A=\Bbb N$, the ordering looks like this:

$$\underbrace{0,1,6,10,12,14,\ldots}_{S_0}\;\underbrace{2,4,8,16,\ldots}_{S_1}\;\underbrace{3,9,27,81,\ldots}_{S_2}\;\ldots$$

(Here I’ve used the particular partition of $\Bbb N$ that I described in the first paragraph.) If, on the other hand, $A=\Bbb N\setminus\{1\}$, so that $1\notin A$, the ordering of the $S_1$ block gets turned around, and $\preceq_A$ looks like this:

$$\underbrace{0,1,6,10,12,14,\ldots}_{S_0}\;\underbrace{\ldots,16,8,4,2}_{S_1},\;\underbrace{3,9,27,81,\ldots}_{S_2}\;\ldots$$

Using arrows in a fairly natural way to represent the arrangement of each chunk, we could diagram these orders as

$$\longrightarrow\longrightarrow\longrightarrow\longrightarrow\ldots$$

and

$$\longrightarrow\longleftarrow\longrightarrow\longrightarrow\ldots\;,$$

respectively.

It isn’t trivial to prove, but if $A$ and $B$ are distinct subsets of $\Bbb N$, the orders $\preceq_A$ and $\preceq_B$ on $\Bbb N$ are not isomorphic. And since $\Bbb N$ has uncountably many subsets, we’ve produced uncountably many pairwise non-isomorphic linear orders on $\Bbb N$.

It probably isn’t at all obvious, but the basic idea underlying this approach is the same as that underlying the approach with the rational numbers: each finds a way to associate a distinct order type with a subset of $\Bbb N$ (or, equivalently, with an infinite sequence of zeroes and ones).