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

My math is weak so I'll try to clarify my question with an example. Consider the set $\{1,2,4\}$ for which the powerset $\{ \{\}, \{1\}, \{2\}, \{4\}, \{1,2\}, \{1,4\}, \{2,4\}, \{1,2,4\} \}$.

Now, if I sum the subsets I get the resulting set $\{ 0, 1, 2, 4, 3, 5, 6, 7 \}$.

How would I write the definition of a function that produces such a set?


To be clear, the function should be able to return the set $\{1,2,4\}$ which holds the property. But I'd like to be able to return a set of $n$ length with that property.

share|cite|improve this question
up vote 1 down vote accepted

For any set $B$ of natural numbers, let $f(B)$ be the set whose elements are sums of subsets of $B$. So $f:\mathcal{P}(\mathbb{N})\rightarrow\mathcal{P}(\mathbb{N})$. What you desire is to find an inverse of this function, however, the function is not surjective, so its inverse won't be defined on all of $\mathcal{P}(\mathbb{N})$.

For example, suppose we begin with the set $A=\{0,1,2\}$ and suppose that there were some set $B$ such that $f(B)=A$. By looking at sets of cardinality $1$, it follows that $B\subset A$, but notice that no subset of $B$ of $A$ gives $f(B)=A$.

If we only look at $f$ onto its image, we would need to show it is injective to show it's inverse in that case is well-defined. Immediately, we can see that if we consider $0$ a natural number, then $f(\{0,1\})=f(\{1\})$ so the map is not injective.

Even if we don't include $0$ as a natural number, notice that $$f(\{1,2,3,6\})=f(\{1,2,4,5\})=\{1,2,3,4,5,6,7,8,9,10,11,12\})$$ so the map is still not injective, and we cannot hope to find its inverse.

share|cite|improve this answer

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.