Order Preserving Isomorphism from $(\mathbb{N},\leq)$ to $(\mathbb{N},\leq)$

Question

Recall: Let $(X,\leq)$, $(Y,\leq ')$ be two well ordered sets. Let $f:X\rightarrow Y$ be a function such that

$a\leq b \rightarrow f(a)\leq 'f(b)$

we say $f$ preserves order relation.

If $f$ is a bijection and $a\leq b \iff f(a)\leq 'f(b)$ fir any $a,b\in X$ we say $f$ is an order isomorphism.

• Let us define $\leq$ on $\mathbb{N}$ as follows:

$x\leq y \iff$ $x$ divides $y$

Find all order preserving isomorphism from $(\mathbb{N},\leq)$ to $(\mathbb{N},\leq ')$.

I found one: since $1$ divides $1$, $2$ divides $2$, ..., then $1\leq 1$, $2\leq 2$,... , that is $Id_{\mathbb{N}}$. Can you help for other order preserving isomorphisms ?

Answer 1

If $n$ is a natural number, let $n_0^{m_0}\cdots n_{k-1}^{m_{k-1}}$ be the prime factorization.

Let $g:\Bbb{P\to P}$ a bijective function(where $\Bbb P$ is the set of primes).

Then $f(n)=f\left(n_0^{m_0}\cdots n_{k-1}^{m_{k-1}}\right)=g\left(n_0\right)^{m_0}\cdots g\left(n_{k-1}\right)^{m_{k-1}}$.

Answer 2

In what follows, work with the opposite of your order relation, so that $x \leq y$ is "$x$ is divisible by $y$".

If $f$ is an order automorphism, then $f$ permutes the order-theoretic prime ideals $I\subseteq \mathbb{N}$. But (working through what "prime ideal" means in this case) these are in bijection with the primes, so $f$ acts as a permutation on the primes: $I_p=\{n:\mathbb{N}| p\text{ divides }n\}$.

Now, let $$S_p=\left(\bigcup_{q\neq p}I_q\right)^{\complement}=\{1,p,p^2,\ldots\}\text{.}$$ Then $f$ induces an order isomorphism $S_p\simeq S_{f(p)}$. Therefore $f(p^{\nu})=f(p)^{\nu}$, and since $f$ preserves binary meets (lcm) we have $$f\left(\prod_p p^{\nu_p}\right)=\prod_p f(p^{\nu_p})\text{.}$$

That is, any order automorphism must be a completely multiplicative function that acts as a permutation on the primes.