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