Not signed in (Sign In)

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

  • Sign in using OpenID

Site Tag Cloud

2-categories 2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry bundles calculus categories category category-theory chern-weil-theory cohesion cohesive-homotopy-theory cohesive-homotopy-type-theory cohomology colimits combinatorics complex-geometry computable-mathematics computer-science connection constructive constructive-mathematics cosmology definitions deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry differential-topology digraphs duality elliptic-cohomology enriched fibration finite foundations functional-analysis functor galois-theory gauge-theory gebra geometric-quantization geometry goodwillie-calculus graph graphs gravity grothendieck group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory history homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory internal-categories k-theory lie-theory limit limits linear linear-algebra locale localization logic mathematics measure-theory modal-logic model model-category-theory monoidal monoidal-category-theory morphism motives motivic-cohomology multicategories noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topological topology topos topos-theory type type-theory universal variational-calculus

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

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • 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

    Understanding M-Set.

    • 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.

Add your comments
  • Please log in or leave your comment as a "guest post". If commenting as a "guest", please include your name in the message as a courtesy. Note: only certain categories allow guest posts.
  • To produce a hyperlink to an nLab entry, simply put double square brackets around its name, e.g. [[category]]. To use (La)TeX mathematics in your post, make sure Markdown+Itex is selected below and put your mathematics between dollar signs as usual. Only a subset of the usual TeX math commands are accepted: see here for a list.

  • (Help)