Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the functions $\text{add}:\mathbb{A}\to \mathbb{Z}$, such that $\mathbb{A}$ is a finite subset of $\mathbb{Z}$, and $f: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$

$$\text{add}(\{a,b,c,d,\ldots, n\}) = a+b+c+d+\ldots+n$$ $$f(m,n)=2m-n$$

Are those functions surjective? If so, how would you prove that? It is an exercise on algorithms for AI.

Thank you very much. I suspect that they are but I do not occur a formal proof to that. I need your help.

share|cite|improve this question
I suspect $\mathbb A$ is the set of all finite subsets of $\mathbb Z$. – Grumpy Parsnip Apr 3 '13 at 3:24
up vote 0 down vote accepted

It looks like you mean that $\Bbb A$ is the set of finite subsets of $\Bbb Z$, and that $$add\bigl(\{a,b,c,...,n\})=a+b+c+\cdots+n.$$ You'll need to be a little careful, here, and specify that $a,b,c,...,n$ must be distinct, or the function isn't well-defined--after all $\{1,1\}=\{1\}$, for example.

To show surjectivity, you must take an arbitrary $k\in\Bbb Z$. Then you must find a finite subset $S$ of $\Bbb Z$ and a pair $(m,n)\in\Bbb Z\times\Bbb Z$ such that $add(S)=k$ and $f(m,n)=k$. For the first one, this should be almost trivial to do. For the second, try letting $m=k$. What will we need $n$ to be?

share|cite|improve this answer
That was all i was looking for, Thank you very much, i would try to find a formal proof using your advices – Sebastian Griotberg Apr 3 '13 at 3:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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