# There are finitely many maps on nonnegative integers satisfying $\phi(ab)=\phi(a)+\phi(b)$

How to show that there are finitely many maps $\phi:\mathbb{N}\cup\{0\}\to \mathbb{N}\cup\{0\}$ with the property that $\phi(ab)=\phi(a)+\phi(b)$ for all $a,b\in \mathbb{N}\cup\{0\}$.

-
The number is infinite if you change the domain to $\mathbb{N}$. Use logs with arbitrary bases. –  John Aug 22 '14 at 15:02
Hint: to show that there is no (nontrivial) multiplicative map from A to B, it suffices to show that A has some multiplicative property not possessed by any (nontrivial) submonoid of B, e.g. having an idempotent or absorbing element, e.g. see my comments to the answers of users1729 and Andre. –  Bill Dubuque Aug 22 '14 at 16:24

Interestingly, there are no such maps if we remove that zero from the picture. That is, there are no maps $\phi:\mathbb{N}\rightarrow\mathbb{N}$ such that $\phi(ab)=\phi(a)+\phi(b)$ for all $a,b\in\mathbb{N}$. This is because, by taking $a=1=b$, we again see that $\phi(a)=0$ for all $a$, a contradiction as $0\not\in\mathbb{N}$.

This argument does not imply the other answers, because there are in fact infinitely many such maps $\phi:\mathbb{N}\rightarrow\mathbb{N}\cup\{0\}$ (the above just proves that the element $1$ us mapped to $0$). To see that there are infinitely many such maps, notice that you can map primes $p$ to $1$ or $0$ (and other places too!), and so long as every prime is mapped to $1$ or $0$ you have a homomorphism.

So, a brief summary:

1. If $\phi:\mathbb{N}\cup\{0\}\rightarrow\mathbb{N}\cup\{0\}$, there is a unique such homomorphism.

2. If $\phi:\mathbb{N}\rightarrow\mathbb{N}\cup\{0\}$, there is are infinitely many such homomorphism.

3. If $\phi:\mathbb{N}\rightarrow\mathbb{N}$, there are no such homomorphisms.

4. If $\phi:\mathbb{N}\cup\{0\}\rightarrow\mathbb{N}$, there are no such homomorphisms (this follows from 3).

-
as you proved the part for general a,b leaving 0.I think I got the answer to my question in comment to @voldemort.thanks. –  spectraa Aug 22 '14 at 14:25
I.e. one cannot map a monoid with an idempotent into a monoid having no idempotents, since monoid maps preserve idempotents. Here $\, 1\cdot 1 = 1\overset{\phi}\to\, n+n = n,\,$ impossible in $\Bbb N_{>0}\ \$ –  Bill Dubuque Aug 22 '14 at 16:05
@Bill Do you not mean "semigroup"? Monoids always have an idempotent (and the proof does not use the unit element, just some idempotent). –  user1729 Aug 22 '14 at 18:19
Can't primes be mapped to anything, not just $0$ or $1$? –  Nishant Aug 22 '14 at 18:26
@Nishant Yes, but I was just trying to say why there are infinitely many maps, not trying to classify them. Of course, just killing all but one prime and varying where that prime goes also works, but the 0-1 argument has the advantage of telling you that there are, in fact, uncountably many such maps... –  user1729 Aug 22 '14 at 18:33

I may be missing something- but it seems that the only map with this property is identically $0$. The proof is as follows:

$\phi(0.0)=\phi(0)+\phi(0)$ which implies that $\phi(0)=0$.

Now, for any $a \in \mathbb{N}$, $\phi(a.0)=\phi(a)+\phi(0)$ which means $\phi(0)=\phi(a)+\phi(0)$ which implies $\phi(a)=0$.

-
thanks for the answer.But now 1 thing I can't understand is that why any other $a,b\in \mathbb{N}\cup\{0\}$ cannot satisfy inequality. –  spectraa Aug 22 '14 at 14:21

Hint: Consider $\phi(0\cdot b)$.

-
I.e. the absorbing element $\, 0 = 0\cdot n\,$ must map to an absorber $\ a = a + n\,$ in the image, thus the image $= \{0\}.\,$ That explains the extension $\,v_p(0) = \infty$ with $\,\infty = \infty + n.\ \$ –  Bill Dubuque Aug 22 '14 at 16:15

The other answers have shown that such a map must be identically zero. If we only require the map to be a homomorphism on the positive integers, the question is slightly more interesting: the positive integers as a multiplicative monoid are generated by the primes, and FTArithmetic means that any set map from the primes to $\mathbb N_0$ extends uniquely to a homomorphism.

-
A homomorphism from the positive integers to the nonnegative integers. –  Robert Israel Aug 22 '14 at 15:26