Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
I suspect $\mathbb A$ is the set of all finite subsets of $\mathbb Z$. –  Grumpy Parsnip Apr 3 '13 at 3:24
    
Thanks.......... –  Sebastian Griotberg Apr 3 '13 at 3:28

1 Answer 1

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

 
discard

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.