# How to find all morphisms from $(\mathbb{N}, \mid)$ to $(\mathbb{N}, \mid)$?

I just need a small hint, not the full answer. I know that, if $f$ is a morphism,

1. $a \mid b \implies f(a) \mid f(b)$
2. $a \mid b$ and $a \mid c \implies a \mid b+c$, so $f(a) \mid f(b), f(a) \mid f(c), f(a) \mid f(b + c)$. Also, $f(a) \mid f(b) + f(c)$
3. $\forall a \in \mathbb{N}, a \mid 0$, so $\forall a \in \mathbb{N}, f(a) \mid f(0)$
4. $\forall a \in \mathbb{N}, 1 \mid a$, so $\forall a \in \mathbb{N}, f(1) \mid f(a)$

From these I can draw some conclusions:

a. From 3., $f(0) = a$ ($a \neq 0$), $f(\mathbb{N})$ only contains divisors of $a$.

b. From 4., if $f(1) = a$, then $f(\mathbb{N})$ only contains multiples of $a$.

The most general form I can think of for f is this:

$f(x) = ax^{b} (a, b \in \mathbb{N})$, but I can't seem to go any further than this.

Any help is appreciated.

-
$f(x) = ax^b$ for b > 1 may not satisfy condition 2. – Isomorphism Dec 15 '12 at 12:20
@Isomorphism can you give me an example for that? My reasoning is that if $x \mid a$ and $x \mid b$, then $x \mid a + b$, which means that $a+b = kx (k \in \mathbb{N})$. But then $(a+b)^r = (kx)^r = k^rx^r$ and $x^r \mid k^rx^r$. (I removed the other constant to make this simpler, it doesn't change anything) Is this wrong? – Gabi Purcaru Dec 15 '12 at 12:33
You were right and I was wrong. We can prove the second property for $f(x) = ax^b$ by looking at the prime divisors. Anyway, another solution is the constant map. Let $c$ be a natural number.Define $f(x) = c$. This works too. – Isomorphism Dec 15 '12 at 12:36
@Isomorphism but isn't this just $f(x) = cx^0$ ? Anyway, I'm not convinced that these are the only morphisms either, because, for example, $f(0)=0$ and $\forall x > 0$, $f(x) = c$, or $f(0) = 8, f(1) = 2, f(2) = 4, f(x) = 8$ for any other $x$, etc. are valid morphisms. – Gabi Purcaru Dec 15 '12 at 12:39
Ah! correct!. But f(1) = 1. For if $f(1) = x > 1$, then since $1^n|a$ for all n, we must have $x^n | f(a)$ for all n. But since $x > 1$, eventually $x^n$ should grow beyond $f(a)$. Thats a contradiction to the claim $f(1^n) | f(a)$ – Isomorphism Dec 15 '12 at 12:42

Your observations a,b are fine so far (if $0\in\mathbb N$ at all, that may depend on your local definitions).

Note that $a|b$ with $a>b$ is only possible with $b=0$. This allows us to construct uncountably many morphisms $f$ with $f(0)=0$: Assume $n\in\mathbb N$ and we have selected $a_k$ for $0\le k<n$ such that $a_0=0$ and $0< r,s\le n$ with $r|s$ implies $a_r|a_s$. Select $$\tag1a_{n}\in\bigcap_{0<k<n\atop k|n} a_k\mathbb N$$ arbitrarily (which is possible as the set on the right contains at least $0$). By the choice we guarantee that $k|n$ implies $a_k|a_n$. Therefore, for any such sequence $(a_n)$, letting $f(n)=a_n$ gives us a morphism. Note that any morphism with $f(0)=0$ can be obtained this way, i.e. the restriction imposed by $(1)$ is necessary.

For morphisms with $f(0)>0$ you correctly observed that we need $f(n)|f(0)$ for all $n$, esp. $f(n)\ne 0$ for all $n$. We can do almost the same as above, more precisely select $$\tag2 a_{n}\in\{d\in\mathbb N\colon d|f(0)\}\cap\bigcap_{0<k<n\atop k|n} a_k\mathbb N$$ this time observing that the set in $(2)$ is nonempty because it contains $f(0)$. However, at each step there are only finitely many choices. Still, this gives another uncountable lot of morphisms (why?) if $f(0)>1$.

-
$0 \in \mathbb{N}$, yes. Sorry for the confusion... This being my homework, I figured I was missing something, but now I'm starting to think the teacher was messing with us. Thanks! – Gabi Purcaru Dec 15 '12 at 13:12

It's a big hairy beast.

At all times, we will assume the prime factorization of $n$ is $n=p_1^{a_1}...p_k^{a_k}$.

For example, define a function first for each prime power, and then you can define $\phi(n)=\phi(p_1^{a_1})...\phi(p_k^{a_k})$. That only gives some basic examples, hardly begins to scratch the surface, but the restriction of $\phi$ at any prime power can be almost anything. (You can't define it arbitrarily for prime powers - for each $p^a$ you can choose $\phi(p^a)/\phi(p^{a-1})$ arbitrarily.)

One non-trivial example is to define $\phi(n) = p_1p_2...$. In this case your result is always square-free. Indeed, the function returns the largest square-free divisor of $n$.

Another non-trivial example would "forget" the power of $2$ is the prime factorization: $\phi(n)$ is the largest odd factor of $n$.

These first two examples preserve $\gcd$ and $\operatorname{lcm}$, which are the meet and join operator of $(\mathbb N,\mid)$.

Another example would be $\phi(n)=x^{\max(a_1,...a_k)}$, for some fixed $x\in\mathbb N$. This does not preserve $\gcd$, I don't think.

It might be worth just looking at examples that only depend on two primes. So morphisms $\phi$ such that $\phi(2^{a_1}3^{a_2}p_3^{a_3}...p_k^{a_k})=\phi(2^{a_1}3^{a_2})$ for all values. Even that is going to be an interesting mess.

-
thanks for your input. I selected Hagen's answer because it describes all solutions though – Gabi Purcaru Dec 16 '12 at 7:02