# What is the “correct” category of multisets

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?

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.

-
Interesting question! I would personally benefit from a little more information on your condition #2 above regarding maps. What does "on the level of elements" mean, and how does this imply that there is only one map {111223} -> {55} in the category? Does it mean that 1, 2, and 3 must all map to 5, forgetting their multiplicity, and that 5 then "becomes doubled"? – Manny Reyes Apr 17 '10 at 20:24
Just wanted to note that there is a discussion in nLab regarding the "right" definition of the category of multisets (ncatlab.org/nlab/show/multiset). AFAICT, subobject classifiers are not considered, but there is some discussion (and references) regarding the "right" definition of arrows in that category (if you are willing to consider alternatives to your (2)). – user2734 Apr 17 '10 at 21:34
+1 good questions – Shizhuo Zhang Apr 17 '10 at 21:51
Am I correct in assuming you want {1,1} $\not\cong$ {1,2}, and {1,1} $\not\cong$ {1}? – S. Carnahan Apr 17 '10 at 22:57
It looks to me like the problems are arising from a sort of inconsistency in how you're thinking about the elements with multiplicity. For {1122}, the two 1s are different enough that you can send one to a 3 and the other to a 4. However, the two 5s in {55} are the same, so you can't tell the difference between any two maps from {111223} to it. (From there it's just a short hop to {55} being a terminal object, hence isomorphic to every other terminal object, including {5}.) I advise you think very carefully about what sort of morphisms a particular application calls for, and go from there. – Owen Biesel Apr 18 '10 at 4:15

For purposes not obviously related to the question we (arXiv:math/0412287) 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?).

-

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.

-
Moreover, it seems that your condition 2 suggests that from the Category's point of view, you can't tell a multiset from its underlying set (throw away multiplicities). I think better is to have some sort of "category enriched in multisets", but that begs the question. – Theo Johnson-Freyd Apr 17 '10 at 22:20
Yes Owen this looks correct :/ Which is disappointing. I would like to preserve property two or something similar for the reason that I added. @Theo, any idea how to make that clear? – B. Bischof Apr 18 '10 at 4:00
I will not accept this answer just yet, in hopes of somebody fixing this issue and producing a category that is as close as possible to what I want. If nobody can come up with something, I will accept this, since you have really answered my original question. – B. Bischof Apr 18 '10 at 4:08
@Owen Biesel:Your suggested category of multisets is a subcategory of $\mathbf{Sets}^{\mathbf{2}}$, where $\mathbf{2}$ is the category of 2 distinct objects and one arrow between them (you consider only surjective functions, hence a subcategory). Now, $\mathbf{Sets}^{\mathbf{2}}$ has a subobject classifier (see pp. 105--106 of Mac Lane). I wonder whether this can be used somehow for your subcategory. [Ref to Mac Lane:books.google.com/… – user2734 Apr 18 '10 at 13:33
@unknown(google): That category is just the category $Arr(Sets)$. Unless the inclusion functor admits a lex left-adjoint (thereby making it a topos as well), I don't see how having the subobject classifier in the big category would help. – Harry Gindi May 6 '11 at 13:35

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.

-
This is one definition that we tried, but if I understand what you are saying, this is a slice category of sets, which give the same subobject classifier. In response to the integers not being a good subobject classifier; what about the time till truth Subobject classifier? This is very interesting based on the interpretation. I want to see what kind of topoi we get from certain SO classifiers like the integers or the reals. I think this is very strange. I would also like to see an SO classifier even more bizzare than just a well-ordered set. Especially because it is not just time till truth. – B. Bischof Apr 18 '10 at 4:06
Are you thinking this is just Sets/$\mathbb{N}$? I think the maps are different. – Nicolas Ford Apr 18 '10 at 4:41