one-to-one and onto functions help

Question

I am trying to understand this exercise.

Define $S : \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ by the rule: For all integers $n$, $S(n) =$ the sum of the positive divisors of $n$.

a. Is $S$ one-to-one? The answer is no. Counterexample: $S(6) = 1 + 2 + 3 = 6$ and $S(11) = 1 + 11 = 12, so S(6) = S(11)$ but $6 \neq 11$. In this one I understand that I need to choose any positive integer and show that there are different sets of positive integers that when added together will both equal the same number. i.e. $12$ in this case. But, I am not sure what $S : \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ has to do with the answer.

b. Is $S$ onto? No. Counterexample: In order for there to be a positive integer $n$ such that $S(n) = 5$, $n$ would have to be $< 5$. But $S(1) = 1$, $S(2) = 3$, $S(3) = 4$, $S(4) = 7$. Hence there is no positive integer $n$ such that $S(n) = 5$.

I do not understand how $S(1) = 1$, $S(2) = 3$, $S(3) = 4$, $S(4) = 7$ is derived? Are they just arbitrarily chosen? At first I was thinking that maybe the numbers are being added together like this: $1 + 1 = 2$ for $S(2)$ and then $2 + 1 = 3$ for $S(3)$, but if that is the case then I would have $3 + 2 = 5$ but there is no $S(5)$.

Thanks for any help you can provide.

Tony

Answer 1

The function $S(n)$ takes a positive integer $n$ as input. According to your definition, the output is determined by summing all the positive divisors of $n$.

The integer $1$ has only $1$ as a divisor, so $S(1) = 1$.

The integer $2$ has both $1$ and $2$ as divisors, so $S(2) = 1 + 2 = 3$.

The integer $3$ has both $1$ and $3$ as divisors, so $S(3) = 1 + 3 = 4$.

The integer $4$ has $1$, $2$, and $4$ as divisors, so $S(4) = 1 + 2 + 4 = 7$.

Answer 2

I'll try to explain everything you've mentioned and provide some wiki links. If you do not know them yet, you should have a look at them. The pictures there may get some things more clear. Hope it helps.

So, you've been given a function (or map) $S : \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ where $S(n) = \text{sum of all positive divisors of n}$.

about $S(n)$: given an integer $n$ a (positive) divisor $d$ of $n$ is any (positive) integer such that $n/d$ is an integer. (Equivalent: $d$ is a divisor of $n$ if an integer $k$ exists such that $n\cdot d = k$.) Therefore if $n = 4$ all possible positive divisors are $1,2,4$. If $n = 24$ all possible positive divisors are $1,2,3,4,6,8,12,24$.

The function $S(n)$ does nothing else but sum all those divisors: $S(4) = 1 + 2 + 4 = 7$, $S(24) = 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24 = 60$.

So, $S(1) = 1$, $S(2) = 1 + 2 = 3$ and so on.

one-to-one: If you want to show that $S$ is one-to-one (which some would call injective) you have to show that for every possible $m,n$ if $S(n) = S(m)$ it has to be that $m = n$. Because then it is guaranteed that there aren't two or more numbers which get mapped by $S$ onto the same result.

Therefore, a counterexample would be exactly this: $m,n$ such that $S(n) = S(m)$ but $m \neq n$ because then you've found two different numbers which get mapped to the same result. Since

$$ S(6) = 1 + 2 + 3 + 6 = 12 = 1 + 11 = S(11) $$

but $6 \neq 11$, this is a counterexample.

onto: Now, a function is called onto if every result can be reached (some would call it surjective). To state it a bit more formally: for every positive integer $k$ one has to find an positive integer $n$ such that $S(n) = k$.

Therefore, a counterexample would be a positive integer $k$ which isn't a result of $S$.

Okay, let's dive into the provided counterexample. First, since $n$ is a positive divisor of $n$ (as long as $n$ is positive, but here it is: $\mathbb{Z}^+$ are only positive integers) it holds that $S(n) \geq n$. Just try it out, let $n$ be any possible positive integer you like, then write down from small to big all possible divisors. The list will always be something like $1, \ldots, n$.

So, if $S$ is onto, there has to be an $n$ such that $S(n) = 5$. Given the argument above it must hold that $5 = S(n) \geq n$. Okay, so let's write down those:

$$S(1) = 1, S(2) = 1 + 2 = 3, S(3) = 1 + 3 = 4, S(4) = 1 + 2 + 4 = 7, S(5) = 1 + 5 = 6$$

Every possible $n$ such that $S(n) = 5$ gives a result $\neq 5$. Therefore $5$ isn't a result of $S$.

(One note: if you think again about the argument above it holds that $S(n) > n$ as long as $n > 1$. So given $n = 5$ you haven't to check $S(5)$ like I did above.)