18
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ 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"? $\endgroup$ Apr 17, 2010 at 20:24
  • 2
    $\begingroup$ 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)). $\endgroup$
    – user2734
    Apr 17, 2010 at 21:34
  • $\begingroup$ Am I correct in assuming you want {1,1} $\not\cong$ {1,2}, and {1,1} $\not\cong$ {1}? $\endgroup$
    – S. Carnahan
    Apr 17, 2010 at 22:57
  • 3
    $\begingroup$ 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. $\endgroup$ Apr 18, 2010 at 4:15
  • 1
    $\begingroup$ @Nicolas: The trouble is that the two conflicting ways of thinking about the multiple elements means that composition can't work: take the unique map from {5} to {55}, and compose it with the map {55}- >{12} sending one of the 5s to 1 and the other to 2. We get a map {5}->{12} - What is its image? This problem is irreparable: if {55} and {5} are both terminal, they are isomorphic, but the former has three distinct maps to {12} and the latter only two. $\endgroup$ Apr 18, 2010 at 4:55

4 Answers 4

6
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Apr 17, 2010 at 22:20
  • $\begingroup$ 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? $\endgroup$
    – B. Bischof
    Apr 18, 2010 at 4:00
  • $\begingroup$ 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. $\endgroup$
    – B. Bischof
    Apr 18, 2010 at 4:08
  • $\begingroup$ @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/… $\endgroup$
    – user2734
    Apr 18, 2010 at 13:33
  • 2
    $\begingroup$ This category doesn't have a subobject classifier. If it did, it would be balanced. The epics are squares whose underlying map $A\to B$ is surjective. Therefore $\{a_1,b_1\}\to \{a,b\}$ has an epic mono to $\{c_1,c_2\}\to\{c\}$, yet these two are not isomorphic. $\endgroup$
    – MTyson
    Nov 24, 2018 at 16:14
6
$\begingroup$

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?).

$\endgroup$
1
  • 1
    $\begingroup$ A trivial remark: the first category you introduce is a subcategory of the category of probability spaces with probability-preserving morphisms, restricted to the case of finite sets in which the mass of every point is a natural number. $\endgroup$
    – Terry Tao
    Jul 17, 2020 at 21:30
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Ah, I guess most of this was discussed in the comments to Owen Biesel's question. In particular, I was wrong to say that $Set^{epi}$ doesn't have pullbacks. Anyway, what's new here is the computation of the subobject classifier in $Set^{\to}$. $\endgroup$
    – Tim Campion
    Jul 18, 2020 at 14:24
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – B. Bischof
    Apr 18, 2010 at 4:06
  • $\begingroup$ Are you thinking this is just Sets/$\mathbb{N}$? I think the maps are different. $\endgroup$ Apr 18, 2010 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.