# Category theory with multisets

An alternative to the notion of multiset introduced in Section 2.2 of Aluffi Chapter 0 is obtained by considering sets endowed with equivalence relations; equivalent elements are taken to be multiple instances of elements 'of the same kind'. Define a notion of morphism between such enhanced sets, obtaining a category MSet containing (a 'copy' of) Set as a full subcategory. (There may be more than one reasonable way to do this! This is intentionally an open-ended exercise.) Which objects in MSet determine ordinary multisets as defined in Section 2.2 and how? Spell out what a morphism of multisets would be from this point of view. (There are several natural notions of morphisms of multisets. Try to define morphisms in MSet so that the notion you obtain for ordinary multisets captures your intuitive understanding of these objects.)

Well the obvious definition works: If $(A,\sim_A)$,$(B,\sim_B)$ are sets with equivalence relations, then define a morphism $(A,\sim_A)\to(B,\sim_B)$ to be a map $f:A\to B$ which respects the relations, i.e. $x\sim_A y \implies f(x) \sim_B f(y)$. It is readily verified that the composition of such morphisms is again a morphism and that the identity on $A$ is a morphism so that we get a category out of this.

The category of sets is embedded in this category of multisets by associating $A$ with $(A,=_A)$ where $=_A$ is the equality relation on $A$, i.e. all distinct elements are unrelated by $=_A$. Any map $A\to B$ obviously respects these relations such that $A\mapsto (A,=_A), f\mapsto f$ become a functor. This functor is the desired embedding of Set into MSet

NOTE: I first thought of posting this as a reply to @JohannasHahn's answer, but it got too long.

At the risk of being too pedantic, I would say that our morphisms must be triplets: $(f,\sim_A,\sim_B)$, since technically sets of morphisms should be disjoint [Aluffi, Def. 3.1 on pg.19]. Alternatively we can define a morphism $(A,\sim_A)\rightarrow(B,\sim_B)$ to be a map $f:(B/\sim_B)\rightarrow(A/\sim_A)$.

The last (and vaguest) part of the question remains unanswered:

Which objects in $\mathsf{MSet}$ determine ordinary multisets as defined in §$2.2$ and how? Spell out what a morphism of multisets would be from this point of view. (There are several natural notions of morphisms of multisets. Try to define morphisms in $\mathsf{MSet}$ so that the notion you obtain for ordinary multisets captures your intuitive understanding of these objects.)

The definition for multisets given in §$2.2$ is a map, $m:A\rightarrow\mathbb N^*$, from a set $A$ to the positive integers. This map can be viewed as a multiset, where every element $a\in A$ appears $m(a)$ times.

I have not been able to answer the above in a satisfactory way with either of the two definitions for morphisms in $\mathsf{MSet}$ we have presented here. Any thoughts?

• My idea is that according §2.2 a multiset may contain only finitely many copies of the same element. If we consider the category $\mathsf{MSet}$ suggested by @JohannesHahn, then some of the objects contain infinitely many equivalent elements (copies). Therefore $(A,\sim_A)$ determines an ordinary multiset if all equivalence classes in $A/ \sim_A$ are finite. In that case we can take $m : A/ \sim_A \to \mathbb{N}, \ m([a]) = | [a] |$. And then, I suppose, $A/ \sim_A \rightarrow B/ \sim_B$ is a "morphisms of multisets from this point of view". – user128245 Aug 30 '17 at 10:38