What is the "correct" category of multisets

Question

During seminar the other day, when speaking about subobject classifiers, I asked if the subobject classifier for the category of multisets would have integer truth values, corresponding to the number of times and element is in the set. We attempted to show this, but quickly realized that we were not even sure of the "correct" category for multisets.

To clarify, when I say correct I want my category to

1. Have objects identified by multisets
2. Have maps between the multisets be on the level of elements in the multiset, and forget the order of those elements, e.g. there is only one map {111223}->{55}
3. The subobject classifier will behave as I had hoped, with {1} having truth value 3 in {111}

My question is;

Can you construct a category satisfying these properties?

Thanks in advance!

EDIT: First, sorry about not checking nLab, I forget about that site far too often. Second, I should say that I have a little bit of motivation for my property two. So let me clarify what I meant in property two. Given a multiset, it can be thought of as a pair $S\times\mathbb{N}$ for a set $S$. Now, when considering morphisms between multisets I want the maps $f,g:\lbrace 1122\rbrace\rightarrow\lbrace34\rbrace$ such that $f$ sends

$\begin{eqnarray*} 1&\mapsto& 3,\\ 1&\mapsto& 4,\\ 2&\mapsto& 3,\\ 2&\mapsto& 4\\ \end{eqnarray*}$

and $g$ sends

$\begin{eqnarray*} 1&\mapsto& 4,\\ 1&\mapsto& 3,\\ 2&\mapsto& 4,\\ 2&\mapsto& 3\\ \end{eqnarray*}$

to be the same morphism. But if $h$ sends

$\begin{eqnarray*} 1&\mapsto& 4,\\ 1&\mapsto& 4,\\ 2&\mapsto& 4,\\ 2&\mapsto& 3\\ \end{eqnarray*}$

then $h$ is not the same as $g$ or $f$. Further I would like it such that $\lbrace 112\rbrace$ is not a subobject of $\lbrace 12\rbrace$ but it is a subobject of $\lbrace 11122\rbrace$.

Hopefully this will clear it up.

Answer 1

For purposes not obviously related to the question we (Ekedahl and Salomonsson - Strict polynomial functions and multisets) considered the following definition of maps of (finite) multisets: In the case of sets a map $S\rightarrow T$ is a subset $\Gamma\subseteq S\times T$ such that the projection on the first factor $\Gamma\rightarrow S$ is a bijection. Let us say that a map $f\colon S\rightarrow T$ of the sets underlying two multisets is a multijection if $\mu(t)=\sum_{f(s)=t}\mu(s)$ for all $t\in T$ (a bijection is a map such that the cardinality of a fibre over $t$ is equal to the cardinality of $\{t\}$). Composites of multijections are then multijections and they form a category (not a groupoid though). We can then define a multimap $S \rightarrow T$ to be a submultiset $\Gamma$ of the multiset product $S\times T$ such that the projection on the first factor is a multijection. This seems to fit with the examples given in the question. The problem is that composition of multimaps becomes multivalued as there will be ambiguities. One can solve this by looking at all possible composites making the composite a multiset of multimaps (technically we did this rather by constructing a category enriched in abelian monoids whose monoid of morphisms $S \rightarrow T$ was the free abelian monoid on the multimaps, but elements in this free monoid corresponds exactly to multisets of multimaps and the basis of a free abelian monoid can be canonically recovered from the monoid).

If this approach is to be used to deal with the question one would have to set up a theory of categories with multivalued composition. I haven't thought at all about the problem of putting this on an abstract enough foundation so that one can even speak of subobject classifiers (multitoposes anyone?).

Answer 2

According to the way I understand your conditions, I think the answer is No. In particular, condition 2 seems to suggest that there should be unique maps {1}->{111} and {111}->{1}, and also that those maps be inverses of each other (since there is only one map {1}->{1} and only one {111}->{111}). Hence the map {1}->{111} is an isomorphism, so its truth value is "true" regardless of whether the latter multiset has three or any other number of 1s.

Edited to add: To me a very natural candidate for the category of multisets would be the category of sets equipped with an equivalence relation, whose morphisms are functions on the underlying set that preserve the equivalence relation. In other words, the category whose objects are surjections A->A' and whose morphisms from (A->A') to (B->B') are pairs of maps A->B and A'->B' making the square commute.

The idea is that for a multiset like {1122}, the set A has four elements (like the multiset should) and the set A' only has two elements (like the underlying set {12} does), and the surjection A->A' tells you which elements of A are "the same" and which are different. The commuting square condition tells you that if two elements are equal, so are their images under any map. (So there's no map from {55} to {12} sending one 5 to 1 and the other to 2. However, there are two distinct maps from {5} to {55}.)

This category does have small limits, and the monomorphisms from (A->A') to (B->B') are the ones whose underlying map A->B is injective. However, I don't know whether this category has a subobject classifier, or what it might look like if it exists.

Answer 3

I suspect that the notion of "multiset" is actually ambiguous. For instance, different notions will be appropriate when talking about bosons vs. fermions vs. distinguishable (but intrinsically identical) particles. Ultimately, I suspect that if you really want there to be a reasonable category of multisets, you should assume that the multiple copies of a given element are distinguishable (though identical). So I'd be led to one of the following two candidates for the category of multisets:

1. The category $Set^\to$ of maps of sets. An object consists of two sets $A,B$ and a function $f: A \to B$; a morphism is a commuting square of maps.

2. The category $Set^{epi}$ of surjective maps of sets. This is the full subcategory of $Set^\to$ where $f: A \to B$ is required to be surjective.

To be clear, if $A \to B$ is an object of one of these categories, we are thinking of it as a multiset whose elements are the elements $b \in B$, with multiplicity given by the size of the fiber $f^{-1}(b) \subseteq A$. The passage from (1) to (2) is motivated by the idea that if $b \in B$ occurs with multiplicity 0, then we shouldn't think of $b$ as occurring in $B$ at all. The category $Set^{epi}$ of case (2) is equivalent to the category of equivalence relations suggested by Owen Biesel.

In case (1), we are working with the category of presheaves on the arrow category (a Grothendieck topos) and we can calculate the subobject classifier $\Omega$ in the standard way. It turns out that $\Omega$ is the multiset $\{110\}$, with the universal subobject $1 \to \Omega$ picking out one of the copies of $1$.

In case (2), we are dealing with a full subcategory $Set^{epi}$ of case the category $Set^\to$ from case (1), but I'm pretty sure this category of multisets doesn't have pullbacks. Nevertheless, any pullback square in $Set^\to$ whose objects happen to lie in $Set^{epi}$ will still be a pullback in $Set^{epi}$, so there is a non-negligible supply of pullbacks, and it's conceivable there might be a subobject classifier. But $\Omega$ from case (1) is not a subobject classifier -- it classifies subobjects in $Set^\to$, and there are almost always more of these than subobjects in $Set^{epi}$. So I don't think this category has a subobject classifier, though I wouldn't claim to have a proof.

Answer 4

This is all just off the cuff, so it might not work at all, and even if it it does, it's probably too complicated.

I think Owen Biesel is right to say that the answer is no as stated, so I think condition 2 ought to be dropped. Assuming that a multiset can only have finitely many copies of each element (as your desire for integer truth values seems to suggest) I think you could have the objects be sets of pairs (x,n) where x is a set and n is a nonnegative integer (so kind of like the elements of a tagged disjoint union) with the property that, if (x,n) is in the set, then so is (x,m) for any m≤n, and for which only finitely many "copies" of the same element appear. A morphism $f:S\to T$ is an equivalence class of set functions with the following property: take $x\in S$, and consider the sequence of elements $f(x,0),f(x,1),\ldots$. This sequence should have the property that, for each $y\in Y$, the appearances of y in the sequence occur in nondecreasing order with no gaps. Two functions are the same if they differ by permuting the indices in the domain.

For example, if this definition does what I hope it does, there are two functions from {x,x} to itself, namely the identity and the one which sends (x,0) and (x,1) to (x,0). I think this at least solves the isomorphism problem; I'm pretty sure that the only isomorphic multisets will be the ones that "ought" to be isomorphic.

I don't think this makes the subobject classifier behave like you'd want, but I'm not sure you'd actually want it to. The integers seem like a bad candidate, because there's nothing "special" about the element 79 as opposed to the element 3; the "truth" map can only pick out one element. I think the way to make it work might be to drop the finiteness assumption and use {0,1,1,...} as the classifier.

EDIT: I'm pretty sure this actually doesn't work; see the comments to the question.

Answer 5

Arguably, the thing that generalizes best from sets to multisets isn't the category Set of functions between sets, but the category Rel of relations between sets. This is clearly a closed monoidal category, since we can represent relations between multisets A and B as a multiset of tuples of elements of A and B, and this is compatible with composition of relations.

This is also the underlying category used by SQL in most relational databases, which also gives you JOIN to represent pullbacks and UNION ALL to represent categorical sums, so it is very well studied.