1
$\begingroup$

I am stuck on the following problem when I was trying to solve an entrance exam paper:

How many maps $\phi \colon \Bbb N \cup \{0\} \to \Bbb N \cup \{0\}$ are there with the property that $\phi(ab)=\phi(a)+\phi(b)$ for all $a,b \in \Bbb N \cup \{0\}$ ?

The options are as follows :

  1. none

  2. finitely many

  3. countably many

  4. uncountably many

Option 1 is not possible as if we take $a=1,b=0$ then we get $\phi(1)=0$ which is possible. But, I am not sure about the other options and could not decide which one holds good.

Can someone explain?

$\endgroup$
2
  • $\begingroup$ The number is infinite if you change the domain to $\mathbb{N}$. Use logs with arbitrary bases. $\endgroup$
    – John
    Aug 22, 2014 at 15:02
  • $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Aug 22, 2014 at 16:24

6 Answers 6

Reset to default
13
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – spectraa
    Aug 22, 2014 at 14:21
10
$\begingroup$

Certainly the map $\phi(n) = 0$ works.

Taking $a=0$ gives $\phi(0) = \phi(0) + \phi(b)$, whence $\phi(b) = 0$. So in fact the identically zero map is the only solution.

$\endgroup$
3
  • $\begingroup$ Thanks for the explanation. So, option 2 is the correct choice,I guess. $\endgroup$
    – learner
    Dec 11, 2013 at 18:54
  • $\begingroup$ No problem! and yes, that's right. $\endgroup$
    – universalset
    Dec 11, 2013 at 18:55
  • 2
    $\begingroup$ By the way, the problem is much more interesting if we don't require that $0$ be in the domain (but still allow it to be in the range). In that case, perhaps surprisingly, the answer is that there are uncountably many such functions! $\endgroup$
    – universalset
    Dec 11, 2013 at 18:57
8
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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.\ \ $ $\endgroup$
    – Bill Dubuque
    Aug 22, 2014 at 16:15
3
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ A homomorphism from the positive integers to the nonnegative integers. $\endgroup$
    – Robert Israel
    Aug 22, 2014 at 15:26
3
$\begingroup$

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).

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – spectraa
    Aug 22, 2014 at 14:25
  • $\begingroup$ 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}\ \ $ $\endgroup$
    – Bill Dubuque
    Aug 22, 2014 at 16:05
  • $\begingroup$ @Bill Do you not mean "semigroup"? Monoids always have an idempotent (and the proof does not use the unit element, just some idempotent). $\endgroup$
    – user1729
    Aug 22, 2014 at 18:19
  • $\begingroup$ Can't primes be mapped to anything, not just $0$ or $1$? $\endgroup$
    – Nishant
    Aug 22, 2014 at 18:26
  • $\begingroup$ @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... $\endgroup$
    – user1729
    Aug 22, 2014 at 18:33
1
$\begingroup$

Exactly one.

$a=0$ leads to: $\varphi\left(0\right)=\varphi\left(0\right)+\varphi\left(b\right)$ hence $\varphi\left(b\right)=0$. This for every $b$.

And function $x\mapsto0$ indeed suffices.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .