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.
 A: 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. 
