Why does mathematical convention deal so ineptly with multisets?

Question

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?

Answer 1

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".)

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

Old question I know, but I wanted to point out that (finite) multisets do appear quite frequently in algebraic geometry/topology in the guise of finite formal sums; i.e., a multiset over a set $A$ is an element of the free abelian group on the elements of $A$. For example:

$$ a-2b+4c $$

for $a,b,c\in A$.

If you want to allow only positive numbers of each element, you work over the free commutative monoid instead; i.e., you require that the coefficients be non-negative:

$$ a+2b+4c $$

The fact that we are allowed to reorder is immediately given to us by the commutativity of the $+$ operation.

In the case of the product of primes it is very easy just to change the operation to multiplication and declare that every number is a unique product of primes, in the sense that it corresponds to a unique formal (commutative) product of (formal symbols corresponding to) primes.

Finite formal sums should be enough for the examples you gave, but if you want to allow infinitely many 'elements' then you can do that as well:

$$ M=\sum_{a\in A} m_a a $$

where $m_a\in\mathbb N$ for each $a\in A$. Semantically, this is still represented as a function from $A$ to $\mathbb N$, but the notation is different.

Answer 6

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.