Kdtyjb

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

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

we say $f$ preserves order relation.

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

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

$xleq y iff$ $x$ divides $y$

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

Since $1$ divides $1$, $2$ divides $2$, ..., then $1leq 1$, $2leq 2$,...
, that is $Id_{mathbb{N}}$.

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{Pto P}$ a bijective function(where $Bbb P$ is the set of primes).

Then $f(n)=fleft(n_0^{m_0}cdots n_{k-1}^{m_{k-1}}right)=gleft(n_0right)^{m_0}cdots gleft(n_{k-1}right)^{m_{k-1}}$.

My question is: How can I show that there is no other isomorphism?

Let $g$ be an automorphism. Then for each prime $p$ we have $1 < p$ and thus $1 < g(p)$. If $g(p)$ were not prime, we'd have some element $1 < x < g(p)$ and thus $1 < g^{-1}(x) < p$ which is absurd. Hence each prime $p$ is sent to another prime $s(p)$. Now, we claim that
$$
g(p_1^{n_1} cdots p_k^{n_k}) = s(p_1)^{n_1} cdots s(p_k)^{n_k} tag{1}
$$

and since these are in fact automorphisms, this characterizes them. In effect, we can do induction on the maximum exponent of a prime decomposition of $n in mathbb{N}$. If $n = 1$ or $n$ prime, we have already proved this. Now take $n = p_1^{n_1} cdots p_k^{n_k} in mathbb{N}$ and without loss of generality, let's assume $n_1 leq dots leq n_k$. Since $ p_1^{n_1} cdots p_k^{n_k-1} < p_1^{n_1} cdots p_k^{n_k}$, then

$$
s(p_1)^{n_1} cdots s(p_k)^{(n_k-1)} = g(p_1^{n_1} cdots p_k^{(n_k-1)}) < g(p_1^{n_1} cdots p_k^{n_k})
$$

and so $g(p_1^{n_1} cdots p_k^{n_k}) = s(p_1)^{m_1} cdots s(p_k)^{m_k}$ with $m_i geq n_i$. We ought to see that $m_i = n_i$ for all $i$. If for some $j$ it would be $m_j > n_j$, then we would have that

$$
s(p_1)^{n_1} cdots s(p_k)^{(n_k-1)} < s(p_1)^{n_1} cdots s(p_k)^{n_k} < s(p_1)^{m_k} cdots s(p_k)^{m_k}
$$

and therefore applying $g^{-1}$ we get that

$$
p_1^{n_1} cdots p_k^{(n_k-1)} < g^{-1}(s(p_1)^{n_1} cdots s(p_k)^{n_k}) < p_1^{n_1} cdots p_k^{n_k}.
$$

which is absurd. This concludes the proof of $(1)$ and so autmorphisms correspond to bijections of $mathbb{P}$, and via their enumeration, the latter correspond to bijections of $mathbb{N}$. In other words, if $p_n$ in the $n$-th prime and we define

$$
begin{align}
Gamma : operatorname{Aut}(&mathbb{N}, |) longrightarrow mathbb{S}(mathbb{P}) longrightarrow mathbb{S}(mathbb{N})\
& g longmapsto (p mapsto g(p)) mapsto s_g
end{align}
$$

with $s_g(m) = n$ iff $g(p_m) = p_n$, then $Gamma$ is bijective.

Edit: according to comments the question concerns automorphisms of the order induced by division, hence what follows does not apply.

To ease on the notation, I will use $U = (mathbb{N},leq)$ for the naturals with the usual order and $D = (mathbb{N},leq')$ for the naturals with the order given by division. Note that any function $g : U to D$ which verifies $x leq y Rightarrow g(x) leq' g(y)$ is monotone as a function $tilde{g}: U to U$, because $x | y$ implies $x leq y$. Thus if $g$ were an isomorphism, we would have a bijective monotone function $tilde{g} : U to U$ with $g(n) = tilde{g}(n)$. As we have ruled out in the comments, as a function we have $g neq id$ and so by well ordering of the naturals (with respect to the order on $U$),

$$
l := min {n : g(n) neq n}
$$

is well defined, and so $g(l) neq l$. By surjectivity, $l = g(k)$ and thus $k neq l$. By minimality, since $k neq g(k)$ necessarily $l < k$ and so $g(l) < g(k) = l$. By minimality once again, this says that $g(g(l)) = g(l) = g(g(k))$ and so by injectivity, we get that $g(l) = g(k) = l$, and that is absurd. Since the contradiction came from assuming that such $g$ existed, no isomorphism between $U$ and $D$ exists.

The key insight is that for the order you defined, a prime number $p$ has the property that from $1 le x le p$ follows $x=1$ or $x=p$. In addition, no other number (besides 1, which is an obvious fixpoint of any isomorphism) fullfills that condition. So by necessitiy, any order isomorphism must bijectively map primes to primes.