I have been thinking about multisets for a while. These are sets where elements can repeat, so $S =\{ a,a,b,c,b\}$ is a multiset on the set $A = \{a,b,c\}$.

I have also been looking into morphisms between multisets. Take two multisets $S_A, S_B$ with underlying sets $A, B$. I would like to define a morphism between multisets $S_A, S_B$ as a span on the underlying sets, so $f = A \leftarrow C \rightarrow B$, and $f: S_A \rightarrow S_B$. I am not sure how to define span composition. I am thinking a lot about David Spivak's work these days, so I am going to suggest a definition from his text, see section, which I cannot reproduce here. He uses fiber products.

I have two questions. Firstly, does my definition of the objects and morphisms define a category? Secondly, is it the case that the definition of morphism, as given, also constitutes a tensor product between multisets in the category as defined?

I have only an intuition that tells me that this definition of morphism is both a morphism of multisets in the category defined but is also a tensor product. We know that the Eilenberg-Moore category for the multiset monad is actually $\mathbb{N}$-modules. We should find a notion of tensor product there. I am guessing that we can define a monad on Set that maps a set to its set of multisets and spans as defined. There should be a similar category of modules, and thus a tensor product. I can only guess that what I am thinking means that the spans, as defined, map to both morphisms in the category of modules and the tensor product in the category of modules.

  • 1
    $\begingroup$ 1. You haven't defined composition so you haven't defined a category. 2. I don't understand what you mean by "a tensor product between multisets". What's the tensor product supposed to be? $\endgroup$ Nov 8, 2018 at 15:25
  • 1
    $\begingroup$ Span composition is defined in that you refer to. You mean you want to modify it so as to depend on $S_A$ and $S_B$ somehow? $\endgroup$ Nov 8, 2018 at 15:58
  • $\begingroup$ Yes, the span composition would depend on $S_A$ and $S_B$, I was hoping I would not have to modify it. I am saying that the morpisms are just spans and then morphism composition is just span composition. $\endgroup$
    – Ben Sprott
    Nov 8, 2018 at 16:07

1 Answer 1


One possibility is as follows. I'll think of a multiset as a finite set $X$ equipped with a multiplicity function $m_X \colon X \to \{1,2,3,\dotsc\}$. We can then define a morphism from $X$ to $Y$ to be a function such that $m_Y(y)=\sum_{x\in f^{-1}\{y\}}m_X(x)$ for all $y$. These can be thought of as "bijections up to multiplicity". Let $\mathcal{M}$ be the resulting category of multisets, and let $\mathcal{M}_{\leq k}$ be the subcategory where all multiplicities are at most $k$. These are symmetric monoidal categories under the evident disjoint union operation, so they have $K$-theory spectra in the sense of stable homotopy theory. Standard arguments show that $K(\mathcal{M}_{\leq 1})$ is just the sphere spectrum. We can also consider $\mathbb{N}$ as a symmetric monoidal category, and there is an adjunction between $\mathcal{M}$ and $\mathbb{N}$ and $K(\mathcal{M})$, which gives rise to a homotopy equivalence between $K(\mathcal{M})$ and $K(\mathbb{N})$, which is just the integer Eilenberg-MacLane spectrum. The really interesting point is that $K(\mathcal{M}_{\leq k})$ is equivalent to $SP^k(S^0)$, the $k$'th symmetric power of the sphere spectrum, which is important for a variety of reasons. This is essentially a translation of an old theorem of Kathryn Lesh, which she formulated in rather different terms.

As well as the disjoint union, we can also use the function $m_{X\times Y}(x,y)=m_X(x)m_Y(y)$ to make $X\times Y$ into a multiset. This makes $\mathcal{M}$ into a symmetric bimonoidal category, with $\mathcal{M}_{\leq 1}$ as a symmetric bimonoidal subcategory; this corresponds to the fact that $S$ and $H$ are ring spectra. This construction also restricts to give functors $\mathcal{M}_{\leq j}\times\mathcal{M}_{\leq k}\to\mathcal{M}_{\leq jk}$, which again have natural counterparts in stable homotopy theory.

  • 1
    $\begingroup$ Thanks for your answer Neil. I am afraid it is not my field of expertise. I am hoping someone can write an intervening post to explain your answer a bit more. $\endgroup$
    – Ben Sprott
    Nov 10, 2018 at 15:47

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.