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-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry beauty bundle bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics comma complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched etcs fibration foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie lie-theory limits linear linear-algebra locale localization logic manifolds mathematics measure measure-theory modal modal-logic model model-category-theory monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages 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 string string-theory subobject superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory 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.
    • CommentAuthorDmitri Pavlov
    • CommentTimeApr 1st 2021

    Removing an old discussion:

    Is there a reason that you moved these references up here? We need them especially for the stuff about morphisms below. —Toby


    Eric: What would a colimit over an MSet-valued functor F:AMSetF:A\to MSet look like?

    Toby: That depends on what the morphisms are.

    Eric: I wonder if there is enough freedom in the definition of morphisms of multisets so that the colimit turns out particularly nice. I’m hoping that it might turn out to be simply the sum of multisets. According to limits and colimits by example the colimit of a Set-valued functor is a quotient of the disjoint union.

    Toby: I think that you might hope for the coproduct (but not a general colimit) of multisets to be a sum rather than a disjoint union. Actually, you could argue that the sum is the proper notion of disjoint union for abstract multisets.

    diff, v38, current

    • CommentRowNumber2.
    • CommentAuthorDmitri Pavlov
    • CommentTimeApr 1st 2021

    Removing an old discussion about morphisms of multisets (what is the outcome, anyway?)


    What is a function between multisets? I would be inclined to say that for multisubsets of an ambient universe UU considered as objects of Set/USet/U, a function from BUB\to U to BUB'\to U would be an arbitrary function BBB\to B' (not necessarily commuting with the projections to UU). But this doesn’t work if a multisubset of UU is an isomorphism class in Set/USet/U rather than merely an object of it. – Mike Shulman

    Eric: This definition is taken from Syropoulos:

    +– {: .un_defn}


    Category MSet\mathbf{MSet} is a category of all possible multisets.

    1. The objects of the category consist of pairs (A,P)(A, P), where AA is a set and P:ASetP:A\to Set a presheaf on AA.
    2. If (A,P)(A,P) and (B,Q)(B,Q) are two objects of the category, an arrow between these objects is a pair (f,λ)(f,\lambda), where f:ABf:A\to B is a function and λ:PQf\lambda:P\to Q\circ f is a natural transformation, i.e., a family of functions.
    3. Arrows compose as follows: suppose that (A,P)(f,λ)(B,Q)(A,P)\stackrel{(f,\lambda)}{\to}(B,Q) and (B,Q)(g,μ)(C,R)(B,Q) \stackrel{(g,\mu)}{\to}(C,R) are arrows of the category, then (f,λ)(g,μ)=(gf,μ×λ)(f,\lambda)\circ (g,\mu) = (g\circ f, \mu\times\lambda), where gfg\circ f is the usual function composition and μ×λ:PR(gf)\mu\times\lambda:P\to R\circ (g\circ f).
    4. Given an object (A,P)(A,P), the identity arrow is (id A,id P)(id_A, id_P). =–

    The last part of the definition is a kind of wreath product (see [4]). However, it is not clear at the moment how this definition fits into the general theory of wreath products.

    Mike Shulman: Huh. So his definition takes a multiset to assign a set to every element, rather than a cardinality to every element, so that the multisubsets of UU are exactly objects of Set/USet/U. I’m surprised, though, that with his definition the only functions {1,1}{2,3}\{1,1\} \to \{2,3\} are constant; why can’t I send the two copies of 11 to different places?

    Toby: If you could, then {1,1}\{1,1\} and {2,3}\{2,3\} would be isomorphic in this category, and we'd just have SetSet back again.

    I find Mathematics of Multisets especially interesting for its distinction between multisets with distinguishable objects and ’pure’ multisets with indistinguishable objects. The definition above involving cardinal numbers gives us ’pure’ multisets, unlike the objects of the category MSetMSet above.

    Normally, one only needs multisubsets of a given set, and one is not interested in functions between them. But if one wants to make a category of abstract multisets, then the pure and impure versions are different!

    Mike Shulman: Whereas his definition makes the category of multisets equivalent to Set 2Set^{\mathbf{2}}. Is that better? [Note here that 2 is the walking arrow.—Anonymous]

    I don’t find it wrong that the category of multisets would be equivalent to SetSet, since SetSet only sees “structural” properties of sets, and the fact that two elements of a set are “the same” (which is what distinguishes {1,1}\{1,1\} from {2,3}\{2,3\}) is a nonstructural property that only makes sense in the context of sub-multisets of some ambient set.

    Toby: At least Set 2Set^{\mathbf{2}} is different from SetSet. And how do you decide whether being ’the same’ is a structural property of a multiset? We're trying to take an idea that originally applied only to collections of elements from a fixed universe and move it to a more abstract settings; there are (at least) two ways to do that, and Syropoulos has chosen the more interesting one. (Anyway, if somebody asked me to come up with a structural notion of abstract multiset, the first thing that I would think of —and did think of, before this discussion started— is an object of Set 2Set^{\mathbf{2}}.) Asking which notion is correct is not really a fair question.

    Eric: The paper Mathematics of Multisets is worth having a look. I might have pasted a suboptimal piece. He talks about two types of multisets (and more actually): 1.) real multisets and 2. multisets. Here is another quote:

    Real multisets and multisets are associated with a (ordinary) set and an equivalence relation or a function, respectively. Here are the formal definitions:

    Definition 1. A real multiset 𝒳\mathcal{X} is a pair (X,ρ)(X,\rho), where XX is a set and ρ\rho an equivalence relation on XX. The set XX is called the field of the real multiset. Elements of XX in the same equivalence class will be said to be of the same sort; elements in different equivalence classes will be said to be of different sorts.

    Given two real multisets 𝒳=(X,ρ)\mathcal{X} = (X,\rho) and 𝒴=(Y,σ)\mathcal{Y} = (Y,\sigma), a morphism of real multisets is a function f:XYf:X\to Y which respects sorts; that is, if x,xXx,x'\in X and xρxx \rho x', then f(x)σf(x)f(x)\sigma f(x').

    Definition 2. Let DD be a set. A multiset over DD is just a pair D,f\langle D, f\rangle, where DD is a set and f:Df:D\to\mathbb{N} is a function.

    The previous definition is the characteristic function definition method for multisets.

    Remark 1. Any ordinary set AA is actually a multiset A,χ A\langle A,\chi_A\rangle, where χ A\chi_A is its characteristic function.

    +– {: .query} Eric: Given X={1,1,2}X = \{1,1,2\} and Y={1,1,3}Y = \{1,1,3\}, is XY={1,1}X\cap Y = \{1,1\} or is XY={1}X\cap Y = \{1\}?

    Todd: It’s {1,1}\{1, 1\}. (To make the question structural, we should think of XX and YY as multisubsets of some other multiset, but never mind.)

    As a writer (perhaps Toby) was saying above, a locally finite multiset MM can be thought of as an ordinary set XX equipped with a multiplicity function μ:X\mu: X \to \mathbb{N}. A multisubset of MM can then be reckoned as XX equipped with a function ν:X\nu: X \to \mathbb{N} which is bounded above by μ\mu. To take the intersection of two multisubsets ν,ν:X\nu, \nu': X \to \mathbb{N}, you take the minimum or inf of ν,ν\nu, \nu'. Your question can then be translated to one where X={1,2,3}X = \{1, 2, 3\}, where ν(1)=2,ν(2)=1,ν(3)=0\nu(1) = 2, \nu(2) = 1, \nu(3) = 0 and ν(1)=2,ν(2)=0,ν(3)=1\nu'(1) = 2, \nu'(2) = 0, \nu'(3) = 1.

    Eric: Thanks Todd! The reference Mathematics of Multisets explains this nicely too. =–

    +– {: .query} Eric: What is the difference (aside from negatives) between multisets and abelian groups freely generate by some set UU? It seems like a multiset X,μ\langle X,\mu\rangle (XX s a set and μ:X\mu:X\to\mathbb{N}) can be thought of as a vector with μ\mu providing the coefficients.

    For example, we could express the multiset 𝒳={1,1,1,2,3,3,3,3,3}\mathcal{X} = \{1,1,1,2,3,3,3,3,3\} as

    𝒳=3{1}+1{2}+4{3}.\mathcal{X} = 3\{1\} + 1\{2\} + 4\{3\}.

    Toby: The only difference is notation; see the note at the end of inner product of multisets.

    Mike Shulman: At least, if all your multisets are locally finite.

    Toby: Right; which they are for Eric, who specified μ:X\mu\colon X \to \mathbb{N}. If you allow arbitrary cardinalities, then it's the free module on UU over the rig of cardinal numbers. =–

    diff, v38, current

    • CommentRowNumber3.
    • CommentAuthorUrs
    • CommentTimeApr 2nd 2021

    what is the outcome, anyway?

    True, these in-entry discussions tended to just be abandoned inconclusively at some point. That’s why, back in those years, we eventually decided to stop having these discussions inside entries and started to remove those we had, as you are doing here (thanks for that).

    To everyone’s defense, one should recall that back then the young nnLab was the first ever collaborative wiki (in our area at least) and nobody had any experience with how these things should work. Also, the nnForum didn’t exist from the beginning (though now I forget when it came into existence).

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)