# Category of multisets

I am trying to define a category $$MSet$$ of multisets as sets equipped with an equivalence relation. I will call such objects multisets. The other notion of multisets as pairs $$(A,m_A\colon A\to\mathbb{N})$$ I will call standard multisets, these are actually multisets in which every equivalence class is finite. I also want the category $$Set$$ to be a full subcategory of $$MSet$$.

The obvious way to define a morphism $$(A,\sim_A)\to(B,\sim_B)$$ is as a map $$f\colon A\to B$$ such that $$\forall a,a'\in A\colon a\sim a'\implies f(a)\sim f(a')$$. One thing that bothers me with this definition is that if we consider equivalent elements as indistinguishable from the point of view of the multiset, then in general many set maps would induce "the same" morphism.

Next try is to simply take functions $$A/\sim_A \to B/\sim_B$$. This does not suffer from the issue above, but I am not satisfied with this either. If we consider the standard multisets then our morphisms are just functions of the underlying sets. What bothers me is that any information on the multiplicity is lost. I'd like for example to be able to define the notion of submultiset, that would come with a natural "inclusion map" that will take multiplicity into account.

The best I could come up with is this:

a morphism $$(A,\sim_A)\to(B,\sim_B)$$ is a set map $$A/\sim_A \to B/\sim_B$$ together with a family of inclusions $$[a]_{\sim A}\hookrightarrow f([a]_{\sim_A})$$.

Is this a good notion of morphism? Is it not too restrictive? I think we could instead ask for bijections $$[a]_{\sim A}\to f([a]_{\sim_A})$$, but that seems even more restrictive.

This is a problem from Aluffi's Algebra Chapter 0, where the author mentions that this is an "open-ended" exercise. So, I guess there is no single "right" definition of $$MSet$$.

I did not find a good reference on this topic. I would also like to know what are the applications of the theory of such multisets (I know that standard multisets are abound in combinatorics).

• Standard multisets abound in combinatorics, but maps between them generally don't. Multivalued maps are often modelled by spans. Aug 20, 2019 at 17:43
• I would go with your first try. Aug 20, 2019 at 21:36

This is typically a situation in which there no most natural way to do things. As long as your definition is indeed a category, it will be as good as mine, depending on the application in mind. (In that sense it is really not a good exercise from Aluffi, because it becomes a problem of set theory/combinatorics and not of category theory.)

(1) You could draw inspiration from the "standard multisets", where the most obvious way to define a morphism is as a morphism of the category $$\mathsf{Set}/\mathbb N$$, meaning a function that preserves multiplicity. Then of course multiplicity is quite more intricate in the case of "sets with an equivalence relation" where you need to count with cardinals instead of numbers: preserving multiplicity becomes preserving cardinality, and you can define a morphism as $$f: A/{\sim_A} \to B/{\sim_B}$$ such that for any $$a\in A$$, the set $$[a]_{\sim_A}$$ has the same cardinality as $$f([a]_{\sim_A})$$, meaning there is a bijection between them (just not naming which one).

(2) Now you could say that in the case of standard multisets, the number $$m(a)$$ for $$a\in A$$ is not so much about counting the appearance of $$a$$ than it is about having $$m(a)$$ names to refer to the object $$a$$ (namely $$a_1,\ldots,a_{m(a)}$$) and then a map between multisets owes to keep track of these names: a map $$f: (A,m) \to (B,n)$$ should not only map an element $$a$$ to an element $$b$$ with as many names, but also describe how to rename $$a_i$$ in one of the $$b_j$$. In that setting, a map of standard multisets $$(A,m)\to (B,n)$$ has to be defined as a map $$f: A\to B$$ together with permutations $$\sigma_a \in \mathfrak S_{m(a)}$$ for each $$a\in A$$. Mimicking this process in the infinite case, the "names" of $$[a]_{\sim_A}$$ are precisely the elements of $$A$$ that are in the class of $$a$$, and the maps based on the above interpretation are then maps $$f: A/{\sim_A} \to B/{\sim_B}$$ together with given bijections $$\phi_k : k \to f(k)$$ for each of the classes $$k\in A/{\sim_A}$$. Remark that these maps are equivalently these equivariant $$f:A \to B$$ (meaning $$a\sim a' \implies f(a)\sim f(a')$$) such that the restrictions $$f\mid_{[a]}: [a]_{\sim_A} \to [f(a)]_{\sim_B}$$ are bijections.

(3) You could now do one jump further and consider that it is acceptable to map a element $$a$$ with $$m(a)$$ names to an element $$b$$ with $$n(b)$$ names even if $$m(a)\neq n(b)$$ as long as you continue to keep track of to which of the $$b_j$$ is mapped each $$a_i$$. Then in the finite case maps $$(A,m)\to(B,n)$$ are just maps $$f: A\to B$$ together with maps $$\phi_a: \{1,\ldots,m(a)\} \to \{1,\ldots,n(f(a))\}$$. In the infinite case, it then should be defined as a map $$f: A/{\sim_A} \to B/{\sim_B}$$ together with maps $$\phi_k : k \to f(k)$$, or equivalently as equivariant maps $$A\to B$$ (and this is back your first try, but it seems much less worrying with that name-interpretation in mind).

Remark that all these are instances of the same process: they are (equivalent to) the Grothendieck construction of pseudofunctors of the form $$\mathsf{Set}\ni A\mapsto \mathbf C^A$$ for a category $$\mathbf C$$ whose objects are (finite) sets.

1. (finite) sets and a unique map $$A\to B$$ whenever $$A$$ has same cardinality than $$B$$,
2. (finite) sets and bijections
3. (finite) sets and functions

You can try other such $$\mathbf C$$ to find other definitions of a multiset category. As long as there is a unique map from the singleton to itself in $$\mathbf C$$, you should be able to embed $$\mathbf{Set}$$ as a full subcategory in the resulting Grothendieck construction.

And this is probably not the only way to construct a solution to the exercise (I have a small voice in my head saying "Bishop's setoids" but I know to little about that to see if it gives something acceptable here.)

I think the most natural thing to do is to consider $$MSet$$ not as a category but as a $$2$$-category. Specifically, a multiset is the same thing as a groupoid with at most one morphism between any two objects (elements of the multiset are objects and there is a morphism between two objects iff they are equivalent). So, we can consider multisets as a full sub-$$2$$-category of the $$2$$-category of categories. Concretely, this means a morphism of multisets is just a function that preserves the equivalence relation (that's a functor between the corresponding groupoids). A natural transformation between two such functions $$f$$ and $$g$$ is just a statement that $$f(x)\sim g(x)$$ for all $$x$$ in the domain. That is, the category of morphisms between two multisets is just another multiset (i.e., thin groupoid), where the elements are functions preserving the equivalence relation and the equivalence relation is $$f\sim g$$ iff $$f(x)\sim g(x)$$ for all $$x$$.

Note, though, that all of this is "evil" if you want to think of multisets as being actually different from sets. In particular, the (weak) $$2$$-category of multisets is equivalent to the $$2$$-category of sets where there are no non-identity $$2$$-morphisms, by sending each multiset to its set of equivalence classes. So any notions like "submultiset" which you define will necessarily be evil (i.e., not preserved by equivalences of (weak) $$2$$-categories).

• Isn't that just the first thing the OP tried, i.e., defining homomorphisms as maps between the quotients by the equivalence relations? Aug 20, 2019 at 17:42
• That's what the isomorphism classes of the morphisms in the $2$-category are, but not the morphisms themselves are. Aug 20, 2019 at 18:01
• The first thing OP tried was to define maps as functions which preserve the equivalence relation. Aug 20, 2019 at 20:16
• Right, but by considering it as a $2$-category you get to have not just those maps but also the natural equivalence relation on them. Aug 20, 2019 at 21:26