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?

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

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.