# Why does mathematical convention deal so ineptly with multisets?

Many statements of mathematics are phrased most naturally in terms of multisets. For example:

Every positive integer can be uniquely expressed as the product of a multiset of primes.

But this theorem is usually phrased more clumsily, without multisets:

Any integer greater than 1 can be written as a unique product (up to ordering of the factors) of prime numbers.¹

Apart from rearrangement of factors, $n$ can be expressed as a product of primes in one way only.²

Every integer greater than 1 can be expressed as a product of prime numbers in a way that is unique up to order.³

Many similar factorization theorems are most naturally stated in terms of multisets; try a search for the phrase "up to rearrangement" or "disregarding order". Other examples: a monic polynomial is uniquely determined by its multiset of roots, not by its set of roots. The eigenvalues of a matrix are a multiset, not a set.

Two types that are ubiquitous in mathematics are the set and the sequence. The sequence has both order and multiplicity. The set disregards both. The multiset has multiplicity without order, but is rare in mathematical literature.

When we do handle a multiset, it's usually by interpreting it as a function into $\Bbb N$. This leads to somewhat strange results. For example, suppose $M$ is the multiset of the prime factors of some integer $n$. We would like to write:

$$n = \prod_{p\in M} p$$

or perhaps even just:

$$n = \prod M$$

But if we take the usual path and embed multisets in the conventional types as a function $M:\mathrm{Primes}\to\Bbb N$, then we have to write the statement with an infinite product and significantly more notation:

$$n = \prod_{p\in\mathrm{ Primes}}p^{M(p)}$$

(For comparison, imagine how annoying it would be if sets were always understood as characteristic functions with codomain $\{0, 1\}$, and if we had to write $\sum_{x\in S}{F(x)}$ all the time instead of just $|F|$.)

Interpreting multisets as functions is infelicitous in other ways too. Except in basic set theory, we usually take for granted that the difference between a finite and an infinite set is obvious. But for multisets-as-functions, we have to say something like:

A multiset $M$ is finite if $M(x)=0$ for all but finitely many values of $x$.

The other way that multisets are sometimes handled in mathematical proofs is as (nonstrict) monotonic sequences. One often sees proofs that begin "Let $a_1\le a_2\le\ldots\le a_n$; then…". The intent here is that the $a_i$ are a multiset, and if $b_i$ are a similar sequence of the same length, then the multisets are equal if and only if $a_i = b_i$ for each $i$. Without the monotonicity, we don't get this equality property. With first-class multisets, we would just say $A=B$ and avoid a lot of verbiage.

Sets and sequences both have a full complement of standard notation and jargon. Multisets don't. There is no standard notation for the union or intersection of multisets. Part of the problem here is that there are two reasonable definitions of multiset union:

$$(M\uplus N)(x) = M(x) + N(x)$$ or $$(M\Cup N)(x) = \max(M(x), N(x))$$

For example, if $M$ and $N$ are the prime factorizations of $m$ and $n$, then $M\uplus N$ is the prime factorization of $mn$, and $M\Cup N$ is the prime factorization of $\mathrm{lcm}(m,n)$.

Similarly there is no standard notation for multiset containment, for the empty multiset, for the natural injection from sets to multisets, or for the forgetful mapping from multisets to sets. If there was standard notation for multisets, we could state potentially useful theorems like this one:

$$m|n \quad\mbox{if and only if}\quad \mathrm{factors}(m) \prec \mathrm{factors}(n)$$

Here $\mathrm{factors}(m)$ means the multiset of prime factors of $m$, and $\prec$ means multiset containment. The analogous statement with sets, that $m|n$ if and only if factors$(m)\subset$ factors$(n)$, is completely false.

It seems to me that multisets are a strangely missing piece of math jargon. Clearly, we get along all right without them, but it seems that a lot of circumlocution would be avoided if we used multisets more freely when appropriate. Is it just a historical accident that multisets are second-class citizens of the mathematical universe?

-
Historical inertia. What are you gonna do? –  Qiaochu Yuan May 31 '12 at 21:40
Dear Mark, A nice question, with great examples. I think that the answer, as @Qiachu write, is historical inertia/accident. Cheers, –  Matt E May 31 '12 at 22:06
Interestingly, many software container libraries ignore the concept as well; one exception that I am aware of the the C++ standard library which includes a container, quite appropriately named, called multiset; I know that .Net does not; Java might..I'm not sure where the prejudice against the concept of a multiset derives, but in practical applications, I have rolled my own on many occasions... –  ItsNotObvious May 31 '12 at 22:22
@user12477: I've seen people post comments-that-are-too-long-for-a-comment as a series of comments instead, which I feel is preferable to posting an answer-that-is-not-really-an-answer. –  Rahul May 31 '12 at 23:00
Very clearly explained! In that last example, don't you mean factors(m) ≺ factors(n)? –  user32648 May 31 '12 at 23:00

This question reminded me of several notes by the influential computer scientist Edsger W. Dijkstra, who spent a lot of time thinking about how our notation can affect how we think and reason formally. (He preferred the term "bag" to "multiset", as in "a bag of positive integers.")

For example:

• In writing about how computing science influenced mathematical style:

I similarly prefer products to be defined on bags of factors rather than on sequences of factors. In the last case, one of the first things one has to do is to point out that as far as the value of the product is concerned, the order in which the factors occur in the sequence is irrelevant. Why then order them in the first place?

• In discussing the notational conventions he uses, and why he uses them:

Not making superfluous distinctions should always be encouraged; it is bad enough that we don’t have a canonical representation for the unordered pair.

Indeed--- forget multisets in general: why don't we even have the unordered pair? In this note, Dijkstra observes how a lack of a standard notation for this object often prevents us from recognizing that two statements are the same. (We are often fooled by superficial differences into saying things like "it suffices" to prove one of A, B, when from a logical point of view there is no difference between A and B.)

For my part, I think that we unconsciously "avoid" the formalism of multisets because we are generally uncomfortable with unordered things as unordered things. It is far more congenial to the human mind to think in terms of ordered things whose order then might, or might not, matter.

For some reason, the unordered set concept really "caught on" and we have all of this standard terminology associated with it. I would regard this as exceptional. I would definitely not regard it as evidence that sets are truly "first-class citizens" in written mathematics:

• Have you noticed how often it is possible to simplify the language and notation of a published argument by using "arbitrary" index sets, instead of initial segments of $\mathbb{N}$? (People introduce integer subscripts that play no role in organizing the ideas of an argument all the time.)

• Have you noticed how often people explicitly rule out the empty set in situations when it only complicates a statement or proof?

We could also avoid "a lot of circumlocution" if we only made better use of firmly established things! But do we?

I think that many mathematicians simply "think in lists." I think this preference has its roots in how humans communicate. Outside of mathematics, it is almost impossible to communicate the elements of an unordered collection without choosing some arbitrary order. (e.g. "Who is going to your party next weekend?" "What do we need from the grocery store?" "What are the nations of Europe?") We naturally communicate the elements of finite sets as lists, and then understand that they are sets. "De-listing" is so natural to us that we barely notice the "circumlocutions" it requires.

Another reason I think that multisets have not caught on is terminological.

• The word "multiset" sounds too technical for what it is.

• Dijkstra's "bag," on the other hand, doesn't sound technical enough. (To me, it only sounds OK for collections of "elementary" things, like integers).

• Neither "multiset" nor "bag" gives rise to a decent-sounding subobject name.

(Note, for example, how the OP unconsciously avoided the awful word "submultiset" through repeated use of the phrase "multiset containment".)

-
Dijkstra's remarks remind me of something J.H. Conway said complaining that mathematicians were too concerned with the specific implementation of objects in terms of set theory. He said that one should simply be able to postulate, say, two kinds of ordered pairs $\langle a,b\rangle$ and $\lbrack a,b\rbrack$ with $\langle a,b\rangle = \langle c,d\rangle$ if and only if $a=c$ and $b=d$, $\lbrack a,b\rbrack = \lbrack c,d\rbrack$ if and only if $a=c$ and $b=d$, and $\langle a,b\rangle\ne\lbrack c,d\rbrack$ for all $a,b,c,d$, without having to worry about how these would be represented by sets. –  MJD Jun 5 '12 at 2:18
Similarly one should be able to causally define an unordered pair $\def\ll{\langle\!\langle} \def\rr{\rangle\!\rangle}\ll a,b\rr$ with $\ll a,b\rr = \ll c,d\rr$ if and only if $(a=c \mathrm{\ and\ } b=d) \mathrm{\ or\ } (a=d \mathrm{\ and\ } b=c)$ without having to allay anyone's suspicions by demonstrating a particular set-theoretic object with that property. Conway wanted a someone to establish a general principle that all "reasonable" objects were definable in any "reasonable" theory, including ZF. –  MJD Jun 5 '12 at 2:20

I agree with Qiaochu that historical inertia plays the largest rôle: short of independent invention, you can’t use what you’ve never seen, and if there’s a familiar alternative, you probably won’t use something that’s less familiar to you, especially if you expect it to be somewhat unfamiliar to your audience. I don’t think that I ever saw them singled out as a separate kind of object until I decided to use Scheinerman’s text for our elementary discrete math course not too many years ago.

The fact that they’re a bit awkward to formalize probably also has had some effect. Had they come into common use early enough, this probably wouldn’t have mattered: ordered pairs are also a little awkward to formalize, but in most contexts no one cares. But their widespread utility was recognized late enough that (a) formalization was more of a concern, and (b) a variety of work-arounds was already available and often in use.

Why the general utility of the concept wasn’t recognized earlier is probably an unanswerable question, though I suspect that the variety of guises in which it can appear, or perhaps better, the variety of equivalent formulations in terms of more ‘standard’ objects, has something to do with the matter. One could also point to the fact that many applications in which they play a more than incidental rôle seem to fall in the area between logic and computer science.

-
I'm pleased that you made the connection to ordered pairs, which I had not thought of before in this context. I think the comparison is quite apt. Ordered pairs also arrived surprisingly late, and I've observed before that a lot of Principia Mathematica would be superfluous if Whitehead and Russell had had a modern conception of the ordered pair. Whole chapters of PM are devoted to proving theorems about relations which, in a modern presentation, would be special cases of the theorems about sets that were proved in earlier chapters. But in $PM$ relations are a different sort than sets. –  MJD Jun 1 '12 at 1:59

I'd suggest that part of the problem is the non-obviousness of operations on multisets. Take a look at the nLab page, for instance, where there's discussion about how precisely to think of morphisms, colimits, etc. with regard to multisets.

Also see the discussion on signed-multisets (a natural and immediate generalization) on haskell-cafe, where there was a large range of opinions regarding the meanings of a range of basic operations.

Arguably, if there were more attention to multisets in general, then more of these issues would be agreed on by convention or understood more broadly. On the other hand, the complexity of these issues vs. the definition of a simple set also points to why there hasn't necessarily been such attention. Also, of course, as one moves to fields like combinatorics, my sense is that multiset constructions become more common.

-
I could remark that what you call signed multisets on a base set $X$, if the multisets are finite (which I think is implicitly assumed in the discussion linked to), are nothing other than elements of the free Abelian group generated by $X$, a construction that is fairly well known and employed in the areas (mostly of algebra) where it is useful. –  Marc van Leeuwen Jul 13 '12 at 7:09

Here's another reason I think multisets have not entered common usage: they are very complicated! Blizard's multiset paper is just full of… stuff. Here are a couple of examples.

1. There are at least three analogs of the 'subset' relation. Writing $x\in_n M$ for "$x$ occurs in the multiset $M$ exactly $n$ times", and $x\in M$ for "$x\in_n M$ for some positive $n$", one can define:

• $A\Subset B$ if $x\in_n A$ implies $x\in_m B$ for some $m\ge n$.
• $A\sqsubset B$ if $x\in_n A$ implies $x\in_n B$
• $A\subset{\llap\sqsubset } B$ if $A\Subset B$ and $x\in B$ implies $x\in A$.

See page 43 of Blizard.

2. A union of multisets may fail to be a multiset. Let $M_i$ be the multiset that contains the single element $\ast$ with multiplicity $i$. Then $\bigcup M_i$ is not a multiset; this holds for both the $\Cup$ and $\uplus$ operations I mentioned in the original question.

-
Point 2 could be resolved by allowing arbitrary cardinal numbers as multiplicity. Then $\bigcup M_i$ would contain the single element $*$ with multiplicity $\aleph_0$. –  celtschk Jul 9 '12 at 16:23
I agree that some notions are really difficult to generalize from sets to multisets. However your examples are not the most convincing. $A\Subset B$ should mean $A\Cup B=B$ and this gives the first interpretation. If arbirtary unions are not allowed, too bad, topology is used to such restrictions as well. However there is a real difficulty in defining maps between multisets (or morphisms of multisets for the categorial oriented), not to mention injections, surjections. –  Marc van Leeuwen Jul 13 '12 at 7:16
@MarcvanLeeuwen, I think that's kind of missing the point. We can have a set $X$, and we can say, "Let $A$ denote a subset of $X$," and we can also say, "Let $B$ denote a multiset in $X$." And just like we can take images and preimages of subsets under functions, we can take images and preimages of multisets under functions. In neither case are subsets/multisets the objects of a category. –  goblin May 7 '13 at 7:10
@user18921: Of course one can, and does, work with multisets without considering them objects of a category. However the real difficulty of finding a natural definition of morphism is quite remarkable (see this discussion that sclv linked to) and certainly explains why we cannot treat multiset like a natural generalisation of sets for all purposes. Also, while I agree with what you say for images, I don't for preimages. If $f(x)=y$, how does the multiplicity of $x$ in $f^{-1}(M)$ depend on the multiplicity of $y$ in the multiset $M$? –  Marc van Leeuwen May 7 '13 at 9:35
@MarcvanLeeuwen, write $x * A$ for the multiplicity of $x$ in $A$, which is understood to be a cardinal number. Then for an arbitrary relation $f : X \rightarrow Y$ and any multiset $A \subseteq X$, we can define $y * f(A) = \sum_{x \in X : (x,y) \in f}x * A$. (From this, you can work out the answer to your question - simply view $f^{-1}$ as the converse of $f$.) Indeed, we can generalize. For an arbitrary multirelation $f : X \rightarrow Y$, we define $y * f(A) = \sum_{x \in X}[x * A][(x,y)*f]$. The point is, in both cases, the source and target of $f$ are sets, not multisets. –  goblin May 7 '13 at 12:50

One reason to prefer working with sequences is that they respond well to having their properties proven by induction. The syntactic representation of associative/commutative structures, by contrast, invites tricky reasoning and proofs with hard-to-spot errors in reasoning by case - if one is forced to reason about equivalence classes of sequences, then there will be no advantage and some additional complexity compared to working with sequences directly.

This problem facing the mathematician at work on a proof is faced in the automatic theorem proving community when trying to do pattern matching on associative-commutative structures. A lot of work has been done in the past thirty years applying term rewriting systems to this problem. As an example, here are how multisets of natural numbers are represented in Maude, an implementation of rewriting logic.

-