# The category of Multisets and Spans: morphism composition and tensor product

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 2.5.2.3, 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. 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? – Najib Idrissi Nov 8 '18 at 15:25
• Span composition is defined in 2.5.2.3 that you refer to. You mean you want to modify it so as to depend on $S_A$ and $S_B$ somehow? – მამუკა ჯიბლაძე Nov 8 '18 at 15:58
• 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. – Ben Sprott Nov 8 '18 at 16:07

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.