\documentclass[12pt,titlepage]{article} \usepackage{amsmath} \usepackage{mathrsfs} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{mathtools} \usepackage{graphicx} \usepackage{color} \usepackage{ucs} \usepackage[utf8x]{inputenc} \usepackage{xparse} \usepackage{hyperref} %----Macros---------- % % Unresolved issues: % % \righttoleftarrow % \lefttorightarrow % % \color{} with HTML colorspec % \bgcolor % \array with options (without options, it's equivalent to the matrix environment) % Of the standard HTML named colors, white, black, red, green, blue and yellow % are predefined in the color package. Here are the rest. \definecolor{aqua}{rgb}{0, 1.0, 1.0} \definecolor{fuschia}{rgb}{1.0, 0, 1.0} \definecolor{gray}{rgb}{0.502, 0.502, 0.502} \definecolor{lime}{rgb}{0, 1.0, 0} \definecolor{maroon}{rgb}{0.502, 0, 0} \definecolor{navy}{rgb}{0, 0, 0.502} \definecolor{olive}{rgb}{0.502, 0.502, 0} \definecolor{purple}{rgb}{0.502, 0, 0.502} \definecolor{silver}{rgb}{0.753, 0.753, 0.753} \definecolor{teal}{rgb}{0, 0.502, 0.502} % Because of conflicts, \space and \mathop are converted to % \itexspace and \operatorname during preprocessing. % itex: \space{ht}{dp}{wd} % % Height and baseline depth measurements are in units of tenths of an ex while % the width is measured in tenths of an em. \makeatletter \newdimen\itex@wd% \newdimen\itex@dp% \newdimen\itex@thd% \def\itexspace#1#2#3{\itex@wd=#3em% \itex@wd=0.1\itex@wd% \itex@dp=#2ex% \itex@dp=0.1\itex@dp% \itex@thd=#1ex% \itex@thd=0.1\itex@thd% \advance\itex@thd\the\itex@dp% \makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}} \makeatother % \tensor and \multiscript \makeatletter \newif\if@sup \newtoks\@sups \def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}% \def\reset@sup{\@supfalse\@sups={}}% \def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else% \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}% \else \append@sup#2 \@suptrue \fi% \expandafter\mk@scripts\fi} \def\tensor#1#2{\reset@sup#1\mk@scripts#2_/} \def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2% \reset@sup\mk@scripts#3_/} \makeatother % \slash \makeatletter \newbox\slashbox \setbox\slashbox=\hbox{$/$} \def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$} \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa \copy\slashbox \kern-\@tempdima \box\@tempboxa} \def\slash{\protect\itex@pslash} \makeatother % math-mode versions of \rlap, etc % from Alexander Perlis, "A complement to \smash, \llap, and lap" % http://math.arizona.edu/~aprl/publications/mathclap/ \def\clap#1{\hbox to 0pt{\hss#1\hss}} \def\mathllap{\mathpalette\mathllapinternal} \def\mathrlap{\mathpalette\mathrlapinternal} \def\mathclap{\mathpalette\mathclapinternal} \def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}} \def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}} \def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}} % Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2} \let\oldroot\root \def\root#1#2{\oldroot #1 \of{#2}} \renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}} % Manually declare the txfonts symbolsC font \DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n} \SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n} \DeclareFontSubstitution{U}{txsyc}{m}{n} % Manually declare the stmaryrd font \DeclareSymbolFont{stmry}{U}{stmry}{m}{n} \SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n} % Manually declare the MnSymbolE font \DeclareFontFamily{OMX}{MnSymbolE}{} \DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n} \SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n} \DeclareFontShape{OMX}{MnSymbolE}{m}{n}{ <-6> MnSymbolE5 <6-7> MnSymbolE6 <7-8> MnSymbolE7 <8-9> MnSymbolE8 <9-10> MnSymbolE9 <10-12> MnSymbolE10 <12-> MnSymbolE12}{} % Declare specific arrows from txfonts without loading the full package \makeatletter \def\re@DeclareMathSymbol#1#2#3#4{% \let#1=\undefined \DeclareMathSymbol{#1}{#2}{#3}{#4}} \re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46} \re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12} \re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64} \re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6} \re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77} \re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77} \makeatother % \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE \makeatletter \def\Decl@Mn@Delim#1#2#3#4{% \if\relax\noexpand#1% \let#1\undefined \fi \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}} \def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}} \def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}} \Decl@Mn@Open{\llangle}{mnomx}{'164} \Decl@Mn@Close{\rrangle}{mnomx}{'171} \Decl@Mn@Open{\lmoustache}{mnomx}{'245} \Decl@Mn@Close{\rmoustache}{mnomx}{'244} \makeatother % Widecheck \makeatletter \DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}} \def\@widecheck#1#2{% \setbox\z@\hbox{\m@th$#1#2$}% \setbox\tw@\hbox{\m@th$#1% \widehat{% \vrule\@width\z@\@height\ht\z@ \vrule\@height\z@\@width\wd\z@}$}% \dp\tw@-\ht\z@ \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@ \setbox\tw@\hbox{% \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box \tw@}}}% {\ooalign{\box\tw@ \cr \box\z@}}} \makeatother % \mathraisebox{voffset}[height][depth]{something} \makeatletter \NewDocumentCommand\mathraisebox{moom}{% \IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{% \IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}% }{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}% \mathpalette\@temp{#4}} \makeatletter % udots (taken from yhmath) \makeatletter \def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.} \mkern2mu\raise4\p@\hbox{.}\mkern1mu \raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}} \makeatother %% Fix array \newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}} %% \itexnum is a noop \newcommand{\itexnum}[1]{#1} %% Renaming existing commands \newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}} \newcommand{\widevec}{\overrightarrow} \newcommand{\darr}{\downarrow} \newcommand{\nearr}{\nearrow} \newcommand{\nwarr}{\nwarrow} \newcommand{\searr}{\searrow} \newcommand{\swarr}{\swarrow} \newcommand{\curvearrowbotright}{\curvearrowright} \newcommand{\uparr}{\uparrow} \newcommand{\downuparrow}{\updownarrow} \newcommand{\duparr}{\updownarrow} \newcommand{\updarr}{\updownarrow} \newcommand{\gt}{>} \newcommand{\lt}{<} \newcommand{\map}{\mapsto} \newcommand{\embedsin}{\hookrightarrow} \newcommand{\Alpha}{A} \newcommand{\Beta}{B} \newcommand{\Zeta}{Z} \newcommand{\Eta}{H} \newcommand{\Iota}{I} \newcommand{\Kappa}{K} \newcommand{\Mu}{M} \newcommand{\Nu}{N} \newcommand{\Rho}{P} \newcommand{\Tau}{T} \newcommand{\Upsi}{\Upsilon} \newcommand{\omicron}{o} \newcommand{\lang}{\langle} \newcommand{\rang}{\rangle} \newcommand{\Union}{\bigcup} \newcommand{\Intersection}{\bigcap} \newcommand{\Oplus}{\bigoplus} \newcommand{\Otimes}{\bigotimes} \newcommand{\Wedge}{\bigwedge} \newcommand{\Vee}{\bigvee} \newcommand{\coproduct}{\coprod} \newcommand{\product}{\prod} \newcommand{\closure}{\overline} \newcommand{\integral}{\int} \newcommand{\doubleintegral}{\iint} \newcommand{\tripleintegral}{\iiint} \newcommand{\quadrupleintegral}{\iiiint} \newcommand{\conint}{\oint} \newcommand{\contourintegral}{\oint} \newcommand{\infinity}{\infty} \newcommand{\bottom}{\bot} \newcommand{\minusb}{\boxminus} \newcommand{\plusb}{\boxplus} \newcommand{\timesb}{\boxtimes} \newcommand{\intersection}{\cap} \newcommand{\union}{\cup} \newcommand{\Del}{\nabla} \newcommand{\odash}{\circleddash} \newcommand{\negspace}{\!} \newcommand{\widebar}{\overline} \newcommand{\textsize}{\normalsize} \renewcommand{\scriptsize}{\scriptstyle} \newcommand{\scriptscriptsize}{\scriptscriptstyle} \newcommand{\mathfr}{\mathfrak} \newcommand{\statusline}[2]{#2} \newcommand{\tooltip}[2]{#2} \newcommand{\toggle}[2]{#2} % Theorem Environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{prop}{Proposition} \newtheorem{cor}{Corollary} \newtheorem*{utheorem}{Theorem} \newtheorem*{ulemma}{Lemma} \newtheorem*{uprop}{Proposition} \newtheorem*{ucor}{Corollary} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{example}{Example} \newtheorem*{udefn}{Definition} \newtheorem*{uexample}{Example} \theoremstyle{remark} \newtheorem{remark}{Remark} \newtheorem{note}{Note} \newtheorem*{uremark}{Remark} \newtheorem*{unote}{Note} %------------------------------------------------------------------- \begin{document} %------------------------------------------------------------------- \section*{multiset} \hypertarget{multisets}{}\section*{{Multisets}}\label{multisets} \noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak \noindent\hyperlink{definitions}{Definitions}\dotfill \pageref*{definitions} \linebreak \noindent\hyperlink{operations_on_multisets}{Operations on multisets}\dotfill \pageref*{operations_on_multisets} \linebreak \noindent\hyperlink{examples}{Examples}\dotfill \pageref*{examples} \linebreak \noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak \noindent\hyperlink{discussion}{Discussion}\dotfill \pageref*{discussion} \linebreak \noindent\hyperlink{morphisms}{Morphisms}\dotfill \pageref*{morphisms} \linebreak \hypertarget{idea}{}\subsection*{{Idea}}\label{idea} A multiset is like a [[set]], just allowing that the elements have multiplicities. Thus the multiset $\{1,1,2\}$ differs from the multiset $\{1,2\}$, while $\{1,2,1\}$ is the same as $\{1,1,2\}$. Multisets are useful in [[combinatorics]]. See \href{http://en.wikipedia.org/wiki/Multiset}{wikipedia}. \hypertarget{definitions}{}\subsection*{{Definitions}}\label{definitions} While it is possible to take multisets as a fundamental concept in [[foundations]], it is more common to define them in terms of [[sets]] and [[functions]]. A \textbf{multiset} $\mathcal{X} = \langle X,\mu_X\rangle$,can be defined as a set $X$ (its \textbf{underlying set}) together with a function $\mu_X$ (giving each element its \textbf{multiplicity}) from $X$ to a class of nonzero [[cardinal numbers]]. A multiset is \textbf{locally finite} if multiplicity takes values in the [[natural numbers]]. Many authors take all multisets to be locally finite; that is the default in combinatorics. The multiset is \textbf{finite} if it is locally finite and $X$ is a [[finite set]]. We can also define a multiset to be a function from the [[proper class]] of all objects to the class of all cardinal numbers, with the proviso that the objects whose multiplicity is nonzero form a set (the set $X$ above). If we are only interested in multisets with elements drawn from a given set $U$ (as is common in combinatorics), then an alternative definition is very useful: a \textbf{multisubset} of $U$ is a function $f\colon B \to U$, where two multisubsets $f\colon B \to U$ and $f'\colon B' \to U$ are considered \emph{equal} if there is a [[bijection]] $g\colon B \to B'$ that makes a commutative triangle. In other words, a multisubset of $U$ is an isomorphism class in the [[slice category]] $Set/U$. (Compare this to the structural definition of \emph{[[subset]]} of $U$ as an [[injective function]] to $U$.) A multisubset of $U$ is locally finite if every [[fibre]] is finite; it is finite if additionally the [[image]] of $f$ (which corresponds to $A$ in the original definition) is finite. A locally finite multisubset can also be described as a function from $U$ to the set of natural numbers; this is just the multiplicity function $\mu$ again, now with $U$ (rather than $X$) specified as the domain and allowing the value $0$ to be taken. \hypertarget{operations_on_multisets}{}\subsection*{{Operations on multisets}}\label{operations_on_multisets} The operations on cardinal numbers induce operations on multisets (or on multisubsets of any given set $U$). In the following, let $\mathcal{X} = \langle X,\mu_X\rangle$ and $\mathcal{Y} = \langle Y,\mu_Y\rangle$ be multisets. \begin{itemize}% \item The [[cardinality]] of a multiset is given by \begin{displaymath} |\mathcal{X}| = \sum_{e\in X} \mu_X(e). \end{displaymath} \item The \textbf{[[intersection]]} of multisets is the multiset whose cardinality is given by the [[infimum]] operation on cardinal numbers. \begin{displaymath} \mathcal{X}\cap\mathcal{Y} = \langle X\cap Y, \min(\mu_X,\mu_Y)\rangle. \end{displaymath} \item The \textbf{[[union]]} of multisets is the multiset whose cardinality is given by the [[supremum]] operation on cardinal numbers. \begin{displaymath} \mathcal{X}\cup\mathcal{Y} = \langle X\cup Y, \max(\mu_X,\mu_Y)\rangle. \end{displaymath} \item The \emph{[[set difference]]} of multisets is the multiset given by \begin{displaymath} \mathcal{X} \backslash \mathcal{Y} = \langle \{ a \in X \cup Y \;|\; mu_X(a) \gt \mu_Y(a) \}, \mu_X - \mu_Y \rangle . \end{displaymath} \item The \textbf{sum} of multisets is the multiset whose cardinality is given by addition of cardinal numbers; this has no analogue for ordinary sets. \begin{displaymath} \mathcal{X}+\mathcal{Y} = \langle X\cup Y, \mu_X+\mu_Y\rangle. \end{displaymath} \item The \textbf{product} of multisets (turning them into a [[rig]]) is the multiset whose cardinality is given by the product of cardinal numbers \begin{displaymath} \mathcal{X}\mathcal{Y} = \langle X\cap Y, \mu_X\mu_Y\rangle. \end{displaymath} Note that if $\mathcal{X}$ is a set, then $\mathcal{X}\mathcal{X} = \mathcal{X}.$ \item The [[inner product of multisets]] is given by \begin{displaymath} \langle\mathcal{X},\mathcal{Y}\rangle = \sum_{e\in{X\cap Y}} \mu_X(e) \mu_Y(e). \end{displaymath} Note that the inner product corresponds to the cardinality of the product \begin{displaymath} \langle\mathcal{X},\mathcal{Y}\rangle = |\mathcal{X}\mathcal{Y}|. \end{displaymath} \end{itemize} \hypertarget{examples}{}\subsection*{{Examples}}\label{examples} \ldots{} \begin{itemize}% \item See also [[inner product of multisets]]. \end{itemize} \hypertarget{references}{}\subsection*{{References}}\label{references} \begin{itemize}% \item \href{http://asyropoulos.eu/papers/PDF/MathMSet.pdf}{Mathematics of Multisets}, Apostolos Syropoulos \item \href{http://asyropoulos.eu/papers/PDF/mset.pdf}{Categorical Models of Multisets}, Apostolos Syropoulos \item \href{http://www.emis.de/journals/NSJOM/Papers/37_2/NSJOM_37_2_073_092.pdf}{An Overview of the Applications of Multisets}, D. Singh, A. M. Ibrahim, T. Yohanna and J. N. Singh \end{itemize} Is there a reason that you moved these references up here? We need them especially for the stuff about morphisms below. ---Toby \hypertarget{discussion}{}\subsection*{{Discussion}}\label{discussion} [[Eric]]: What would a colimit over an MSet-valued functor $F:A\to MSet$ look like? \emph{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. \emph{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 \emph{is} the proper notion of [[disjoint union]] for abstract multisets. \hypertarget{morphisms}{}\subsection*{{Morphisms}}\label{morphisms} What is a function between multisets? I would be inclined to say that for multisubsets of an ambient universe $U$ considered as objects of $Set/U$, a function from $B\to U$ to $B'\to U$ would be an arbitrary function $B\to B'$ (not necessarily commuting with the projections to $U$). But this doesn't work if a multisubset of $U$ is an \emph{isomorphism class} in $Set/U$ rather than merely an object of it. -- [[Mike Shulman]] [[Eric]]: This definition is taken from Syropoulos: \begin{udefn} Category $\mathbf{MSet}$ is a category of all possible multisets. \begin{enumerate}% \item The objects of the category consist of pairs $(A, P)$, where $A$ is a set and $P:A\to Set$ a presheaf on $A$. \item If $(A,P)$ and $(B,Q)$ are two objects of the category, an arrow between these objects is a pair $(f,\lambda)$, where $f:A\to B$ is a function and $\lambda:P\to Q\circ f$ is a natural transformation, i.e., a family of functions. \item Arrows compose as follows: suppose that $(A,P)\stackrel{(f,\lambda)}{\to}(B,Q)$ and $(B,Q) \stackrel{(g,\mu)}{\to}(C,R)$ are arrows of the category, then $(f,\lambda)\circ (g,\mu) = (g\circ f, \mu\times\lambda)$, where $g\circ f$ is the usual function composition and $\mu\times\lambda:P\to R\circ (g\circ f)$. \item Given an object $(A,P)$, the identity arrow is $(id_A, id_P)$. \end{enumerate} \end{udefn} 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 \emph{set} to every element, rather than a \emph{cardinality} to every element, so that the multisubsets of $U$ are exactly objects of $Set/U$. I'm surprised, though, that with his definition the only functions $\{1,1\} \to \{2,3\}$ are constant; why can't I send the two copies of $1$ to different places? \emph{Toby}: If you could, then $\{1,1\}$ and $\{2,3\}$ would be isomorphic in this category, and we'd just have $Set$ back again. I find \emph{Mathematics of Multisets} especially interesting for its distinction between multisets with \emph{distinguishable} objects and `pure' multisets with \emph{indistinguishable} objects. The definition above involving cardinal numbers gives us `pure' multisets, unlike the objects of the category $MSet$ 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^{\mathbf{2}}$. Is that better? Note here that \textbf{2} is the walking arrow.—Anonymous I don't find it wrong that the category of multisets would be equivalent to $Set$, since $Set$ only sees ``structural'' properties of sets, and the fact that two elements of a set are ``the same'' (which is what distinguishes $\{1,1\}$ from $\{2,3\}$) is a nonstructural property that only makes sense in the context of sub-multisets of some ambient set. \emph{Toby}: At least $Set^{\mathbf{2}}$ is \emph{different} from $Set$. And how do you decide whether being `the same' is a structural property of a \emph{multi}set? 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^{\mathbf{2}}$.) Asking which notion is correct is not really a fair question. [[Eric]]: The paper \href{http://www.asyropoulos.eu/papers/PDF/MathMSet.pdf}{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: \begin{quote}% Real multisets and multisets are associated with a (ordinary) set and an equivalence relation or a function, respectively. Here are the formal definitions: \textbf{Definition 1}. A real multiset $\mathcal{X}$ is a pair $(X,\rho)$, where $X$ is a set and $\rho$ an equivalence relation on $X$. The set $X$ is called the field of the real multiset. Elements of $X$ 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 $\mathcal{X} = (X,\rho)$ and $\mathcal{Y} = (Y,\sigma)$, a morphism of real multisets is a function $f:X\to Y$ which respects sorts; that is, if $x,x'\in X$ and $x \rho x'$, then $f(x)\sigma f(x')$. \textbf{Definition 2}. Let $D$ be a set. A multiset over $D$ is just a pair $\langle D, f\rangle$, where $D$ is a set and $f:D\to\mathbb{N}$ is a function. The previous definition is the characteristic function definition method for multisets. \textbf{Remark 1}. Any ordinary set $A$ is actually a multiset $\langle A,\chi_A\rangle$, where $\chi_A$ is its characteristic function. \end{quote} [[Eric]]: Given $X = \{1,1,2\}$ and $Y = \{1,1,3\}$, is $X\cap Y = \{1,1\}$ or is $X\cap Y = \{1\}$? [[Todd Trimble|Todd]]: It's $\{1, 1\}$. (To make the question structural, we should think of $X$ and $Y$ as multisubsets of some other multiset, but never mind.) As a writer (perhaps Toby) was saying above, a locally finite multiset $M$ can be thought of as an ordinary set $X$ equipped with a multiplicity function $\mu: X \to \mathbb{N}$. A multisubset of $M$ can then be reckoned as $X$ equipped with a function $\nu: X \to \mathbb{N}$ which is bounded above by $\mu$. To take the intersection of two multisubsets $\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\}$, where $\nu(1) = 2, \nu(2) = 1, \nu(3) = 0$ and $\nu'(1) = 2, \nu'(2) = 0, \nu'(3) = 1$. [[Eric]]: Thanks Todd! The reference \href{http://obelix.ee.duth.gr/~apostolo/Articles/MathMSet.pdf}{Mathematics of Multisets} explains this nicely too. [[Eric]]: What is the difference (aside from negatives) between multisets and abelian groups freely generate by some set $U$? It seems like a multiset $\langle X,\mu\rangle$ ($X$ s a set and $\mu:X\to\mathbb{N}$) can be thought of as a \emph{vector} with $\mu$ providing the coefficients. For example, we could express the multiset $\mathcal{X} = \{1,1,1,2,3,3,3,3,3\}$ as \begin{displaymath} \mathcal{X} = 3\{1\} + 1\{2\} + 4\{3\}. \end{displaymath} \emph{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. \emph{Toby}: Right; which they are for Eric, who specified $\mu\colon X \to \mathbb{N}$. If you allow arbitrary cardinalities, then it's the free module on $U$ over the rig of cardinal numbers. [[!redirects multiset]] [[!redirects multisets]] [[!redirects multisubset]] [[!redirects multisubsets]] [[!redirects bag]] [[!redirects bags]] \end{document}