Finding all bijections $f : \mathbb{N}^+ \to \mathbb{N}^+$ satisfying $a \mid b \Rightarrow f(a) \mid f(b)$

Question

Let $f$ be a bijection from $\mathbb{N}$ to $\mathbb{N}$. We have two statements:

1. $\quad a \mid b \Leftrightarrow f(a) \mid f(b)$
2. $\quad a \mid b \Rightarrow f(a) \mid f(b)$

I have managed to find all bijections $f$ satisfying statement (1). They are precisely the functions defined as

\begin{equation*} f(n) = \sigma(p_1)^{\alpha_1} \cdots \sigma(p_m)^{\alpha_m} \end{equation*}

where $n = p_1^{\alpha_1} \cdots p_m^{\alpha_m}$ is the prime decomposition of $n$, and $\sigma$ is a permutation of the infinite set of prime numbers (i.e. $\sigma$ is a bijection between the set of prime numbers and itself.).

Now I want to find all bijections $f$ satisfying statement (2), but I couldn't make any significant progress. My conjecture is that there is no bijection satisfying (2) but not (1). An example of such a bijection would also be very good as a first step. Thanks for any help.

EDIT 1: So far, I have proved some easy properties like the followings, but that's all. Let $f$ be a bijection satisfying statement (2), then we have

• $f(1) = 1$
• If $f(p)$ is prime, then $p$ is prime,
• If $f(a)$ and $f(b)$ are relatively prime, then $a$ and $b$ are relatively prime,
• If $f$ satisfies $f(ab) = f(a)f(b)$, then $f$ also satisfies statement (1).

Answer 1

I don't expect that there's any nice description of all the bijections that satisfy (2). In particular, here is a procedure you can follow to construct lots of them.

We define $f$ on numbers one by one with the following restrictions (starting from $f(1)=1$). First, don't define $f(n)$ until you've defined $f(m)$ for all divisors $m$ of $n$. When defining $f(n)$, you pick some value that is a common multiple of the (already-chosen) values for $f(m)$ for divisors $m$ of $n$. After doing so, for each divisor $d$ of $f(n)$ that is not yet in the image of $f$, pick some prime $p$ on which you have not yet defined $f$ and define $f(p)=d$.

In this way, you can define $f$ step-by-step such that in each step, the domain of $f$ is always a finite subset of $\mathbb{N}^+$ closed under taking divisors and its image is also closed under taking divisors. You can also easily arrange in this process that every element of $\mathbb{N}^+$ is eventually in the domain of $f$ and eventually in the image, so in the end you get a bijection $\mathbb{N}^+\to\mathbb{N}^+$. But also, $f$ can do all sorts of wild things. For instance, you could start by defining $f(2)=30$, and then defining $f$ on a bunch of other primes to take values in all the divisors of $30$. Then you could define $f(4)$ to be any multiple of $30$ at all. Continuing in this way, you will have infinitely many opportunities to define $f$ to not just behave like a permutation of the primes.