Set builder notation for matching element pairs

885 Views Asked by At

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

1

There are 1 best solutions below

2
On BEST ANSWER

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.