Suppose that $S$ is a set of functions such that $f \in S$ if and only if $f$ is either multiplicative or completely multiplicative and every $f \in S$ is defined on the set of natural numbers and takes natural numbers as its values ($f: \mathbb N \to \mathbb N$).

Recall that the function $f$ is completely multiplicative if, for every integers $a$ and $b$ we have $f(ab)=f(a)f(b)$ and $f(1)=1$. Such functions exist, one example is Liouville function.

Recall that the function $f$ is multiplicative if $f(1)=1$ and $f(ab)=f(a)f(b)$ for every coprime integers $a$ and $b$. An example of such a function is Euler`s totient function.

Only curiosity led me to the question of "how big" is the set of either multiplicative or completely multiplicative functions defined on the set $\mathbb N$ and which take values in the set $\mathbb N$.

It is clear that the set $S$ is at least countable because for every $n \in \mathbb N$ the function $f(a)=a^n$ is completely multiplicative.

So the real question is:

Is $S$ uncountable?


To define a totally multiplicative function $f: \mathbb{N}\to \mathbb{N}$, you only need to define its values on the primes numbers, since then $f(n)$ is just given by the prime factors decomposition of $n$.

But conversely, you can see that any value is allowed for the $f(p)$ where $p$ is prime. So $S$ has the cardinality of the set of functions $P\to \mathbb{N}$ where $P$ is the set of prime numbers. And this set is clearly uncountable (it has the same cardinality as $\mathbb{N}^{\mathbb{N}}$).

Another way to say all that is that $\mathbb{N}^*$ is the free abelian monoid on $P$, but you need not know such a notion to conclude.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.