Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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?
