Order preserving bijection between countable sets and the set of natural numbers

Question

Let $M$ be a countable set. Suppose a linear order $\leq$ can be defined on $M$ such that there is an order preserving bijection between $M$ and the set of natural numbers $\mathbb{N}$ that preserves the order $\leq$. Then, is it true that for any other linear order $\leq'$ on $M$ there is an order preserving bijection between $M$ and $\mathbb{N}$ that preserves the order $\leq'$?

Let me take the example of $\mathbb{N}$. Define $\leq'$ in the following way: $1 <' 0 $ and for $n\geq 2$ $\leq'$ is the same as the natural order on $\mathbb{N}$. Thus $1 <' 0 <' 2 <' 3 <' \ldots$. Define the bijection $f$ as follows: $f(1)=0$, $f(0)=1$, $f(2)=2$, and so on. Then $f$ preserves the order $\leq'$. Now there is a doubt I have which is that when we talk about natural numbers $\mathbb{N}$ then does it by definition mean that we talk about the tuple $(\mathbb{N},\leq)$, where $\leq$ is the natural order on $\mathbb{N}$. If this is the case then $(\mathbb{N},\leq')$ is not the set of natural numbers. Then my example is wrong. Otherwise can you give a counterexample. But in general it is true for any arbitrary finite set which doesnot come with a natural order predefined on it. For instance if $X=\{a,b\}$, then under the two orders $a\leq' b$ and $b\leq' a$, $X$ is isomorphic with the set $\{0,1\}$. I assume $0$ to be a natural number. My hunch is that it is true in general, I may be missing something though, because the order $\leq'$ seems to me just a reshuffling of the elements of $M$ ordered accordingly to $\leq$.

Kindly help.

Answer 1

This is not true. You can get a counterexample by bijectively mapping $\mathbb N$ to $\mathbb Z$, for instance with

$$f:\mathbb N\to\mathbb Z,n\mapsto\begin{cases}k&n=2k\;,\\-k&n=2k+1\;.\end{cases}$$

If you now define $m\le'n\Leftrightarrow f(m)\le'f(n)$, there’s no least element in the resulting linearly ordered set $(\mathbb N,\le')$, whereas $(\mathbb N,\le)$ has the least element $1$, so there can’t be an order-preserving bijection between $(\mathbb N,\le)$ and $(\mathbb N,\le')$.

Answer 2

It's not true even if you require $\leq'$ to be a well ordering. Define $\leq'$ by using the natural order on the even numbers and the natural order on the odd numbers, but also defining $a \leq' b$ whenever $a$ is even and $b$ is odd. Then $1$ is not the least element of your well order but it has no immediate predecessor. (If you're familiar with order types, this gives the integers the order type $\omega + \omega$.)

Even simpler, use the natural order on all positive integers but say $k \leq' 0$ for all $k \gt 0$. This gives the integers order type $\omega + 1$.

In summary, you can give $\Bbb N$ the order type of any countably infinite ordinal, and there are $\aleph_1$ of those.

Answer 3

A simpler example is what follows. Consider $\mathbb N$ with the following total order: $$ n \leq ' m \text{ iff } m\leq n. $$

It can be checked that is satisfies the definition. Now, it is easy to see it cannot be a bijection from $(\mathbb N,\leq)$ to $(\mathbb N,\leq')$ preserving the orders:

Suppose $f$ is such a map, what happen to the image of $0$? Let's denote it by $m_0=f(0)$. It is clear that $m_0+1 \leq' m_0$ since $m_0 \leq m_0+1$. But then, $m_0+1$ cannot have a preimage, because if $f(x)=m_0+1$ it should be, since $m_0+1 \leq' m_0$, $$ x\leq 0, $$ which is a contradiction.