7
$\begingroup$

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.

  • 0
    Can you state the homework problem exactly as presented in the problem? In particular, do you want partial order morphisms, or lattice homomorphisms? Partial order morphisms seem too broad to come up with a simple characterization of all instances.2012-12-15

2 Answers 2

3

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 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 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 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
    $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!2012-12-15
3

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.

  • 0
    thanks for your input. I selected Hagen's answer because it describes all solutions though2012-12-16