# Start a new discussion

## Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

## Site Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentRowNumber1.
• CommentAuthorEric
• CommentTimeOct 14th 2009

I asked a question on multiset.

If $X = \{1,1,2\}$ and $Y = \{1,1,3\}$, is $X\cap Y = \{1,1\}$?

• CommentRowNumber2.
• CommentAuthorTodd_Trimble
• CommentTimeOct 14th 2009

I answered you over at multiset. It's $\{1, 1\}$.

• CommentRowNumber3.
• CommentAuthorMike Shulman
• CommentTimeOct 14th 2009

I asked another question at multiset.

• CommentRowNumber4.
• CommentAuthorEric
• CommentTimeOct 14th 2009
• (edited Oct 14th 2009)
I added some references to multiset that might answer your question

http://obelix.ee.duth.gr/~apostolo/Articles/MathMSet.pdf

http://obelix.ee.duth.gr/~apostolo/Articles/mset.pdf
• CommentRowNumber5.
• CommentAuthorEric
• CommentTimeOct 14th 2009
PS: Instead of making you dig for it, I added the definition of the category MSet to multiset.
• CommentRowNumber6.
• CommentAuthorTobyBartels
• CommentTimeOct 15th 2009

I have added my thoughts to the discussion.

• CommentRowNumber7.
• CommentAuthorEric
• CommentTimeOct 21st 2009
• (edited Oct 21st 2009)
This comment is invalid XHTML+MathML+SVG; displaying source. <div> <p>I added a question to <a href="http://ncatlab.org/nlab/show/multiset">multiset</a></p> <blockquote>What would a colimit over an MSet-valued functor <img src="https://nforum.ncatlab.org/extensions//vLaTeX/cache/latex_1dac663271b525f37d22d6ed48334c38.png" title="F:A\to MSet" style="vertical-align: -20%;" class="tex" alt="F:A\to MSet"/> look like?</blockquote> </div>
• CommentRowNumber8.
• CommentAuthorEric
• CommentTimeOct 27th 2009

I proposed an alternative definition for the intersection of multisets, but would be interesting in hearing arguments for and (more likely) against.

• CommentRowNumber9.
• CommentAuthorEric
• CommentTimeOct 28th 2009
• (edited Oct 28th 2009)

Thanks Toby for making me look at a simple example to see the depth of nonsense I was spewing about intersections :)

I think I am happy with it now, but while convincing myself I came back to an issue that has bothered me. On multiset, I think you and I went back and forth on whether we should allow $\mu = 0$ (I removed "nonzero" from "nonzero cardinal numbers" and I think you put it back). In those papers by Syropolous, he allows $\mu = 0$ and I kind of think we should as well.

If we were to allow $\mu = 0$, then I would define

$\mathcal{X}\backslash\mathcal{Y} = \langle X\cup Y,max(0,\mu_X-\mu_Y)\rangle.$

This only makes sense if we allow $\mu = 0$.

I just doodled a proof that with this definition of set difference we have

$\mathcal{X} + \mathcal{Y} = \mathcal{X}\backslash\mathcal{Y} + \mathcal{X}\backslash\mathcal{Y} + 2\mathcal{X}\cap \mathcal{Y}.$

What is the reason for requiring the cardinal numbers to be nonzero? Can we change it to allow zero?

PS: Thanks for removing the query box. I was going to remove it after I was sure you saw it, but only now remembered I could have removed it and told you about the change here.

• CommentRowNumber10.
• CommentAuthorEric
• CommentTimeOct 28th 2009
• (edited Oct 28th 2009)

In the simple example you gave, we have

$\mathcal{X} = \{1,1,2,3\}$ and $\mathcal{Y} = \{1,1,2,2\}$

so that

$\mathcal{X}+\mathcal{Y} = \{1,1,1,1,2,2,2,3\}.$

With the above definition of set difference (which requires allowing $\mu = 0$) we'd have

$\mathcal{X}\backslash\mathcal{Y} = \{3\},$ $\mathcal{Y}\backslash\mathcal{X} = \{2\},$

and

$\mathcal{X}\cap\mathcal{Y} = \{1,1,2\}.$

Note that

$2\{1,1,2\} = \{1,1,1,1,2,2\}$

so that

$\{1,1,1,1,2,2,2,3\} = \{3\} + \{2\} + 2\{1,1,2\}.$
• CommentRowNumber11.
• CommentAuthorTobyBartels
• CommentTimeOct 28th 2009
• (edited Oct 28th 2009)

The reason for restricting attention to nonzero cardinal numbers is to make it unambiguous what is the underlying set of the multiset. If you remove ‘nonzero’ from the definition on the page, then $(\{1,2,3\}, (2,1,0))$ and $(\{1,2\}, (2,1))$ become different, even though they should both be $\{1,1,2\}$ (whatever that is).

• CommentRowNumber12.
• CommentAuthorTobyBartels
• CommentTimeOct 28th 2009

Really, this comes from trying to make a material theory of multisets to match a material theory of sets. You get a clean theory by doing one of the following:

1. Fix a universe $U$ and considering only multisets whose elements are elements of $U$. Then a multiset is simply a function $\mu\colon U \to Card$ (or $\mu\colon U \to \mathbb{N}$ for locally finite multisets), which may very well take $0$ as a value. Note that multisets form a rig, with the additive identity being the empty multiset, whose multiplicity function always takes the value $0$; this rig may be identified with $Card^U$ (or $\mathbb{N}^U$).
2. Define a multiset as a surjection $\mathcal{X} \to X$, modulo an appropriate notion of isomorphism. Then every element of $X$ has a nonzero multiplicity, which is the cardinality of its fibre in $\mathcal{X}$. We can equivalently define this multiset as the set $\mathcal{X}$ equipped with an equivalence relation, so that a multiset is a setoid. (But there are at least two choices of the definition of morphism and hence of isomorphism.) Note that now multisets form a category.

All of that stuff about intersections and inner products and so forth can only refer to (1). So we might as well allow $0$ as a multiplicity, but then we should do everything relative to $U$. But all of the stuff about morphisms of multisets is about (2).

It's probably more confusing than it's worth to try to mix (1) and (2). I'd only ever seen multisets used for (1) until I saw those references about morphisms of multisets on the Café. But if you come from a material (ZFC-like) conception of sets, then it's very natural to mix them, which means that you need to keep adjusting the underlying set of a multiset, to keep it appropriate for (2), whenever you do an operation appropriate for (1). And that's what we've been doing on multiset.

And you can do this! You can define $\mathcal{X} \setminus \mathcal{Y}$ to have the right underlying set such that $\mu$ takes only nonzero values; I just mentioned how at multiset.

• CommentRowNumber13.
• CommentAuthorEric
• CommentTimeOct 28th 2009
• (edited Oct 28th 2009)

Thanks. So what would you suggest we do? Mix (1) and (2) or choose one? For the nLab, (2) almost seems for appropriate.

I'm not sure which one I'm using when I write $\langle X,\mu_X\rangle$. Is it closer to (2) with $F:\mathcal{X}\to X$ and $\mu_X(x) = |F^{-1}(x)|$? I was trying to shy away from introducing a universal set.

What is the best notation? I can rewrite the examples once a notation is settled.

Sometimes I'm even tempted to treat multisets as vectors and write things like

$\mathcal{X} = \sum_{x\in X} \mu_X(x) \{x\}.$

By the way, did you see my extremely speculative Colimit as a Linear Regression of Multisets?

Edit: Oh, by the way, I moved the "Discussion" to the bottom because "Examples" and "References" were buried at the bottom of the page. I usually think of "Discussion" as being an addendum that appears at the end while "Examples" and "References" are part of the main content. No big deal. I really just wanted the Example to appear before the long discussion and took the References along for the ride.

• CommentRowNumber14.
• CommentAuthorTobyBartels
• CommentTimeOct 29th 2009

So what would you suggest we do?

I think:

Note the difference between (1) and (2), explain why and how one might conflate them, then cover things separately. Possibly this means eventually branching to separate pages.

I'm running of time to be online now, but I can do this later.

• CommentRowNumber15.
• CommentAuthorEric
• CommentTimeOct 29th 2009

I started some notes at ericforgy:Multiset. Feedback welcome!

• CommentRowNumber16.
• CommentAuthorEric
• CommentTimeOct 29th 2009
• (edited Oct 29th 2009)

When I was writing the section "How can we settle this?" at ericforgy:Multiset, I got a sense of deja vu. I've only begun reading Goldblatt's very cool book, but I was wondering if there was some way we can interpret the cardinality

$\mu_X:U\to Card$

as a subobject classifier $\Omega$ for some topos?

Instead of Set, maybe some topos in a category of elements of some universe $U$? Or something...

Edit:

I guess another similar question is can we think of Set as a topos on a category of elements with subobject classifier

$\chi_X:U\to\{0,1\}.$

Since objects in the category of elements are, well, "elements" then I was thinking the subobject classifier tells you if the element is in the set $X$.

Then

$\mu_X:U\to\mathbb{N}$ tells you not only whether the element is in the multiset, but also tells you how many times it appears.

• CommentRowNumber17.
• CommentAuthorEric
• CommentTimeOct 29th 2009
• (edited Oct 29th 2009)
This comment is invalid XML; displaying source. <p>I would love to have a copy of this paper:</p> <p><a href="http://cat.inist.fr/?aModele=afficheN&cpsidt=13517583">The category of M-Sets</a></p> <p>Abstract. A topos is a category which looks and behaves very much like the category of sets, and so it may be thought of as a universe for mathematical discourses. One of the very useful topoi in many branches of mathematics as well as in computer sciences is the topos MSet, of sets with an action of a monoid M on them. It is well known that MSet, being isomorphic to the functor category SetM, is a topos. Here, we explicitly give the ingredients of a topos in MSet and investigate their properties for the working scientists and computer scientists. Among other things, we give some equivalent conditions, such as the left Ore condition, to <img src="https://nforum.ncatlab.org/extensions//vLaTeX/cache/latex_e114a9b563636b5006b7f2b0e27a5e45.png" title="\Omega" style="vertical-align:-20%;" class="tex" alt="\Omega" />, the subobject classifier of MSet, being a Stone algera. Also the free and the cofree objects, as well as, limits and colimits are discussed in MSet.</p> 
• CommentRowNumber18.
• CommentAuthorTodd_Trimble
• CommentTimeOct 30th 2009

It sounds like a lot of that paper would be in the way of a very good exercise for someone who is starting to learn topos theory. It might even be a good exercise to carry out here on the Lab: learning to do topos calculations just with one's bare hands and brain.

• CommentRowNumber19.
• CommentAuthorEric
• CommentTimeOct 30th 2009
• (edited Oct 30th 2009)

I would start a "journal club"-like page if I could somehow manage to get my hands on the paper (hint) :)

Edit: Argh. I just realized I packed away my copy of Goldblatt and it will be inaccessible for a few weeks.

• CommentRowNumber20.
• CommentAuthorTodd_Trimble
• CommentTimeOct 30th 2009

We don't even need the paper or Goldblatt; we can get started right now without them. For example, what is M-Set exactly, and what does the author mean by saying that M-Set is isomorphic to Set^M? Then: how does one calculate finite products in M-Set/Set^M? (There's a good chance you know this already.)

We can go on from there to discuss general limits and colimits in M-Set, cartesian closure, the subobject classifier, and so on. This could be fun and a very good learning experience, and there are people right here who know this material rather well.

• CommentRowNumber21.
• CommentAuthorEric
• CommentTimeOct 30th 2009

I have a vague enough understanding of multisets (which I hope are related to M-sets) to be able to perform some computations, but I'm still struggling with the right way to think of them. You can get a feel for what I know and don't know from

ericforgy:Multisets

where I am trying to get a handle on "what are multisets exactly". I don't know :)

(feedback welcome!)

You can also see some confusion (on my part at least) of what a morphism should be between multisets at multiset.

In the meantime, I created a stub for M-Set where we can put some definitions and stuff and started a page

• CommentRowNumber22.
• CommentAuthorEric
• CommentTimeOct 30th 2009

Oh no! According to Todd's comment on Understanding M-Set, it seems multisets may not be objects in M-Set.

I get distracted easily enough already. What I really want to understand is the category of multisets. In the references at multiset, they denote the category of multisets "MSet". Oh no!

• CommentRowNumber23.
• CommentAuthorTodd_Trimble
• CommentTimeOct 30th 2009

Ah well. I responded to what you wrote at Understanding M-Set at any rate.

• CommentRowNumber24.
• CommentAuthorEric
• CommentTimeOct 30th 2009

Thanks!

I would really LOVE to go through all this stuff. Especially while I have your attention! :)

I just wish we could find a category closer to my heart to do all those exercises. I wouldn't even mind doing an "Understanding Set" :) That might actually be a really good idea.

Maybe M-Set is close to my heart and I just don't realize it yet. Almost everything I'm tinkering with these days is related to multisets though (with a vague hope that they will help me with a speculative idea of mine

Colimit as a Linear Regression of Multisets

• CommentRowNumber25.
• CommentAuthorTobyBartels
• CommentTimeOct 30th 2009

I changed the text at M-Set to refer to the topic of Understanding $M$-$Set$, but maybe we should move it to MSet for the category of multisets.

• CommentRowNumber26.
• CommentAuthorEric
• CommentTimeOct 30th 2009
• (edited Oct 30th 2009)

I thought that multisets were an example, but I am not sure anymore. If they are not, then I'd like to reserve M-Set or MSet for the category of multisets if possible.

• CommentRowNumber27.
• CommentAuthorTobyBartels
• CommentTimeOct 30th 2009

Well, ‘$M$-$Set$’ (or $M$ $Set$, with a thin space) is extremely common for the category of $M$-sets, relative to a fixed monoid $M$. It's shear luck that nobody has wanted to make that page yet. So I would use ‘$MSet$’ (no space) for the category of multisets.

How do M-Set and MSet look now?

• CommentRowNumber28.
• CommentAuthorEric
• CommentTimeOct 30th 2009
• (edited Oct 30th 2009)

Oh. Ok. We should probably call the category of multisets something else then to avoid confusion. Instead of MSet (with no space), which is too close to M-Set, how about "MultiSet" or "Bags" as Syropoulos calls it?

• CommentRowNumber29.
• CommentAuthorTodd_Trimble
• CommentTimeOct 30th 2009

I like MultiSet or Multiset (if we can agree on what the morphisms are). Bags I like less, but that's just me.

• CommentRowNumber30.
• CommentAuthorEric
• CommentTimeOct 30th 2009

Cool. I'll wait to create MultiSet until the morphism issue is settled.

Any ideas on the best n-Lab-esque way to define the category of multisets? Arrow theoretically somehow?

• CommentRowNumber31.
• CommentAuthorTobyBartels
• CommentTimeOct 30th 2009

I already created it, at MSet, so I'll just move it now.

But yeah, there are at least two interesting ways to define the morphisms.