5
$\begingroup$

Suppose we have a multi-set $S$. For example, $S = \{ 1,2,2,3 \}$. Suppose we also have a set $T$, e.g., $T=\{1,2,3\}$. I would like to say, compactly, that $S$, when its duplicates are removed, is equal to $T$. Is there a simple, standard notation to do this?

$\endgroup$
1
  • 10
    $\begingroup$ I think this question is better suited for math.se. $\endgroup$
    – R B
    Dec 15 '14 at 16:22
14
$\begingroup$

Seeing how this question doesn't appear to be set to be moved to Math.SE (where it would properly belong), I'll answer it here.

Multisets are an awkward case of a perfectly natural mathematical object which never really got a standard notation — likely because multisets took much longer to be interesting to logicians. As a corollary, there is no standard notation for extracting a set from a multiset.

There are some natural ways to go about defining a reasonable notation for set-extraction:

  • Intersection. If your multiset is drawn from a universe $\mathbf U$, you can simply take the intersection of your multiset $\mathcal M$ with the universe, $\mathcal M \cap \mathbf U$. This is to me already a good notation, and is a good way of describing any other notation you might want to define. For your example, we may write $\{1,2,3\} = \{1,2,2,3\} \cap \mathbb N$.

  • Multiplicity filtering. Perhaps you are sometimes interested in when there are at least n of some of the elements; you can consider the set of such elements. One standard(-ish) notation for "$a$ is an element of $\mathcal M$ at least $n$ times" is $a \in^n\! \mathcal M$. Consider defining $$ \big.^n\!\mathcal M := \Bigl\{ a \in \mathcal M \;\Big|\; a \in^n\! \mathcal M \Bigr\} $$ in which case you have the identity $\big.^1\!\mathcal M = \mathcal M \cap \mathbf U$.

  • A set (forgetful) functor. Don't make things hard on yourself! You want the set associated with a multiset $\mathcal M$? Define $\mathbf{Set}(\mathcal M) = \big.^1\!\mathcal M$ to be that set!

There are any number of approaches to doing this. Of course, you should Google long and hard to see if there is any convention which your target audience is likely to be using. But if there isn't, then bear in mind that — by that very fact — there is no notation which you can assume your audience will be familiar with: so define your notation explicitly!


Remarks

The following are really extended comments...

Notation

It's pretty clear that $\{1,2,2,3\}$ can be used to represent a multiset in which there are two 2s, it will actually get in the way of how some people learned sets: not just that it has no repetition, but that repitition doesn't matter. Some schools teach that $\{1,2,2,3\} = \{1,2,3\}$, and in the standard set-theoretic construction of the ordered pair $(a,b) := \{\{a\},\{a,b\}\}$, one situation which must be addressed is the case of where $a = b$, in which case one obtains the set $\{\{a\}\}$. Bear this in mind, if you want to use multisets and sets side-by-side, and consider using a different notations entirely for multisets:

  • Square brackets notation (as noted by Wikipedia):

    $[1,2,2,3]$

  • Double-square brackets or double-set braces notation (as found here and here):

    $ [\![1,2,2,3]\!] \qquad \{\!\{ 1,2,2,3 \}\!\}$

    (bearing in mind that $\{\!\{ 1,2,2,3 \}\!\}$ looks a lot like the singleton set containing $\{1,2,2,3\}$).

  • Bag notation as provided by the stmaryrd LaTeX package (as illustrated here):

    Bag notation for the multi-set {1,2,2,3}

Multisets versus characteristic functions

You could try to treat multisets as being identical with their characteristic functions, so that $\{1,2,2,3\}$ can be identified with a function $f$ such that $f(2) = 2$, $f(1) = f(3) = 1$, and $f(n) = 0$ otherwise. Just as we sometimes identify languages $L \subset \{0,1\}^\ast$ with their characteristic functions $L: \{0,1\}^\ast \to \{0,1\}$, this is okay as an abuse of notation. But taking this too seriously has problems. For instance, you might not be pre-occupied with sums, but does $\mathrm{Sum}(f)$ represent $\sum_n f(n)$ (the sum of the values of $f$), or $\sum_n n\cdot f(n)$ (the sum of the elements of the multiset represented by $f$)? If you intend to act as though multisets "really are" their histograms, you must be prepared for such potential confusions by people who assume you have important reasons to choose that convention.

I would recommend that you treat multisets as first-class entities, which have characteristic functions, but are not the same as characteristic functions. That is, that you should keep the distinction between the collection and the function, unless you feel that identifying the two is very useful or important.

$\endgroup$
2
  • 3
    $\begingroup$ I like your Set(M) notation. In general, I think we would be better off using more descriptive names for things and fewer single-letter names or obscure accent marks, as the computer programming people learned much earlier. $\endgroup$ Dec 20 '14 at 0:21
  • $\begingroup$ @DavidEppstein: agreed, but semantic naming is also very important (also as understood by many programmers). For example, the support of the multiplicity function of a multiset $\def\M{\mathcal M}\M$ is indeed the projection of $\mathcal M$ into Set-land, but $\mathrm{supp}(\M)$ is not nearly as clear as $\mathrm{Set}(\M)$ is. Even for graphs, where the vertex set of a graph $G$ is $V(G)$, the semantics are provided (however telegraphically in that case) in a way that wouldn't be for $\bigl[\bigcup_{e \in G} e\bigr]$ (in the not entirely rare interpretation of graphs as a set of edges). $\endgroup$ Dec 20 '14 at 8:43
2
$\begingroup$

One possibility is to use $\mathrm{dom}$ or $\mathrm{sup}$ (or $\mathrm{supp}$), since you can think of a multiset as a function whose range is the non-negative integers; you are after the domain or support of this function.

$\endgroup$
2
  • 2
    $\begingroup$ Wouldn't the domain of the function include things which are not members of it? $\endgroup$ Dec 19 '14 at 4:34
  • $\begingroup$ Right, if we use domain that we want the range to be strictly positive. But support still makes sense. $\endgroup$ Dec 19 '14 at 4:51

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.