# Set builder notation for matching element pairs

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$)?

• 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. – copper.hat May 20 '15 at 18:10
• 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. – hardmath May 20 '15 at 18:12
• @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. – jbx May 20 '15 at 18:18
• @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'. – jbx May 20 '15 at 18:19
• 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). – hardmath May 20 '15 at 18:23

• 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). – jbx May 21 '15 at 12:32
• 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! – hardmath May 21 '15 at 12:40