3
$\begingroup$

Say you have a set 

A = { 1, 5, 10 }

which when put through a function, produces the set:

B = { 1, 5, 10, 6, 11, 15, 16 }

That is, f(A) = B. I’m not sure the proper way to write the math for this, but the gist is that the output is made from all combinations of the input set, without duplicates. So, for example, here's how the elements are computed in the given example:

B = { 1, 5, 10, 5+1, 10+1, 10+5, 10+5+1 }

Each individual item in A is combined with the others so that the output is a list of unique values. That is, since 1+5 is the same as 5+1, we only use that value once. A more concise way to describe the function is that it is the set of unique values from all nonempty combinations.

The second (and most important) part to this is to go the other direction: given B, how do you figure out A?

Since I’m so new to this whole field, my question can be broken down into a few parts:

  1. What is the proper way to write the mathematics described above?
  2. What branch of mathematics would generally cover this problem?
  3. What would a solution to this specific problem look like?

I'm generally coming from more of a self-taught programming background, so I'm sure there are plenty of gaps in my knowledge. Sorry for my ignorance, and thanks in advance!

I've explored a bit of of matrix algebra for this, and I've had some success with combining A and its transpose, taking the lower triangular matrix from the result, and combining this with the original values of A. I was hoping there would be a straight-forward way to reverse this process? (Possibly wishful thinking?)

I think there may also be some way to puzzle through this by looking at which combinations of values in B produce the others, but I imagine there's a much more elegant way to go about it.

I've asked a corresponding question regarding the CS aspects of this problem here: https://stackoverflow.com/questions/56825784/is-there-a-standard-approach-to-solving-non-injective-functions

$\endgroup$
5
  • 3
    $\begingroup$ Shouldn't $0$ be part of $B$? $\endgroup$ – Vsotvep Jun 30 '19 at 2:54
  • $\begingroup$ @Vsotvep No, in this scenario I'm only looking to add the numbers together. (In my actual application it's more detailed, but for the sake of simplicity I'm just doing addition.) $\endgroup$ – saucewaffle Jun 30 '19 at 4:27
  • $\begingroup$ Exactly, if you add none of the numbers together, you get $0$. Since $\varnothing\subset A$, your description says $\sum\varnothing=0$ should be part of $B$, but the $B$ you have written out says it shouldn't. The precise description you're looking for is thus that you're looking for all nonempty combinations of elements in $A$. $\endgroup$ – Vsotvep Jun 30 '19 at 6:54
  • $\begingroup$ I see - makes total sense! Yes, the nonempty combinations are what we're looking for. $\endgroup$ – saucewaffle Jun 30 '19 at 13:51
  • $\begingroup$ After some more research, it seems like this may be a constraint satisfaction problem $\endgroup$ – saucewaffle Jun 30 '19 at 16:04
2
$\begingroup$

I would write it as $$ f(X) = \Bigl\{\sum_{a\in A} a \Bigm| A\subseteq X, A\text{ is finite}, A\ne\varnothing\Bigr\}$$

This is a combination of set builder notation and an indexed sum. Both of these are so widespread as part of "ordinary mathematical notation" that it's hard to assign them to a particular "branch" of mathematics. They're usually taught, more or less, in first-year courses that have a different main focus, as part of an effort to give students general familiarity with mathematical notation.

You could say they're part of set theory, but if you pick up a textbook dedicated to "set theory" in particular, it's probably going to zip past this kind of elementary notation in ten seconds flat.

$\endgroup$
1
  • $\begingroup$ This is fantastic! Thanks so much on the guidance - no wonder I've been getting so lost! Regarding the formula you provided, is there a way to solve for B? (Also, I've updated my question to clarify my thinking a little.) $\endgroup$ – saucewaffle Jun 30 '19 at 4:46
1
$\begingroup$

Given $B$ and assuming it is a finte set if positive integers, we can at leas partially reconstruct $A$: To begin with, any element of $B$ that cannot be written as the sum of two distinct smaller elements of $B$, must be an element of $A$. In particular, this applies to the two smallest elements of $B$. With $B=\{1,5,6,10,11,15,16\}$, we find $1,5\in A$ and also $10\in A$ and thus are already done. Note that more elements may belong to $A$. For example, we might ignore $11$ because $11=5+6$, but this equality is not the reason why $11\notin A$ (because it is actually "invalid" as $6$ comes from $1+5$ and so $11=5+1+5$ would use $5$ twice). You have a few more tricks up your sleeve as the largest element of $B$mus be the sum of all elements of $A$.

However, $$ f(\{1,2,3,4,7\}) =f(\{1,2,3,5,6\})=\{1,2,3,\ldots,17\}$$ shows that in general we cannot reconstruct $A$ reliably.

$\endgroup$
8
  • $\begingroup$ Thanks so much! I feel this is very much the right track of thinking. A few points of clarification: the use of 5 twice is not an issue; it's just the resulting sum that needs to be unique. In fact, it's expected that you would use each number multiple times, and I've updated my question to illustrate this. Also, in the last part of your answer, I'm confused about what it's showing, and how it explains that we can't reliably reconstruct A? $\endgroup$ – saucewaffle Jun 30 '19 at 4:43
  • $\begingroup$ @saucewaffle Not every function has an inverse. To be precise, only injective functions have inverses. A function is injective if two distinct inputs give two distinct outputs. The last part of this answer shows that both the input $\{1,2,3,4,7\}$ and the input $\{1,2,3,5,6\}$ give the output $\{1,2,3,\dots,16,17\}$. So if we had an inverse, what should it send the output $\{1,2,3,\dots,16,17\}$ to? It's not possible, since there is no unique input resulting in that output. $\endgroup$ – Vsotvep Jun 30 '19 at 6:59
  • $\begingroup$ @saucewaffle Also, you say "the use of $5$ twice is not an issue", but your description of the function is that there are no duplicates, so this is an issue. $\endgroup$ – Vsotvep Jun 30 '19 at 7:13
  • $\begingroup$ @Vsotvep Thank you so much for explaining injective functions! That makes perfect sense, and yes it does show that there's no way to clearly figure out the inverse. I figured something like this may be the case, and I'll poke around on StackOverflow if there's a common CS approach to solving these types of problems. $\endgroup$ – saucewaffle Jun 30 '19 at 13:59
  • $\begingroup$ @Vsotvep Regarding the use of 5, yes this is confusing in my description. I meant that all values of $A$ must be unique, but that the values are used multiple times in $f(A)$ $\endgroup$ – saucewaffle Jun 30 '19 at 14:01

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.