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](http://math.mit.edu/~dspivak/CT4S.pdf), 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.



The category of Multisets and Spans: morphism composition and tensor product
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. 


