I have a set of pairs, $S = \{ \langle a,b \rangle_1, \langle a,b \rangle_2, ..., \langle a,b \rangle_n \} $ where $a$ is not unique amongst the pairs.

If I want to express the extraction of all the instances of $b$ for a particular instance of $a$, as a function, lets say $groupPairs()$. Is the following correct?

$groupPairs(a) = \{ b | \langle a, b \rangle \in S \}$

What if the actual pairs were not unique, and $S$ is a list rather than a set? How would I express the same function (thus giving me a non-unique list of instances of $b$)?

  • $\begingroup$ I'm not familiar with set builder notation, but perhaps you could write (clumsily) $\{(b,n) | (a,b) \in S, n = | \{ b | (a,b) \in S \}| \}$. This is not a list, but the second element gives the number of times the first element appears. $\endgroup$ – copper.hat May 20 '15 at 18:10
  • $\begingroup$ Note that set membership implies items appear at most once, so in the present context the ordered pairs $(a,b)$ will not repeat (even if the first coordinate $a$ does happen to repeat). To get repetitions of the ordered pairs you need what is called a multi-set or (in many programming contexts) a bag. $\endgroup$ – hardmath May 20 '15 at 18:12
  • $\begingroup$ @hardmath Yes. Thats why I said $S$ becomes a list and not a set, you can see it as a sequence. But I don't know if there is any elegant mathematical notation to iterate through and extract the list (or bag or whatever) of $b$ items. $\endgroup$ – jbx May 20 '15 at 18:18
  • $\begingroup$ @copper.hat I don't want to count the number of times. I want a list of the actual elements. Imagine it is a pair of 'surname' and 'name' and we're extracting the list of 'names' with the same 'surname'. $\endgroup$ – jbx May 20 '15 at 18:19
  • $\begingroup$ Okay, the list allows repetitions but also arranges an order of items (sequence) that you seem not to want (it wouldn't make a difference if all items were the same, though). $\endgroup$ – hardmath May 20 '15 at 18:23

Set-builder notation often means avoiding any explicit enumeration of the items (up to repetition, somehow, in the case of multi-sets) by giving a predicate that characterizes those items which belong. Strictly speaking this cannot work for multi-sets, since a predicate is either satisfied or not (true or false) upon application to an item.

What would be needed is a function, just as @copper.hat proposed, that assigns a count to each member of the underlying set. Once one has gone out on the limb, one may as well let the function itself be the representation of the multi-set.

There is a way to make the explicit enumeration of items in a list a faithful representation of a multi-set, i.e. one that disallows variable arrangement of the items. This is simply to insist on a sorted list. This requires the underlying set (domain) to have a sort order that is canonical or at least understood from the context. For surnames one might make the obvious choice of lexicographic ordering.

In the end what makes the best choice of representation depends on the use to which the notation is being put. An author needs their readers to be able to parse the notation with minimum confusion.

  • $\begingroup$ Thanks for your answer. Do you think the multiset union symbol $\uplus$ is clear and popular enough to use on its own? Or would I need to write a sentence or even define it (that it adds the sum together). $\endgroup$ – jbx May 21 '15 at 12:32
  • $\begingroup$ I think any choice of notation for multi-sets will need a definition in your write-up; there are no choices that are accepted by consensus, analogous to curly brackets $\{\ldots\}$ or union $\cup$ for sets. But definitions are good -- they give the Readers a chance to realize they are not in Kansas anymore! $\endgroup$ – hardmath May 21 '15 at 12:40

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.