0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I suspect $\mathbb A$ is the set of all finite subsets of $\mathbb Z$. $\endgroup$ – Cheerful Parsnip Apr 3 '13 at 3:24
0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ That was all i was looking for, Thank you very much, i would try to find a formal proof using your advices $\endgroup$ – Sebastian Valencia Apr 3 '13 at 3:34

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.