\( \gdef\badDispatch#1{\textbf{\textcolor{e1432d}{#1}}} \gdef\noKatexForm#1{\badDispatch{#1}} \gdef\largeDot{\raisebox{0.06em}{\tiny∙}} \gdef\rarrbar{ {\raisebox{-0.05em}{→}\mkern{-0.13em}{\large\shortmid}}} \gdef\larrbar{ { {\large\shortmid}\mkern{-0.13em}{\raisebox{-0.05em}{←}}}} \gdef\suptrans{^\mathsf{T}} \gdef\supdagger{^\dagger} \gdef\rawsymbol#1{\operatorname{#1}} \gdef\colorsymbol#1#2{\textcolor{#1}{\rawsymbol{#2}}} \gdef\lsymbol#1{\colorsymbol{262626}{#1}} \gdef\msymbol#1{\colorsymbol{b50800}{#1}} \gdef\osymbol#1{\colorsymbol{00427f}{#1}} \gdef\lstring#1{\textcolor{666666}{\textrm{\textquotedblleft{\text{#1}}\textquotedblright}}} \gdef\boldForm#1{\textbf{#1}} \gdef\lrform#1{ {\textcolor{e1432d}{#1}}} \gdef\lgform#1{ {\textcolor{4ea82a}{#1}}} \gdef\lbform#1{ {\textcolor{3e81c3}{#1}}} \gdef\lrgform#1{ {\textcolor{ffc87d}{#1}}} \gdef\lgbform#1{ {\textcolor{96e2e3}{#1}}} \gdef\lrbform#1{ {\textcolor{f989b8}{#1}}} \gdef\rform#1{ {\textcolor{cb2b1a}{#1}}} \gdef\gform#1{ {\textcolor{399318}{#1}}} \gdef\bform#1{ {\textcolor{2b6fb0}{#1}}} \gdef\drform#1{ {\textcolor{9b0000}{#1}}} \gdef\dgform#1{ {\textcolor{006800}{#1}}} \gdef\dbform#1{ {\textcolor{004987}{#1}}} \gdef\drgform#1{ {\textcolor{ae5900}{#1}}} \gdef\dgbform#1{ {\textcolor{006567}{#1}}} \gdef\drbform#1{ {\textcolor{86004d}{#1}}} \gdef\rgform#1{ {\textcolor{dc841a}{#1}}} \gdef\gbform#1{ {\textcolor{47a5a7}{#1}}} \gdef\rbform#1{ {\textcolor{c74883}{#1}}} \gdef\pform#1{ {\textcolor{665996}{#1}}} \gdef\dpform#1{ {\textcolor{41326b}{#1}}} \gdef\waform#1{ {\textcolor{6b6b6b}{#1}}} \gdef\wbform#1{ {\textcolor{929292}{#1}}} \gdef\wcform#1{ {\textcolor{c5c5c5}{#1}}} \gdef\tick{\checkmark} \gdef\barToken{\mathbf{|}} \gdef\filledRectangleToken{▮} \gdef\emptyRectangleToken{▯} \gdef\filledSquareToken{■} \gdef\emptySquareToken{□} \gdef\filledToken{∙} \gdef\emptyToken{∘} \gdef\cardinalRewrite#1#2{\rewrite{#1}{#2}} \gdef\primed#1{ {#1}^{\prime}} \gdef\tinybullet{ {\tiny●}} \gdef\factsym#1{\mathord{#1}} \gdef\forwardFactor{\factsym{\uparrow}} \gdef\backwardFactor{\factsym{\downarrow}} \gdef\forwardBackwardFactor{\factsym{\updownarrow}} \gdef\forwardBackwardNeutralFactor{\factsym{\mathrlap{\downarrow}{\mathrlap{\uparrow}{\endash} } }} \gdef\neutralFactor{\factsym{\shornarrow}} \gdef\arrowhead{⏵} \gdef\inverseArrowhead{⏴} \gdef\rightArrowhead{⏵} \gdef\leftArrowhead{⏴} \gdef\upArrowhead{⏶} \gdef\downArrowhead{⏷} \gdef\de#1#2{ { {#1}\xundirectededge{}{#2}}} \gdef\ue#1#2{ { {#1}\xrightedge{}{#2}}} \gdef\shifttag#1{\raisebox{-1em}{$#1$}} \gdef\shifttag#1{#1} \gdef\tde#1#2#3{ {#1}\:\xrightedge{\shifttag{#3}}\;{#2}} \gdef\tue#1#2#3{ {#1}\;\xundirectededge{\shifttag{#3}}\;{#2}} \gdef\shiftunderset#1#2{\underset{\raisebox{0.15em}{\scriptsize $#1$}}{#2}} \gdef\mdtde#1#2#3#4{ {#1}\,\;\shiftunderset{#4}{\xrightedge{#3}}\;{#2}} \gdef\mtue#1#2#3#4{ {#1}\,\;\shiftunderset{#4}{\xundirectededge{#3}}\;\,{#2}} \gdef\mtde#1#2#3#4{ {#1}\,\;\operatornamewithlimits{\xrightedge{#3}}\limits_{#4} \;{#2}} \gdef\mapsfrom{\htmlClass{hreflect}{\mapsto}} \gdef\longmapsfrom{\htmlClass{hreflect}{\longmapsto}} \gdef\diffd{𝕕} \gdef\partialdof#1{\partial {#1}} \gdef\emptySet{\empty} \gdef\unknown{\wbform{\text{?}}} \gdef\notApplicable{\wbform{\text{---}}} \gdef\textAnd{\text{\,and\,}} \gdef\identicallyEqualSymbol{\equiv} \gdef\congruentSymbol{\equiv} \gdef\isomorphicSymbol{\simeq} \gdef\homeomorphicSymbol{\cong} \gdef\homotopicSymbol{\simeq} \gdef\approxEqualSymbol{\approx} \gdef\bijectiveSymbol{\approx} \gdef\defeq{\mathrel{≝}} \gdef\defEqualSymbol{\mathrel{≝}} \gdef\syntaxEqualSymbol{\mathrel{\textcolor{888888}{\equiv}}} \gdef\tailEqualSymbol{\underdot{=}} \gdef\headEqualSymbol{\dot{=}} \gdef\ruledelayed{:\to} \gdef\mathdollar{\text{\textdollar}} \gdef\hyphen{\text{-}} \gdef\endash{\text{--}} \gdef\emdash{\text{---}} \gdef\updownarrows{\uparrow\!\downarrow} \gdef\vthinspace{\mkern{1pt}} \gdef\dlq{\text{\textquotedblleft}} \gdef\drq{\text{\textquotedblright}} \gdef\dprime{ {\prime\prime}} \gdef\inverse#1{ { {#1}^{-1}}} \gdef\inverseSymbol{\inverse{□}} \gdef\groupDirectProduct#1{#1} \gdef\groupDirectProductSymbol{\times} \gdef\groupInverse{\inverse} \gdef\groupPower#1#2{ {#1}^{#2}} \gdef\groupCommutator#1#2{\left[{#1},{#2}\right]} \gdef\groupoidInverse{\inverse} \gdef\latticeBFS#1{\textrm{bfs}({#1})} \gdef\pathHomomorphism#1{#1} \gdef\groupoidFunction#1{#1} \gdef\groupoidHomomorphism#1{#1} \gdef\affineModifier#1{\overrightharpoon{#1}} \gdef\supercirc#1{#1^{\circ}} \gdef\supercircb#1{#1^{\bullet}} \gdef\blackCircleModifier#1{\supercircb{#1}} \gdef\whiteCircleModifier#1{\supercirc{#1}} \gdef\totalSpaceStyle#1{\rbform{#1}} \gdef\baseSpaceStyle#1{\bform{#1}} \gdef\fiberSpaceStyle#1{\rform{#1}} \gdef\totalSpaceElementStyle#1{\drbform{#1}} \gdef\baseSpaceElementStyle#1{\dbform{#1}} \gdef\fiberSpaceElementStyle#1{\drform{#1}} \gdef\bundleProjectionStyle#1{\dgform{#1}} \gdef\bundleGraphStyle#1{\rbform{#1}} \gdef\bundleSectionStyle#1{\drgform{#1}} \gdef\bundleFunctionStyle#1{\drbform{#1}} \gdef\graphFunctionStyle#1{\totalSpaceStyle{#1}} \gdef\projectionFunctionStyle#1{\totalSpaceStyle{#1}} \gdef\sectionFunctionStyle#1{\totalSpaceStyle{#1}} \gdef\functionGraph#1{G_{#1}} \gdef\toroidalModifier#1{\supercirc{#1}} \gdef\modulo#1{\supercirc{#1}} \gdef\dividesSymbol{\mathrel{|}} \gdef\groupFunction#1{#1} \gdef\groupHomomorphism#1{#1} \gdef\automorphisms{\operatorname{Aut}} \gdef\endomorphisms{\operatorname{End}} \gdef\transportMap#1{\transportMapSymbol_{#1}} \gdef\transportMapSymbol{\tau} \gdef\action#1{#1} \gdef\selfAction#1{\hat{#1}} \gdef\actionGroupoid#1{\utilde{#1}} \gdef\cardinalGroup#1{G^*({#1})} \gdef\signed#1{ {#1}^*} \gdef\transportAtlas#1{T_{#1}} \gdef\inverted#1{\underline{#1}} \gdef\mirror#1{\overline{#1}} \gdef\pathComposeSymbol{\mathbin{∷}} \gdef\pathCompose#1#2{ {#1}\pathComposeSymbol{#2}} \gdef\translateSymbol{\mathbin{\uparrow}} \gdef\backwardTranslateSymbol{\mathbin{\downarrow}} \gdef\pathTranslate#1#2{ {#1}\translateSymbol{#2}} \gdef\pathLeftTranslate#1{ { {#1}\translateSymbol}} \gdef\pathBackwardTranslate#1#2{ {#1}{\backwardTranslateSymbol}{#2}} \gdef\pathLeftBackwardTranslate#1{ {#1}{\backwardTranslateSymbol}} \gdef\compactCovariantDifference#1#2{\Delta_{#1}\,{#2}} \gdef\covariantDifference{ {#1}\,\Delta\,{#2}} \gdef\forwardDifference{\Delta^{+}} \gdef\backwardDifference{\Delta^{-}} \gdef\centralDifference{\Delta} \gdef\pathForwardDifference#1{\forwardDifference_{#1}} \gdef\pathBackwardDifference#1{\backwardDifference_{#1}} \gdef\pathCentralDifference#1{\centralDifference_{#1}} \gdef\pathHead#1{\pathHeadVector{#1}} \gdef\pathTail#1{\pathTailVector{#1}} \gdef\pathHeadVector#1{ {#1}^{\bullet}} \gdef\pathTailVector#1{ {#1}_{\bullet}} \gdef\pathReverse#1{ {#1}^{\dagger}} \gdef\pathIntegral#1#2{ {#1} \int {#2}} \gdef\pathIntegralSymbol{ {\int}} \gdef\pathDot#1#2{ {#1} \cdot {#2}} \gdef\pathDotSymbol{ {\cdot}} \gdef\compactBasis#1{\mathscr{B}} \gdef\length{\operatorname{len}} \gdef\signedLength{\operatorname{len^*}} \gdef\andFn{\operatorname{and}} \gdef\orFn{\operatorname{or}} \gdef\notFn{\operatorname{not}} \gdef\vertexList{\operatorname{vertices}} \gdef\vertexList{\operatorname{vertices}} \gdef\edgeList{\operatorname{edges}} \gdef\pathList{\operatorname{paths}} \gdef\cardinalList{\operatorname{cards}} \gdef\signedCardinalList{\operatorname{cards^*}} \gdef\wordOf{\operatorname{word}} \gdef\headVertex{\operatorname{head}} \gdef\tailVertex{\operatorname{tail}} \gdef\basis{\operatorname{basis}} \gdef\split{\operatorname{split}} \gdef\lcm{\operatorname{lcm}} \gdef\minimalContractionSets{\operatorname{MCSets}} \gdef\minimalContractions{\operatorname{MC}} \gdef\grade{\operatorname{grade}} \gdef\support{\operatorname{support}} \gdef\coefficient{\operatorname{coeff}} \gdef\domain{\operatorname{domain}} \gdef\codomain{\operatorname{codomain}} \gdef\modFunction{\operatorname{mod}} \gdef\clip{\operatorname{clip}} \gdef\sign{\operatorname{sign}} \gdef\step{\operatorname{step}} \gdef\projection{\operatorname{proj}} \gdef\lift{\operatorname{lift}} \gdef\identity{\operatorname{id}} \gdef\total{\operatorname{total}} \gdef\torus{\operatorname{torus}} \gdef\mobius{\operatorname{mobius}} \gdef\stateCompose{\operatorname{glue}} \gdef\infixStateComposeSymbol{\_} \gdef\stateDecompose{\operatorname{melt}} \gdef\stateJoin{\operatorname{conj}} \gdef\stateMeet{\operatorname{disj}} \gdef\stateExtent{\operatorname{extent}} \gdef\stateIntent{\operatorname{intent}} \gdef\infixStateJoinSymbol{\sqcup} \gdef\infixStateMeetSymbol{\sqcap} \gdef\isPrime#1{#1\textrm{ prime}} \gdef\blank{\_} \gdef\emptyWord{} \gdef\multiwordSymbol#1{\mathbf{#1}} \gdef\wordSymbol#1{\mathtt{#1}} \gdef\word#1{#1} \gdef\pathMap#1{#1} \gdef\function#1{#1} \gdef\imageModifier#1{ {#1}^{\rightarrow}} \gdef\preimageModifier#1{ {#1}^{\leftarrow}} \gdef\multiImageColorModifier#1{\msetCol{#1}} \gdef\multiImageModifier#1{ {#1}^{\Rightarrow}} \gdef\multiPreimageModifier#1{ {#1}^{\Leftarrow}} \gdef\functionComposition#1{#1} \gdef\functionCompositionSymbol{\mathbin{\small ∘}} \gdef\route#1#2#3{[{#1}\!:\!{#2}\!:\!{#3}]} \gdef\multiroute#1#2#3{[{#1}\!:\!{#2}\!:\!{#3}]} \gdef\pathWord#1#2#3{ {#1}\!:\!{#2}\!:\!{#3}} \gdef\parenPathWord#1#2#3{\left(\pathWord{#1}{#2}{#3}\right)} \gdef\nullPath{\bot} \gdef\nullElement{\bot} \gdef\path#1{#1} \gdef\vert#1{#1} \gdef\underdot#1{\underset{\raisebox{0.3em}{.}}{#1}} \gdef\headVertexSymbol{◨} \gdef\tailVertexSymbol{◧} \gdef\placeholderVertexSymbol{\mathrlap{◨}{◧}} \gdef\tvert#1{\underdot{#1}} \gdef\hvert#1{\dot{#1}} \gdef\edge#1{#1} \gdef\card#1{\mathtt{#1}} \gdef\path#1{#1} \gdef\quiver#1{#1} \gdef\bindingRuleSymbol{\to} \gdef\compactBindingRuleSymbol{:} \gdef\cayleyQuiverSymbol#1{\selfAction{#1}} \gdef\bindCayleyQuiver#1#2{\selfAction{#1}[#2]} \gdef\bindActionQuiver#1#2{#1[#2]} \gdef\bindSize#1#2{#1(#2)} \gdef\bindCardSize#1#2{#1[#2]} \gdef\bindCards#1#2{#1[#2]} \gdef\subSize#1#2{#1_{#2}} \gdef\gridQuiver#1{\textrm{Grid}^{#1}} \gdef\treeQuiver#1{\textrm{Tree}^{#1}} \gdef\bouquetQuiver#1{\textrm{Bq}^{#1}} \gdef\lineQuiver{\textrm{L}} \gdef\cycleQuiver{\textrm{C}} \gdef\squareQuiver{\textrm{Sq}} \gdef\cubicQuiver{\textrm{Cbc}} \gdef\triangularQuiver{\textrm{Tri}} \gdef\hexagonalQuiver{\textrm{Hex}} \gdef\rhombilleQuiver{\textrm{Rmb}} \gdef\limit#1#2{\lim_{#2}\,#1} \gdef\realVectorSpace#1{\mathbb{R}^{#1}} \gdef\complexVectorSpace#1{\mathbb{C}^{#1}} \gdef\matrixRing#1#2{M_{#2}(#1)} \gdef\groupoid#1{#1} \gdef\group#1{#1} \gdef\field#1{#1} \gdef\ring#1{#1} \gdef\variable#1{#1} \gdef\semiring#1{#1} \gdef\sym#1{#1} \gdef\matrix#1{#1} \gdef\polynomial#1{#1} \gdef\setLetter{\mathcal{S}} \gdef\signedSetLetter{\mathcal{S^*}} \gdef\multisetLetter{\mathcal{M}} \gdef\signedMultisetLetter{\mathcal{M^*}} \gdef\multisetSemiringSymbol#1{#1} \gdef\multisetSemiring#1#2{\multisetLetter\left[#1, #2\right]} \gdef\signedMultisetRingSymbol#1{#1} \gdef\signedMultisetRing#1#2{\signedMultisetLetter\left[#1, #2\right]} \gdef\polynomialRing#1#2{#1[{#2}]} \gdef\routeSymbol#1{#1} \gdef\multirouteSymbol#1{\mathbf{#1}} \gdef\planSymbol#1{\mathbf{#1}} \gdef\ringElement#1{#1} \gdef\matrixPart#1#2#3{#1\llbracket{#2,#3}\rrbracket} \gdef\matrixRowPart#1{#1} \gdef\matrixColumnPart#1{#1} \gdef\subMatrixPart#1#2#3{#1_{#2,#3}} \gdef\matrixDotSymbol{\cdot} \gdef\matrixPlusSymbol{+} \gdef\wordGroup#1{\wordGroupSymbol_{#1}} \gdef\wordGroupSymbol{\Omega} \gdef\wordRing#1{\wordRingSymbol_{#1}} \gdef\wordRingSymbol{\Omega\!\degree} \gdef\wordRingElement#1{#1} \gdef\wordRingBasisElement#1{e_{#1}} \gdef\linearCombinationCoefficient#1{ {\textcolor{888888}{#1}}} \gdef\plan#1{#1} \gdef\planRing#1{\planRingSymbol_{#1}} \gdef\planRingSymbol{\Phi} \gdef\basisPath#1#2{\mathbf{#1}_{#2}} \gdef\basisPathWeight#1#2{ {#1}_{#2}} \gdef\unitSymbol{\mathbf{e}} \gdef\unitVertexField{\unitSymbol_1} \gdef\forwardSymbol{f} \gdef\backwardSymbol{b} \gdef\symmetricSymbol{s} \gdef\antisymmetricSymbol{a} \gdef\wordVector#1#2{\unitSymbol_{#1}^{#2}} \gdef\gradOf#1{\grad\,{#1}} \gdef\grad{\nabla} \gdef\divOf#1{\div\,{#1}} \gdef\div{\dot{\nabla}} \gdef\laplacianOf#1{\laplacian\,{#1}} \gdef\laplacian{\ddot{\nabla}} \gdef\suchThat#1#2{ {#1}\,\big|\,{#2}} \gdef\chart#1{\chartSymbol_{#1}} \gdef\chartSymbol{C} \gdef\graphRegionIntersectionSymbol{\cap} \gdef\graphRegionUnionSymbol{\cup} \gdef\pathIso{\simeq} \gdef\factorial#1{#1!} \gdef\power#1#2{ {#1}^{#2}} \gdef\repeatedPower#1#2{ {#1}^{#2}} \gdef\kroneckerDeltaForm#1{\kroneckerDeltaSymbol_{#1}} \gdef\kroneckerDeltaSymbol{\delta} \gdef\contractionLattice#1{\operatorname{Con}(#1)} \gdef\contractedRelation#1{\sim_{#1}} \gdef\isContracted#1#2{ {#1} \sim {#2}} \gdef\isContractedIn#1#2#3{ {#1} \sim_{#3} {#2}} \gdef\isNotContracted#1#2{ {#1} \not \sim {#2}} \gdef\isNotContractedIn#1#2#3{ {#1} \not \sim_{#3} {#2}} \gdef\contractionSum#1{#1} \gdef\contractionSumSymbol{\sqcup} \gdef\contractionProduct#1{#1} \gdef\contractionProductSymbol{ {\cdot}} \gdef\graph#1{#1} \gdef\graphHomomorphism#1{#1} \gdef\coversSymbol{\sqsupseteq} \gdef\coveredBySymbol{\sqsubseteq} \gdef\strictlyCoversSymbol{\sqsupset} \gdef\strictlyCoveredBySymbol{\sqsubset} \gdef\graphCovering#1#2#3{ {#2} \sqsupseteq_{#1} {#3}} \gdef\quiverCovering#1#2#3{ {#2} \sqsupseteq^{#1} {#3}} \gdef\powerSetSymbol{\mathcal{P}} \gdef\powerSet#1{\powerSetSymbol({#1})} \gdef\existsForm#1#2{\exists\,{#1}\,:\,{#2}} \gdef\forAllForm#1#2{\forall\,{#1}\,:\,{#2}} \gdef\notted#1{\notSymbol {#1}} \gdef\andSymbol{\land} \gdef\orSymbol{\lor} \gdef\notSymbol{\lnot} \gdef\latticeSymbol#1{#1} \gdef\meetSemilatticeSymbol#1{#1} \gdef\joinSemilatticeSymbol#1{#1} \gdef\posetSymbol#1{#1} \gdef\latticeElementSymbol#1{#1} \gdef\meetSemilatticeElementSymbol#1{#1} \gdef\joinSemilatticeElementSymbol#1{#1} \gdef\posetElementSymbol#1{#1} \gdef\latticeMeetSymbol{\wedge} \gdef\latticeJoinSymbol{\vee} \gdef\latticeTop{\top} \gdef\latticeBottom{\bot} \gdef\semilatticeMeetSymbol{\wedge} \gdef\semilatticeJoinSymbol{\vee} \gdef\semilatticeTop{\top} \gdef\semilatticeBottom{\bot} \gdef\semilatticeSemimeetSymbol{\wedge} \gdef\semilatticeSemijoinSymbol{\vee} \gdef\latticeGreaterSymbol{>} \gdef\latticeGreaterEqualSymbol{\ge} \gdef\latticeLessSymbol{<} \gdef\latticeLessEqualSymbol{\le} \gdef\posetGreaterSymbol{>} \gdef\posetGreaterEqualSymbol{\ge} \gdef\posetLessSymbol{<} \gdef\posetLessEqualSymbol{\le} \gdef\posetCoversSymbol{⋗} \gdef\posetCoveredBySymbol{⋖} \gdef\grpname#1{\operatorname{\mathsf{#1}}} \gdef\mkg#1#2#3{\grpname{#1}({#2},{#3})} \gdef\mka#1#2#3{\mathfrak{#1}({#2},{#3})} \gdef\generalLinearAlgebra#1#2{\mka{gl}{#1}{#2}} \gdef\generalLinearGroup#1#2{\mkg{GL}{#1}{#2}} \gdef\specialLinearAlgebra#1#2{\mka{sl}{#1}{#2}} \gdef\specialLinearGroup#1#2{\mkg{SL}{#1}{#2}} \gdef\projectiveGeneralLinearAlgebra#1#2{\mka{pgl}{#1}{#2}} \gdef\projectiveGeneralLinearGroup#1#2{\mkg{PGL}{#1}{#2}} \gdef\projectiveSpecialLinearAlgebra#1#2{\mka{psl}{#1}{#2}} \gdef\projectiveSpecialLinearGroup#1#2{\mkg{PSL}{#1}{#2}} \gdef\orthogonalAlgebra#1#2{\mka{o}{#1}{#2}} \gdef\orthogonalGroup#1#2{\mkg{O}{#1}{#2}} \gdef\specialOrthogonalAlgebra#1#2{\mka{so}{#1}{#2}} \gdef\specialOrthogonalGroup#1#2{\mkg{SO}{#1}{#2}} \gdef\unitaryAlgebra#1{\mka{u}{#1}{#2}} \gdef\unitaryGroup#1{\mkg{U}{#1}{#2}} \gdef\specialUnitaryAlgebra#1#2{\mka{su}{#1}{#2}} \gdef\specialUnitaryGroup#1#2{\mkg{su}{#1}{#2}} \gdef\spinAlgebra#1#2{\mka{spin}{#1}{#2}} \gdef\spinGroup#1#2{\mkg{Spin}{#1}{#2}} \gdef\pinAlgebra#1#2{\mka{pin}{#1}{#2}} \gdef\pinGroup#1#2{\mkg{Pin}{#1}{#2}} \gdef\symmetricGroup#1{\grpname{Sym}({#1})} \gdef\presentation#1{#1} \gdef\groupPresentation#1#2{\left\langle\,{#1}\,\,\middle|\mathstrut\,\,{#2}\,\right\rangle} \gdef\groupRelationIso{=} \gdef\groupGenerator#1{#1} \gdef\groupRelator#1{#1} \gdef\groupElement#1{#1} \gdef\identityElement#1{#1} \gdef\groupoidElement#1{#1} \gdef\groupIdentity#1{#1} \gdef\groupoidIdentityElement#1#2{#1_{#2}} \gdef\ringIdentity#1{#1} \gdef\iconstruct#1#2{ {#1}\,\,\middle|{\large\mathstrut}\,\,{#2}} \gdef\setConstructor#1#2{\left\{\,\iconstruct{#1}{#2}\,\right\}} \gdef\multisetConstructor#1#2{\left\{\mkern{-2.3pt}\left|\,\,\iconstruct{#1}{#2}\,\right|\mkern{-2.3pt}\right\}} \gdef\cardinalityConstructor#1#2{\left|\,\iconstruct{#1}{#2}\,\right|} \gdef\setToMultiset#1{ {#1}^\uparrow} \gdef\multisetToSet#1{ {#1}^\downarrow} \gdef\subsets#1{\setLetter({#1})} \gdef\signedSubsets#1{\signedSetLetter({#1})} \gdef\multisets#1{\multisetLetter({#1})} \gdef\signedMultisets#1{\signedMultisetLetter({#1})} \gdef\circleSpaceSymbol{S} \gdef\topologicalSpace#1{#1} \gdef\bundleSection#1{#1} \gdef\bundleProjection#1{#1} \gdef\setSymbol#1{#1} \gdef\signedSetSymbol#1{#1} \gdef\multisetSymbol#1{#1} \gdef\signedMultisetSymbol#1{#1} \gdef\setElementSymbol#1{#1} \gdef\signedSetElementSymbol#1{#1} \gdef\multisetElementSymbol#1{#1} \gdef\signedMultisetElementSymbol#1{#1} \gdef\negated#1{\bar{#1}} \gdef\positiveSignedPart#1{ {#1}^+} \gdef\negativeSignedPart#1{ {#1}^-} \gdef\multisetMultiplicitySymbol{\,\raisebox{.1em}{\small\#}\mkern{.1em}\,} \gdef\signedMultisetMultiplicitySymbol{\,\raisebox{.1em}{\small\#}\mkern{.1em}\,} \gdef\boundMultiplicityFunction#1{ {#1}^{\sharp}} \gdef\boundSignedMultiplicityFunction#1{\operatorname{ {#1}^{\sharp}}} \gdef\constructor#1#2{\left.{#1}\,\,\middle|\mathstrut\,\,{#2}\right.} \gdef\elemOf#1#2{ { {#1} \in {#2} }} \gdef\notElemOf#1#2{ { {#1} \notin {#2} }} \gdef\edgeOf#1#2{ { {#1} {\in}_E {#2} }} \gdef\vertOf#1#2{ { {#1} {\in}_V {#2} }} \gdef\pathOf#1#2{ { {#1} {\in}_P {#2} }} \gdef\pathType#1{\operatorName{path}{#1}} \gdef\vertexType#1{\operatorName{vertex}{#1}} \gdef\edgeType#1{\operatorName{edge}{#1}} \gdef\multisetType#1{\operatorName{mset}{#1}} \gdef\signedMultisetType#1{\operatorName{mset^*}{#1}} \gdef\unitInterval{\mathbb{I}} \gdef\fromTo#1{#1} \gdef\fromToSymbol{\mapsto} \gdef\vertexCountOf#1{|{#1}|} \gdef\vertices#1{ V_{#1} } \gdef\edges#1{ E_{#1} } \gdef\vertexField#1{#1} \gdef\edgeField#1{#1} \gdef\pathVector#1{\mathbf{#1}} \gdef\pathVectorSpace#1{\mathscr{#1}} \gdef\baseField#1{#1} \gdef\finiteField#1{\mathbb{F}_{#1}} \gdef\functionSpace#1#2{#2^{#1}} \gdef\finiteTotalFunctionSpace#1#2{#2^{\sub #1}} \gdef\pathGroupoid#1{ { \Gamma_{#1} }} \gdef\forwardPathQuiver#1#2{ {\overrightharpoon{#1}_{#2}}} \gdef\backwardPathQuiver#1#2{ {\overrightharpoon{#1}^{#2}}} \gdef\pathQuiver#1{ {\overrightharpoon{#1}}} \gdef\mto#1#2{ {#1}\mapsto{#2}} \gdef\mtoSymbol{\mapsto} \gdef\groupWordRewriting#1{\langle{#1}\rangle} \gdef\rewrite#1#2{ {#1}\mapsto{#2}} \gdef\rewritingRule#1#2{ {#1}\mapsto{#2}} \gdef\rewritingSystem#1{\mathcal{#1}} \gdef\multiwayBFS#1{\textrm{bfs}({#1})} \gdef\rewritingStateBinding#1#2{ {\left.{#1}\!\mid\!{#2}\right.}} \gdef\rewritingRuleBinding#1#2{#1{\left[\,{#2}\,\right]}} \gdef\namedSystem#1{\mathtt{#1}} \gdef\genericRewritingSystem{\namedSystem{Sys}} \gdef\stringRewritingSystem{\namedSystem{Str}} \gdef\circularStringRewritingSystem{\namedSystem{CStr}} \gdef\turingMachineRewritingSystem{\namedSystem{TM}} \gdef\cellularAutomatonRewritingSystem{\namedSystem{CA}} \gdef\graphRewritingSystem{\namedSystem{Gr}} \gdef\hypergraphRewritingSystem{\namedSystem{HGr}} \gdef\petriNetRewritingSystem{\namedSystem{Petri}} \gdef\localStates#1{\localStatesSymbol^#1} \gdef\regionalStates#1{\regionalStatesSymbol^#1} \gdef\globalStates#1{\globalStatesSymbol^#1} \gdef\keySubStates#1{\keySubStatesSymbol^#1} \gdef\valueSubStates#1{\valueSubStatesSymbol^#1} \gdef\localState#1#2{#2_{#1}} \gdef\regionalState#1{#1} \gdef\globalState#1{#1} \gdef\keySubState#1{#1} \gdef\valueSubState#1{#1} \gdef\lhsState#1{#1_{L}} \gdef\rhsState#1{#1_{R}} \gdef\rewriteLHSRegionalState#1{#1_{L}} \gdef\rewriteRHSRegionalState#1{#1_{R}} \gdef\regionalStateForm#1{\waform{(}#1\waform{)}} \gdef\invalidRegionalState{\rform{\times}} \gdef\emptyRegionalState{\regionalStateForm{}} \gdef\regionalSubstateSymbol{\sqsubseteq} \gdef\regionalSuperstateSymbol{\sqsupseteq} \gdef\comparableRegionalStatesSymbol{\mathbin{\square}} \gdef\incomparableRegionalStatesSymbol{\mathbin{\boxtimes}} \gdef\namedStateSet#1{\mathbf #1} \gdef\localStatesSymbol{\namedStateSet L} \gdef\regionalStatesSymbol{\namedStateSet R} \gdef\globalStatesSymbol{\namedStateSet G} \gdef\keySubStatesSymbol{\namedStateSet L_K} \gdef\valueSubStatesSymbol{\namedStateSet L_V} \gdef\localStateSymbol#1{#1} \gdef\regionalStateSymbol#1{#1} \gdef\globalStateSymbol#1{#1} \gdef\keySubStateSymbol#1{#1} \gdef\valueSubStateSymbol#1{#1} \gdef\infixComposeLocalStatesSymbol{\_} \gdef\composeLocalStatesSymbol{\operatorname{glue}} \gdef\composeLocalStatesForm#1{\composeLocalStatesSymbol(#1)} \gdef\ncard#1{\card{\inverted{#1}}} \gdef\mcard#1{\card{\mirror{#1}}} \gdef\nmcard#1{\card{\inverted{\mirror{#1}}}} \gdef\assocArray#1{\left\langle {#1} \right\rangle} \gdef\openMultiset{\lBrace} \gdef\closeMultiset{\rBrace} \gdef\set#1{\{ {#1} \}} \gdef\signedSet#1{\{ {#1} \}} \gdef\list#1{\{ {#1} \}} \gdef\multiset#1{\openMultiset {#1} \closeMultiset} \gdef\signedMultiset#1{\openMultiset {#1} \closeMultiset} \gdef\styledSet#1#2{#1\{ {#1} #1\}} \gdef\styledList#1#2{#1\{ {#1} #1\}} \gdef\styledMultiset#1#2{#1\openMultiset {#2} #1\closeMultiset} \gdef\styledSignedMultiset#1#2{\openMultiset {#2} \closeMultiset} \gdef\permutationCycle#1{#1} \gdef\permutationCycleSymbol{\to} \gdef\permutationSet#1{#1} \gdef\permutationSetSymbol{;} \gdef\transposition#1#2{ {#1} \leftrightarrow {#2}} \gdef\tuple#1{( {#1} )} \gdef\concat#1{ {#1} } \gdef\paren#1{\left( {#1} \right)} \gdef\ceiling#1{\lceil{#1}\rceil} \gdef\floor#1{\lfloor{#1}\rfloor} \gdef\translationVector#1{\left[{#1}\right]_{\textrm{T}}} \gdef\quotient#1#2{ {#1} / {#2}} \gdef\compactQuotient#1#2#3{ {#1}\;{\upharpoonright_{#2}}\;{#3}} \gdef\multilineQuotient#1#2{\frac{#1}{#2}} \gdef\idElem#1{e_{#1}} \gdef\minus#1{-{#1}} \gdef\elem{\ \in\ } \gdef\vsp{\mkern{0.4pt}} \gdef\iGmult{\vsp} \gdef\gmult{\vsp\ast\vsp} \gdef\Gmult{\vsp\ast\vsp} \gdef\gdot{\vsp\cdot\vsp} \gdef\gDot{\vsp\mathbin{\largeDot}\vsp} \gdef\mdot{\vsp\cdot\vsp} \gdef\smallblackcirc{\vsp\raisebox{0.15em}{\tiny∙}\vsp} \gdef\smallwhitecirc{\vsp\raisebox{0.15em}{\tiny∘}\vsp} \gdef\sgdot{\mathbin{\smallwhitecirc}} \gdef\srdot{\mathbin{\smallblackcirc}} \gdef\srplus{+} \gdef\ellipsis{\,\wbform{...}\,} \gdef\verticalEllipsis{\vdots} \gdef\appliedRelation#1{#1} \gdef\setUnionSymbol{\cup} \gdef\setIntersectionSymbol{\cap} \gdef\setRelativeComplementSymbol{-} \gdef\msetCol{\textcolor{bb4444}} \gdef\repeatedMultiset#1#2{#1\,#2} \gdef\msrdot{\mathbin{\smallblackcirc}} \gdef\msrplus{+} \gdef\smrdot{\mathbin{\smallblackcirc}} \gdef\smrplus{+} \gdef\dotminus{\mathbin{\dot{-}}} \gdef\dotcap{\mathbin{\dot{\cap}}} \gdef\dotcup{\mathbin{\dot{\cup}}} \gdef\multisetUnionSymbol{\dotcup} \gdef\multisetIntersectionSymbol{\dotcap} \gdef\multisetRelativeComplementSymbol{\dotminus} \gdef\multisetSumSymbol{\dotplus} \gdef\cartesianProductSymbol{\times} \gdef\functionType#1#2{ {#1} \to {#2}} \gdef\functionSignature#1#2#3{ { {#1} : {#2} \to {#3}}} \gdef\partialFunctionSignature#1#2#3{ { {#1} : {#2} \rightharpoonup {#3}}} \gdef\poly#1{#1} \gdef\quiverProdPoly#1{#1} \gdef\quiverProdPower#1#2{#1^{#2}} \gdef\quiverProdTimes#1{#1} \gdef\parenLabeled#1#2{#1\ ({#2})} \gdef\parenRepeated#1#2{\parenLabeled{#1}{ {#2}\text{ times}}} \gdef\underLabeled#1#2{\underbrace{#1}_{#2}} \gdef\underRepeated#1#2{\underbrace{#1}_{#2\text{ times}}} \gdef\overLabeled#1#2{\overbrace{#1}^{#2}} \gdef\overRepeated#1#2{\overbrace{#1}^{#2\text{ times}}} \gdef\modLabeled#1#2{ {#1 }\textrm{ mod }{#2}} \gdef\freeGroup#1{F_{#1}} \gdef\cyclicGroup#1{\mathbb{Z}_{#1}} \gdef\componentSuperQuiverOfSymbol{\succ} \gdef\setCardinality#1{|{#1}|} \gdef\multisetCardinality#1{|{#1}|} \gdef\dependentQuiverProductSymbol{\mathbin{\times}} \gdef\rightIndependentQuiverProductSymbol{\mathbin{⋊}} \gdef\leftIndependentQuiverProductSymbol{\mathbin{⋉}} \gdef\rightStrongQuiverProductSymbol{\mathbin{⧒}} \gdef\leftStrongQuiverProductSymbol{\mathbin{⧑}} \gdef\rightFiberQuiverProductSymbol{\mathbin{⧕}} \gdef\leftFiberQuiverProductSymbol{\mathbin{⧔}} \gdef\lockedQuiverProductSymbol{\mathbin{\searrow}} \gdef\rightFreeQuiverProductSymbol{\mathbin{\smallerthan}} \gdef\leftFreeQuiverProductSymbol{\mathbin{\largerthan}} \gdef\strongIndependentQuiverProductSymbol{\mathbin{⨝}} \gdef\cartesianQuiverProductSymbol{\mathbin{□}} \gdef\strongQuiverProductSymbol{\mathbin{⊠}} \gdef\graphUnionSymbol{\sqcup} \gdef\graphProductSymbol{\times} \gdef\inlineProdSymbol{|} \gdef\serialCardSymbol{ {:}} \gdef\parallelCardSymbol{ {\mid}} \gdef\cardinalSequenceSymbol{ {:}} \gdef\cardinalProduct#1{(#1)} \gdef\vertexProduct#1{(#1)} \gdef\edgeProduct#1{(#1)} \gdef\cardinalProductSymbol{\inlineProdSymbol} \gdef\vertexProductSymbol{\inlineProdSymbol} \gdef\edgeProductSymbol{\inlineProdSymbol} \gdef\verticalVertexProduct#1#2{\cfrac{#1}{#2}} \gdef\verticalCardinalProduct#1#2{\cfrac{#1}{#2}} \gdef\indexSum#1#2#3{ {\sum_{#2}^{#3} #1}} \gdef\indexProd#1#2#3{ {\prod_{#2}^{#3} #1}} \gdef\indexMax#1#2#3{ {\max_{#2}^{#3} #1}} \gdef\indexMin#1#2#3{ {\min_{#2}^{#3} #1}} \gdef\indexUnion#1#2#3{ {\bigcup_{#2}^{#3} #1}} \gdef\indexIntersection#1#2#3{ {\bigcap_{#2}^{#3} #1}} \gdef\indexGraphUnion#1#2#3{ {\bigcup_{#2}^{#3} #1}} \gdef\indexGraphDisjointUnion#1#2#3{ {\bigcup_{#2}^{#3} #1}} \gdef\styledIndexSum#1#2#3#4{ {#1\sum_{#3}^{#4} #2}} \gdef\styledIndexProd#1#2#3#4{ {#1\prod_{#3}^{#4} #2}} \gdef\styledIndexMax#1#2#3#4{ {#1\max_{#3}^{#4} #2}} \gdef\styledIndexMin#1#2#3#4{ {#1\min_{#3}^{#4} #2}} \gdef\indexSumSymbol{\sum} \gdef\indexProdSymbol{\prod} \gdef\indexMaxSymbol{\max} \gdef\indexMinSymbol{\min} \gdef\openInterval#1#2{(#1,#2)} \gdef\closedInterval#1#2{[#1,#2]} \gdef\openClosedInterval#1#2{(#1,#2]} \gdef\closedOpenInterval#1#2{[#1,#2)} \gdef\oneTo#1{1..{#1}} \gdef\zeroTo#1{0..{#1}} \gdef\qstring#1{\mathtt{"}{#1}\mathtt{"}} \gdef\wstring#1{\textcolor{6b6b6b}{#1}} \gdef\qchar#1{\mathtt{'}{#1}\mathtt{'}} \gdef\lstr#1{\mathtt{#1}} \gdef\lchar#1{\mathtt{#1}} \gdef\string#1{ {#1}} \gdef\character#1{ {#1}} \gdef\homomorphismMapping#1{\assocArray{#1}} \gdef\starModifier#1{ {#1}^*} \gdef\translationPresentation#1{\textrm{Z}_{#1}} \gdef\starTranslationPresentation#1{\textrm{Z}^*_{#1}} \gdef\translationPathValuation#1{\mathcal{\overrightharpoon Z}_{#1}} \gdef\starTranslationPathValuation#1{\overrightharpoon{\mathcal{Z}^*_{#1}}} \gdef\translationWordHomomorphism#1{\mathcal{Z}_{#1}} \gdef\starTranslationWordHomomorphism#1{\mathcal{Z}^*_{#1}} \gdef\translationCardinalValuation#1{\textrm{T}_{#1}} \gdef\starTranslationCardinalValuation#1{\textrm{T}^*_{#1}} \)
Multisets

Multisets

Introduction

History

The multiset is a simple and natural piece of mathematical technology that has been strangely underused in the last hundred years. That the multiset has failed to live up to its potential is due probably to historical accident. One possible explanation is that as the need for foundational rigor became urgent, modern mathematics quickly standardized on the set as a kind of universal building block, starving out other data structures, like the multiset. Such is the unfortunate role of fashion in mathematics. Luckily, multisets have seen renewed interest with the work of more computation-oriented mathematicians like Donald Knuth.

Motivation

We are taking the time to explain multisets because they play an important interpretative role, giving us an alternative way of understanding algebraic structures. This role will only become clear in the next two sections: Word rings, where we'll elements of the word ring as multisets of words ("multiwords"), and Adjacency, where we'll interpret matrices as multisets of paths ("multipaths"). Interleaving the explanation of multisets with those topics would be confusing, so we'll front-load the work in understanding multisets here, in one place.

Sets and multisets

Sets vs multisets

To contrast sets with multisets, we first repeat some basic facts about sets.

Sets are the building blocks of modern mathematics. They consist of a collection of elements: \(\sym{X} = \set{\sym{x_1},\sym{x_2},\ellipsis ,\sym{x_{\sym{n}}}}\). We can express that an element is a member of a set with the notation \(\elemOf{\setElementSymbol{x}}{\setSymbol{X}}\).

Among the fundamental properties of a sets is that the elements have no defined order. Hence, the expressions \(\set{\rform{\card{r}},\bform{\card{b}}}\textAnd \set{\bform{\card{b}},\rform{\card{r}}}\) describe the same set. Furthermore, an object is either an element of a set or it is not. It is meaningless to say that it occurs twice, for example. Hence, the expressions \(\set{\rform{\card{r}},\rform{\card{r}},\bform{\card{b}}}\textAnd \set{\rform{\card{r}},\bform{\card{b}}}\) describe the same set – especially when constructing sets we rely on this redundancy being irrelevant.

If we instead specify that repetition does matter, we arrive at the idea of a multiset. A multiset can contain an object more than once. The number of times a multiset contains an object will be called the multiplicity of that object.

We'll write multisets with double-struck braces: \(\sym{X} = \multiset{\sym{x_1},\sym{x_2},\ellipsis ,\sym{x_{\sym{n}}}}\). Hence, \(\multiset{\rform{\card{r}},\rform{\card{r}},\bform{\card{b}}}\textAnd \multiset{\rform{\card{r}},\bform{\card{b}}}\) describe different multisets: the multiplicity of \(\rform{\card{r}}\) is \(1\) in the first and \(2\) in the second.

We’ll denote the multiplicity of an object \(\multisetElementSymbol{x}\) in a multiset \(\multisetSymbol{M}\) by \(\multisetSymbol{M}\multisetMultiplicitySymbol \multisetElementSymbol{x}\). For example, in the multiset \(\multisetSymbol{M} = \multiset{\rform{\card{r}},\rform{\card{r}},\bform{\card{b}}}\), we have that \(\multisetSymbol{M}\multisetMultiplicitySymbol \rform{\card{r}} = 2\), \(\multisetSymbol{M}\multisetMultiplicitySymbol \bform{\card{b}} = 1\), and \(\multisetSymbol{M}\multisetMultiplicitySymbol \gform{\card{g}} = 0\).

The set of multisets

The powerset \(\powerSet{\multisetSymbol{B}}\) of a set \(\multisetSymbol{B}\) is the set of subsets of \(\multisetSymbol{B}\). We'll call these the sets on \(\multisetSymbol{B}\), and \(\multisetSymbol{B}\) the base set.

We can similarly form the set of multisets whose objects are taken from \(\multisetSymbol{B}\), written \(\multisets{\multisetSymbol{B}}\). We'll call these the multisets on \(\multisetSymbol{B}\).

Any particular object from the base set can occur any finite number of times in one such multiset, so \(\multisets{\multisetSymbol{B}}\) is generally an infinite set (unless \(\multisetSymbol{B}\) is empty). Let's look at some examples of this simple and natural idea.

If \(\multisetSymbol{B}\) is a singleton, that is, contains only one element, then the multisets in \(\multisets{\multisetSymbol{B}}\) can contain this element any finite number of times. Here we list some multisets in \(\multisets{\multisetSymbol{B}}\) for \(\multisetSymbol{B} = \set{\rform{\card{r}}}\):

\[ \multisets{\set{\rform{\card{r}}}} = \set{\multiset{},\multiset{\rform{\card{r}}},\multiset{\rform{\card{r}},\rform{\card{r}}},\multiset{\rform{\card{r}},\rform{\card{r}},\rform{\card{r}}},\ellipsis } \]

Clearly, we can identify these multisets with the positive integers, since they count the number of times that \(\rform{\card{r}}\) is present.

If \(\multisetSymbol{B}\) contains two elements, then the multisets in \(\multisets{\multisetSymbol{B}}\) can be identified with pairs of positive integers, counting how many times the two elements are present. Here we list some elements of the set \(\multisets{\multisetSymbol{B}}\) for \(\multisetSymbol{B} = \set{\rform{\card{r}},\bform{\card{b}}}\):

\[ \multisets{\set{\rform{\card{r}},\bform{\card{b}}}} = \set{\multiset{},\multiset{\rform{\card{r}}},\multiset{\bform{\card{b}}},\multiset{\rform{\card{r}},\rform{\card{r}}},\multiset{\rform{\card{r}},\bform{\card{b}}},\multiset{\bform{\card{b}},\bform{\card{b}}},\multiset{\rform{\card{r}},\rform{\card{r}},\rform{\card{r}}},\multiset{\rform{\card{r}},\rform{\card{r}},\bform{\card{b}}},\ellipsis } \]

More generally, we can identify any multiset \(\elemOf{\multisetSymbol{M}}{\multisets{\multisetSymbol{B}}}\) with the function \(\functionSignature{\function{\boundMultiplicityFunction{\multisetSymbol{M}}}}{\multisetSymbol{B}}{\mathbb{N}}\) that takes an element of \(\multisetSymbol{B}\) and returns its multiplicity in \(\multisetSymbol{M}\).

For example, we can identify the multiset \(\multisetSymbol{M} = \multiset{\rform{\card{r}},\rform{\card{r}},\bform{\card{b}}}\) with the function \(\boundMultiplicityFunction{\multisetSymbol{M}} = \assocArray{\mto{\rform{\card{r}}}{2},\mto{\bform{\card{b}}}{1}}\).

Formally, then, we have a bijection between multisets on \(\multisetSymbol{B}\) on one side and functions from \(\multisetSymbol{B}\) to the natural numbers on the other (multiplicity functions):

\[ \multisets{\setSymbol{B}}\bijectiveSymbol \functionSpace{\setSymbol{B}}{\baseField{\mathbb{N}}} \]

We'll shortly see how we can encode the natural operations on a multiset in terms of operations on such multiplicity functions.

Translating between sets and multisets

We can identify a set \(\multisetSymbol{X}\) with a multiset in which each element \(\elemOf{\setElementSymbol{x}}{\multisetSymbol{X}}\) appears exactly once. For example:

\[ \set{\rform{\card{r}},\bform{\card{b}}}\isomorphicSymbol \multiset{\rform{\card{r}},\bform{\card{b}}} \]

In other words, we have a bijection between on one hand \(\powerSet{\multisetSymbol{B}}\), the sets on \(\multisetSymbol{B}\), and on the other hand the multisets on \(\multisetSymbol{B}\) with maximum multiplicity 1:

\[ \subsets{B}\bijectiveSymbol \setConstructor{\multisetSymbol{M}}{\elemOf{\multisetSymbol{M}}{\multisets{B}},\max(\boundMultiplicityFunction{\multisetSymbol{M}}) = 1} \]

To a given set \(\multisetSymbol{X}\) in terms we define the corresponding multiset via its multiplicity function \(\boundMultiplicityFunction{\multisetSymbol{X}}\):

\[ \boundMultiplicityFunction{\multisetSymbol{X}}\defEqualSymbol \mto{\setElementSymbol{b}}{\begin{cases} 1 &\text{if } \elemOf{\setElementSymbol{b}}{\setSymbol{X}}\\ 0 &\text{if } \text{otherwise}\\ \end{cases} } \]

Conversely, given a multiset defined by \(\boundMultiplicityFunction{\multisetSymbol{X}}\) with \(\max(\boundMultiplicityFunction{\multisetSymbol{X}}) = 1\), we define the corresponding set \(\multisetSymbol{X}\) as follows:

\[ \setSymbol{X}\defEqualSymbol \setConstructor{\setElementSymbol{b}}{\elemOf{\setElementSymbol{b}}{\setSymbol{B}},\function{\boundMultiplicityFunction{\multisetSymbol{X}}}(\setElementSymbol{b}) = 1} \]

Projection and lift

We can define this bijection via two functions called projection and lift:

\[ \begin{csarray}{ccccc}{acccc} \lift & : & \subsets{\setSymbol{X}} & \rarr & \multisets{X}\\ \projection & : & \multisets{X} & \rarr & \subsets{\setSymbol{X}} \end{csarray} \]

Lift takes a set and gives the multiset that contains each element exactly once:

\[ \lift(\setSymbol{A})\defEqualSymbol \multisetConstructor{\multisetElementSymbol{x}}{\elemOf{\multisetElementSymbol{x}}{\setSymbol{A}}} \]

Projection takes a multiset and gives the set of its elements:

\[ \projection(\setSymbol{A})\defEqualSymbol \setConstructor{\multisetElementSymbol{x}}{\elemOf{\multisetElementSymbol{x}}{\setSymbol{A}}} \]

Lifting and projecting a set yields the same set:

\[ \projection(\lift(\setSymbol{A}))\identicallyEqualSymbol \setSymbol{A} \]

Operations on multisets

How can we combine multisets? We'll look to sets for inspiration.

For sets \(\multisetSymbol{X},\multisetSymbol{Y}\), we can form the union \(\multisetSymbol{X}\setUnionSymbol \multisetSymbol{Y}\) – the set of elements that are in \(\multisetSymbol{X}\) and/or \(\multisetSymbol{Y}\), the intersection \(\multisetSymbol{X}\setIntersectionSymbol \multisetSymbol{Y}\) – the set of elements in both \(\multisetSymbol{X}\textAnd \multisetSymbol{Y}\), and the relative complement \(\multisetSymbol{X}\setRelativeComplementSymbol \multisetSymbol{Y}\) – the set of elements in \(\multisetSymbol{X}\) but not in \(\multisetSymbol{Y}\).

\[ \begin{aligned} \setSymbol{X}\setUnionSymbol \setSymbol{Y}&\defEqualSymbol \setConstructor{\setElementSymbol{x}}{\paren{\elemOf{\setElementSymbol{x}}{\setSymbol{X}}}\orSymbol \paren{\elemOf{\setElementSymbol{x}}{\setSymbol{Y}}}}\\ \setSymbol{X}\setIntersectionSymbol \setSymbol{Y}&\defEqualSymbol \setConstructor{\setElementSymbol{x}}{\paren{\elemOf{\setElementSymbol{x}}{\setSymbol{X}}}\andSymbol \paren{\elemOf{\setElementSymbol{x}}{\setSymbol{Y}}}}\\ \setSymbol{X}\setRelativeComplementSymbol \setSymbol{Y}&\defEqualSymbol \setConstructor{\setElementSymbol{x}}{\paren{\elemOf{\setElementSymbol{x}}{\setSymbol{X}}}\andSymbol \paren{\notElemOf{\setElementSymbol{x}}{\setSymbol{Y}}}}\end{aligned} \]

For multisets \(\multisetSymbol{M}\textAnd \multisetSymbol{N}\), we now define the equivalent operations multiset union \(\multisetSymbol{M}\multisetUnionSymbol \multisetSymbol{N}\), multiset intersection \(\multisetSymbol{M}\multisetIntersectionSymbol \multisetSymbol{N}\), and multiset relative complement \(\multisetSymbol{M}\multisetRelativeComplementSymbol \multisetSymbol{N}\). Notice the dot to distinguish these operations from their set counterparts.

We will define these in terms of the multiplicity functions \(\boundMultiplicityFunction{\multisetSymbol{M}}\textAnd \boundMultiplicityFunction{\multisetSymbol{N}}\):

\[ \begin{aligned} \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetUnionSymbol \multisetSymbol{N}}}&\defEqualSymbol \max(\boundMultiplicityFunction{\multisetSymbol{M}},\boundMultiplicityFunction{\multisetSymbol{N}})\\ \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetIntersectionSymbol \multisetSymbol{N}}}&\defEqualSymbol \min(\boundMultiplicityFunction{\multisetSymbol{M}},\boundMultiplicityFunction{\multisetSymbol{N}})\\ \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetRelativeComplementSymbol \multisetSymbol{N}}}&\defEqualSymbol \max(\boundMultiplicityFunction{\multisetSymbol{M}} - \boundMultiplicityFunction{\multisetSymbol{N}},0)\end{aligned} \]

Here, when we apply \(\max\textAnd \min\) to functions, we are creating a new function that applies that operation to their outputs e.g. \(\function{\max(\function{f},\function{g})}(\multisetElementSymbol{x})\defEqualSymbol \max(\function{f}(\multisetElementSymbol{x}),\function{g}(\multisetElementSymbol{x}))\).

Examples

Here is an example of a multiset union and the corresponding operation on multiplicity functions, where the base set is \(\multisetSymbol{B} = \set{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}\):

\[ \begin{array}{cccccc} \multiset{\rform{\card{r}},\rform{\card{r}},\gform{\card{g}}} & \multisetUnionSymbol & \multiset{\rform{\card{r}},\bform{\card{b}},\bform{\card{b}}} & = & \multiset{\rform{\card{r}},\rform{\card{r}},\gform{\card{g}},\bform{\card{b}},\bform{\card{b}}} & \\ & & & & & \\ \begin{csarray}{rrcll}{abbba} \langle & \rform{\card{r}} & \mtoSymbol & 2, & \\ & \gform{\card{g}} & \mtoSymbol & 1, & \\ & \bform{\card{b}} & \mtoSymbol & 2 & \rangle \end{csarray} & \multisetUnionSymbol & \begin{csarray}{rrcll}{abbba} \langle & \rform{\card{r}} & \mtoSymbol & 1, & \\ & \gform{\card{g}} & \mtoSymbol & 0, & \\ & \bform{\card{b}} & \mtoSymbol & 2 & \rangle \end{csarray} & = & \begin{csarray}{rrcll}{abbba} \langle & \rform{\card{r}} & \mtoSymbol & 2, & \\ & \gform{\card{g}} & \mtoSymbol & 1, & \\ & \bform{\card{b}} & \mtoSymbol & 2 & \rangle \end{csarray} & \end{array} \]

Here's an example of an intersection:

\[ \begin{array}{cccccc} \multiset{\rform{\card{r}},\rform{\card{r}},\gform{\card{g}},\bform{\card{b}},\bform{\card{b}}} & \multisetIntersectionSymbol & \multiset{\rform{\card{r}},\bform{\card{b}},\bform{\card{b}}} & = & \multiset{\rform{\card{r}},\bform{\card{b}},\bform{\card{b}}} & \\ & & & & & \\ \begin{csarray}{rrcll}{abbba} \langle & \rform{\card{r}} & \mtoSymbol & 2, & \\ & \gform{\card{g}} & \mtoSymbol & 1, & \\ & \bform{\card{b}} & \mtoSymbol & 0 & \rangle \end{csarray} & \multisetIntersectionSymbol & \begin{csarray}{rrcll}{abbba} \langle & \rform{\card{r}} & \mtoSymbol & 1, & \\ & \gform{\card{g}} & \mtoSymbol & 0, & \\ & \bform{\card{b}} & \mtoSymbol & 2 & \rangle \end{csarray} & = & \begin{csarray}{rrcll}{abbba} \langle & \rform{\card{r}} & \mtoSymbol & 1, & \\ & \gform{\card{g}} & \mtoSymbol & 0, & \\ & \bform{\card{b}} & \mtoSymbol & 2 & \rangle \end{csarray} & \end{array} \]

Here's an example of a relative complement:

\[ \begin{array}{cccccc} \multiset{\rform{\card{r}},\rform{\card{r}},\gform{\card{g}},\bform{\card{b}},\bform{\card{b}}} & \multisetRelativeComplementSymbol & \multiset{\rform{\card{r}},\bform{\card{b}},\bform{\card{b}}} & = & \multiset{\rform{\card{r}},\gform{\card{g}}} & \\ & & & & & \\ \begin{csarray}{rrcll}{abbba} \langle & \rform{\card{r}} & \mtoSymbol & 2, & \\ & \gform{\card{g}} & \mtoSymbol & 1, & \\ & \bform{\card{b}} & \mtoSymbol & 0 & \rangle \end{csarray} & \multisetRelativeComplementSymbol & \begin{csarray}{rrcll}{abbba} \langle & \rform{\card{r}} & \mtoSymbol & 1, & \\ & \gform{\card{g}} & \mtoSymbol & 0, & \\ & \bform{\card{b}} & \mtoSymbol & 2 & \rangle \end{csarray} & = & \begin{csarray}{rrcll}{abbba} \langle & \rform{\card{r}} & \mtoSymbol & 1, & \\ & \gform{\card{g}} & \mtoSymbol & 1, & \\ & \bform{\card{b}} & \mtoSymbol & 0 & \rangle \end{csarray} & \end{array} \]

As extensions of set operations

The following elementary identities connect these operations on multisets to their counterparts on sets:

\[ \begin{aligned} \projection(\multisetSymbol{M}\multisetUnionSymbol \multisetSymbol{N})&= \projection(\multisetSymbol{M})\setUnionSymbol \projection(\multisetSymbol{N})\\ \projection(\multisetSymbol{M}\multisetIntersectionSymbol \multisetSymbol{N})&= \projection(\multisetSymbol{M})\setIntersectionSymbol \projection(\multisetSymbol{N})\\ \lift(\setSymbol{X}\setUnionSymbol \setSymbol{Y})&= \lift(\setSymbol{X})\multisetUnionSymbol \lift(\setSymbol{Y})\\ \lift(\setSymbol{X}\setIntersectionSymbol \setSymbol{Y})&= \lift(\setSymbol{X})\multisetIntersectionSymbol \lift(\setSymbol{Y})\end{aligned} \]

This occurs because the \(\max\textAnd \min\) behave like logical \(\orSymbol\) and \(\andSymbol\) when operating on multiplicities \(\set{0,1}\). It's in this sense that our multiset operations generalize the set operations.

Multiset sums

An additional operation is now available to us, which is simply to sum two multisets together:

\[ \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetSumSymbol \multisetSymbol{N}}}\defEqualSymbol \boundMultiplicityFunction{\multisetSymbol{M}} + \boundMultiplicityFunction{\multisetSymbol{N}} \]

As with \(\max\textAnd \min\), we are adding functions together in the sense that \(\function{\paren{\function{f} + \function{g}}}(\multisetElementSymbol{x})\defEqualSymbol \function{f}(\multisetElementSymbol{x}) + \function{g}(\multisetElementSymbol{x})\).

Here's an example of a multiset sum:

\[ \begin{array}{cccccc} \multiset{\rform{\card{r}},\rform{\card{r}},\gform{\card{g}}} & \multisetSumSymbol & \multiset{\rform{\card{r}},\bform{\card{b}},\bform{\card{b}}} & = & \multiset{\rform{\card{r}},\rform{\card{r}},\rform{\card{r}},\gform{\card{g}},\bform{\card{b}},\bform{\card{b}}} & \\ & & & & & \\ \begin{csarray}{rrcll}{abbba} \langle & \rform{\card{r}} & \mtoSymbol & 2, & \\ & \gform{\card{g}} & \mtoSymbol & 1, & \\ & \bform{\card{b}} & \mtoSymbol & 0 & \rangle \end{csarray} & \multisetSumSymbol & \begin{csarray}{rrcll}{abbba} \langle & \rform{\card{r}} & \mtoSymbol & 1, & \\ & \gform{\card{g}} & \mtoSymbol & 0, & \\ & \bform{\card{b}} & \mtoSymbol & 2 & \rangle \end{csarray} & = & \begin{csarray}{rrcll}{abbba} \langle & \rform{\card{r}} & \mtoSymbol & 3, & \\ & \gform{\card{g}} & \mtoSymbol & 1, & \\ & \bform{\card{b}} & \mtoSymbol & 2 & \rangle \end{csarray} & \end{array} \]

Multiples of a multiset

We introduce a convenient notation for the act of adding a multiset to itself \(\sym{n}\) times:

\[ \repeatedMultiset{\sym{n}}{\multisetSymbol{M}}\syntaxEqualSymbol \overRepeated{\multisetSymbol{M}\multisetSumSymbol \multisetSymbol{M}\multisetSumSymbol \ellipsis \multisetSumSymbol \multisetSymbol{M}}{\sym{n}} \]

As an example, we have: \(\repeatedMultiset{3}{\multiset{\rform{\card{r}},\bform{\card{b}}}}\syntaxEqualSymbol \multiset{\rform{\card{r}},\rform{\card{r}},\rform{\card{r}},\bform{\card{b}},\bform{\card{b}},\bform{\card{b}}}\)

In terms of multiplicity functions, the we simply multiply the multiplicity function:

\[ \boundMultiplicityFunction{\paren{\repeatedMultiset{\sym{n}}{\multisetSymbol{M}}}}\defEqualSymbol \sym{n} \, \boundMultiplicityFunction{\multisetSymbol{M}} \]

We have the following properties of multiples:

\[ \begin{aligned} \repeatedMultiset{\sym{n}}{\paren{\multisetSymbol{A}\multisetSumSymbol \multisetSymbol{B}}}&= \sym{n} \, \multisetSymbol{A}\multisetSumSymbol \sym{n} \, \multisetSymbol{B}\\ \repeatedMultiset{\sym{n}}{\paren{\multisetSymbol{A}\multisetUnionSymbol \multisetSymbol{B}}}&= \sym{n} \, \multisetSymbol{A}\multisetUnionSymbol \sym{n} \, \multisetSymbol{B}\\ \repeatedMultiset{\sym{n}}{\paren{\multisetSymbol{A}\multisetIntersectionSymbol \multisetSymbol{B}}}&= \sym{n} \, \multisetSymbol{A}\multisetIntersectionSymbol \sym{n} \, \multisetSymbol{B}\\ \repeatedMultiset{\paren{\sym{n} + \sym{m}}}{\multisetSymbol{A}}&= \repeatedMultiset{\sym{n}}{\multisetSymbol{A}}\multisetSumSymbol \repeatedMultiset{\sym{m}}{\multisetSymbol{A}}\\ \repeatedMultiset{\sym{n}}{\paren{\repeatedMultiset{\sym{m}}{\multisetSymbol{A}}}}&= \repeatedMultiset{\paren{\sym{n} \, \sym{m}}}{\multisetSymbol{A}}\\ \repeatedMultiset{1}{\multisetSymbol{A}}&= \multisetSymbol{A}\\ \repeatedMultiset{0}{\multisetSymbol{A}}&= \multiset{}\end{aligned} \]

Cardinality of a multiset

The cardinality of a multiset \(\multisetSymbol{A}\), written \(\multisetCardinality{\multisetSymbol{A}}\), is the number of elements of the multiset – in other words, the total multiplicity of all objects in the multiset. We can also express it as the total of the multiplicity function:

\[ \multisetCardinality{\multisetSymbol{A}}\defEqualSymbol \total(\boundMultiplicityFunction{\multisetSymbol{A}}) \]

We show some examples below:

\[ \begin{aligned} \multisetCardinality{\multiset{}}&= 0\\ \multisetCardinality{\multiset{\rform{\card{r}}}}&= 1\\ \multisetCardinality{\multiset{\rform{\card{r}},\rform{\card{r}}}}&= 2\\ \multisetCardinality{\multiset{\rform{\card{r}},\rform{\card{r}},\bform{\card{b}}}}&= 3\\ \multisetCardinality{\multiset{\bform{\card{b}},\bform{\card{b}},\bform{\card{b}}}}&= 3\end{aligned} \]

The following identities is easily verified:

\[ \begin{aligned} \multisetCardinality{\multisetSymbol{A}\multisetSumSymbol \multisetSymbol{B}}&= \multisetCardinality{\multisetSymbol{A}} + \multisetCardinality{\multisetSymbol{B}}\end{aligned} \]

So are the following inequalities:

\[ \begin{nsarray}{c} \multisetCardinality{\multisetSymbol{A}\multisetIntersectionSymbol \multisetSymbol{B}} \le \multisetCardinality{\multisetSymbol{A}},\multisetCardinality{\multisetSymbol{B}} \le \multisetCardinality{\multisetSymbol{A}\multisetUnionSymbol \multisetSymbol{B}}\\ \multisetCardinality{\multisetSymbol{A}} - \multisetCardinality{\multisetSymbol{B}} \le \multisetCardinality{\multisetSymbol{A}\multisetRelativeComplementSymbol \multisetSymbol{B}} \le \multisetCardinality{\multisetSymbol{A}} \le \multisetCardinality{\multisetSymbol{A}\multisetUnionSymbol \multisetSymbol{B}} \le \multisetCardinality{\multisetSymbol{A}} + \multisetCardinality{\multisetSymbol{B}} \end{nsarray} \]

Multiset-multiplicity duality

\[ \multisets{\setSymbol{X}} \]

We saw that multisets can be represented one-to-one by multiplicity functions.

There is a bijection between \(\multisets{\setSymbol{X}}\), the set of finite multisets on a base set \(\setSymbol{X}\), and the integrable functions from \(\setSymbol{X}\) to the natural numbers. By this we mean the set of functions with finite total. We'll write this set of functions as \(\finiteTotalFunctionSpace{\setSymbol{X}}{\baseField{\mathbb{N}}}\), because it necessarily consists of those functions in \(\functionSpace{\setSymbol{X}}{\baseField{\mathbb{N}}}\) that are only non-zero on a finite subset of \(\setSymbol{X}\):

\[ \finiteTotalFunctionSpace{\setSymbol{X}}{\baseField{\mathbb{N}}}\defEqualSymbol \setConstructor{\function{f}}{\elemOf{\function{f}}{\functionSpace{\setSymbol{X}}{\baseField{\mathbb{N}}}},\total(\function{f})< \infty } \]

Then the bijection between multisets and their multiplicity functions is given by:

\[ \begin{aligned} \multisets{\setSymbol{X}}& \approx \finiteTotalFunctionSpace{\setSymbol{X}}{\baseField{\mathbb{N}}}\\ \multisetSymbol{M}& \approx \boundMultiplicityFunction{\multisetSymbol{M}}\end{aligned} \]

More importantly, this bijection is an isomorphism, because it preserves the multiset operations of union, intersection, sum, etc., which we revisit here:

\[ \begin{aligned} \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetSumSymbol \multisetSymbol{N}}}&= \boundMultiplicityFunction{\multisetSymbol{M}} + \boundMultiplicityFunction{\multisetSymbol{N}}\\ \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetUnionSymbol \multisetSymbol{N}}}&= \max(\boundMultiplicityFunction{\multisetSymbol{M}},\boundMultiplicityFunction{\multisetSymbol{N}})\\ \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetIntersectionSymbol \multisetSymbol{N}}}&= \min(\boundMultiplicityFunction{\multisetSymbol{M}},\boundMultiplicityFunction{\multisetSymbol{N}})\\ \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetRelativeComplementSymbol \multisetSymbol{N}}}&= \max(\boundMultiplicityFunction{\multisetSymbol{M}} - \boundMultiplicityFunction{\multisetSymbol{N}},0)\\ \boundMultiplicityFunction{\paren{\repeatedMultiset{\sym{n}}{\multisetSymbol{M}}}}&= \sym{n} \, \paren{\boundMultiplicityFunction{\multisetSymbol{M}}}\end{aligned} \]

We say that the multiset \(\multisetSymbol{M}\) is dual to the multiplicity function \(\boundMultiplicityFunction{\multisetSymbol{M}}\).

We can express this isomorphism as a isomorphism of realms, where a realm is a set with the algebraic structure of sums, unions, and intersections. We will not enter into the realm of realms, however.

We can also see this duality as a particularly simple example of the duality between a space and its rings of functions. Here, the space is just \(\setSymbol{X}\) with the discrete topology, and the (semi)ring is the ring of functions \(\functionSignature{\function{f}}{\setSymbol{X}}{\mathbb{N}}\).

Multiset constructors

Let's consider a general multiset constructor:

\[ \multisetConstructor{\function{F}(\multisetElementSymbol{x}_1,\multisetElementSymbol{x}_2,\ellipsis ,\multisetElementSymbol{x}_{\sym{n}})}{\elemOf{\multisetElementSymbol{x}_1}{\multisetSymbol{M}_1},\elemOf{\multisetElementSymbol{x}_2}{\multisetSymbol{M}_2},\ellipsis ,\elemOf{\multisetElementSymbol{x}_{\sym{n}}}{\multisetSymbol{M}_{\sym{n}}}} \]

Here, \(\function{F}\) is some function that computes an output value from inputs \(\multisetElementSymbol{x}_1,\multisetElementSymbol{x}_2,\ellipsis ,\multisetElementSymbol{x}_{\sym{n}}\). Where do these inputs come from? The values of \(\multisetElementSymbol{x}_1,\multisetElementSymbol{x}_2,\ellipsis ,\multisetElementSymbol{x}_{\sym{n}}\) are drawn from multisets (or sets) \(\multisetSymbol{M}_1,\multisetSymbol{M}_2,\ellipsis ,\multisetSymbol{M}_{\sym{n}}\) via the bindings \(\elemOf{\multisetElementSymbol{x}_{\sym{i}}}{\multisetSymbol{M}_{\sym{i}}}\). Bindings are indications that the multiset constructor should "draw an element from \(\multisetSymbol{M}_{\sym{i}}\) and place it in \(\multisetElementSymbol{x}_{\sym{i}}\)". The multiset constructor performs bindings in all possible ways in order to build a multiset of results.

This is very similar to how ordinary set constructor notation works, except for one important distinction. In set constructor notation, a particular value can only be drawn from a set once – or more precisely, if we draw a particular value more than once, we would correspondingly collect a particular result \(\function{F}(\multisetElementSymbol{x}_1,\multisetElementSymbol{x}_2,\ellipsis ,\multisetElementSymbol{x}_{\sym{n}})\) more than once, but this would still result in the same constructed set, since multiplicity is ignored! In contrast, multisets care about multiplicity. Therefore we draw an element from each \(\multisetSymbol{M}_{\sym{i}}\) exactly as many times as it appears. Here we show this difference for a simple example:

\[ \begin{aligned} \setConstructor{\power{\setElementSymbol{x}}{2}}{\elemOf{\setElementSymbol{x}}{\set{0,1,2,3,4}}}&= \set{0,1,4,9,16}\\[1em] \multisetConstructor{\power{\setElementSymbol{x}}{2}}{\elemOf{\setElementSymbol{x}}{\multiset{0,0,0,1,2,2,3,4}}}&= \multiset{0,0,0,1,4,4,9,16}\end{aligned} \]

Similarly, when \(\function{F}\) produces a particular result multiple times, it will appear in the constructed multiset with the corresponding multiplicity. In the following example, \(\modFunction(\setElementSymbol{x},2)\) outputs the value \(0\) three times as \(\setElementSymbol{x}\) is bound the integers \(\zeroTo{4}\), because \(\modFunction(0,2) = \modFunction(2,2) = \modFunction(4,2) = 0\):

\[ \multisetConstructor{\modFunction(\setElementSymbol{x},2)}{\elemOf{\setElementSymbol{x}}{\set{0,1,2,3,4}}} = \multiset{0,0,0,1,1} \]

The set version of this construction doesn't capture this multiplicity:

\[ \setConstructor{\modFunction(\setElementSymbol{x},2)}{\elemOf{\setElementSymbol{x}}{\set{0,1,2,3,4}}} = \set{0,1} \]

Images and preimages of sets

We now review some basic facts about images and preimages of functions, to set the stage for analogous definitions for multisets. These ideas can be found in any undergraduate text on set theory. If this is familiar, you can jump to .

Definition

Consider a function \(\functionSignature{\function{f}}{\setSymbol{X}}{\setSymbol{Y}}\). We wish to apply it "set-wise", asking how it acts on a set of inputs (\(\setSymbol{A} \subseteq \setSymbol{X}\)) to give a set of outputs (\(\setSymbol{B} \subseteq \setSymbol{Y}\)). We similarly might wish to know what set of inputs corresponds to a given set of outputs.

To formalize these ideas, we define the image and preimage functions of \(\function{f}\), written \(\imageModifier{\function{f}}\) and \(\preimageModifier{\function{f}}\) respectively. They have the following signatures:

\[ \begin{csarray}{ccccc}{acccc} \function{f} & : & \setSymbol{X} & \rarr & \setSymbol{Y}\\ \imageModifier{\function{f}} & : & \subsets{X} & \rarr & \subsets{Y}\\ \preimageModifier{\function{f}} & : & \subsets{Y} & \rarr & \subsets{X} \end{csarray} \]

We define the image and preimage functions by using set constructor notation, where the image \(\imageModifier{\function{f}}\) function collects the outputs corresponding to the provided set of inputs, and the preimage \(\preimageModifier{\function{f}}\) collects the inputs corresponding to the provided set of outputs:

\[ \begin{aligned} \function{\imageModifier{\function{f}}}(\setSymbol{A})&\defEqualSymbol \setConstructor{\function{f}(\setElementSymbol{x})}{\elemOf{\setElementSymbol{x}}{\setSymbol{A}}}\\ \function{\preimageModifier{\function{f}}}(\setSymbol{B})&\defEqualSymbol \setConstructor{\setElementSymbol{x}}{\elemOf{\setElementSymbol{x}}{\setSymbol{X}},\elemOf{\function{f}(\setElementSymbol{x})}{\setSymbol{B}}}\end{aligned} \]

Example

Consider the function \(\functionSignature{\function{f}}{\set{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}}{\set{\rgform{\card{x}},\gbform{\card{y}}}}\) defined by \(\function{f} = \assocArray{\mto{\rform{\card{r}}}{\rgform{\card{x}}},\mto{\gform{\card{g}}}{\rgform{\card{x}}},\mto{\bform{\card{b}}}{\gbform{\card{y}}}}\).

We’ll say that e.g. \(\set{\rgform{\card{x}}}\) is the image of \(\set{\rform{\card{r}}}\) under \(\function{f}\), meaning that \(\function{\imageModifier{\function{f}}}(\set{\rform{\card{r}}}) = \set{\rgform{\card{x}}}\) (for singletons, people sometimes elide the braces). For \(\function{f}\), we have the following images:

\[ \begin{csarray}{rclrclrclrcl}{accicciccicc} & & & \function{\imageModifier{\function{f}}}(\set{\rform{\card{r}}}) & = & \set{\rgform{\card{x}}} & \function{\imageModifier{\function{f}}}(\set{\rform{\card{r}},\gform{\card{g}}}) & = & \set{\rgform{\card{x}}} & & & \\[0.5em] \function{\imageModifier{\function{f}}}(\set{}) & = & \set{} & \function{\imageModifier{\function{f}}}(\set{\gform{\card{g}}}) & = & \set{\rgform{\card{x}}} & \function{\imageModifier{\function{f}}}(\set{\rform{\card{r}},\bform{\card{b}}}) & = & \set{\rgform{\card{x}},\gbform{\card{y}}} & \function{\imageModifier{\function{f}}}(\set{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}) & = & \set{\rgform{\card{x}},\gbform{\card{y}}}\\[0.5em] & & & \function{\imageModifier{\function{f}}}(\set{\bform{\card{b}}}) & = & \set{\gbform{\card{y}}} & \function{\imageModifier{\function{f}}}(\set{\gform{\card{g}},\bform{\card{b}}}) & = & \set{\rgform{\card{x}},\gbform{\card{y}}} & & & \end{csarray} \]

Since we've listed the images of all subsets of \(\set{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}\), we can collect these together to give the explicit value of \(\imageModifier{\function{f}}\):

\[ \imageModifier{\function{f}} = \begin{csarray}{rrclrclrclrcll}{abbbcbbcbbcbba} \langle & \set{} & \mtoSymbol & \set{}, & \set{\rform{\card{r}}} & \mtoSymbol & \set{\rgform{\card{x}}}, & \set{\gform{\card{g}}} & \mtoSymbol & \set{\rgform{\card{x}}}, & \set{\bform{\card{b}}} & \mtoSymbol & \set{\gbform{\card{y}}}, & \\ & \set{\rform{\card{r}},\gform{\card{g}}} & \mtoSymbol & \set{\rgform{\card{x}}}, & \set{\rform{\card{r}},\bform{\card{b}}} & \mtoSymbol & \set{\rgform{\card{x}},\gbform{\card{y}}}, & \set{\gform{\card{g}},\bform{\card{b}}} & \mtoSymbol & \set{\rgform{\card{x}},\gbform{\card{y}}}, & \set{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}} & \mtoSymbol & \set{\rgform{\card{x}},\gbform{\card{y}}} & \rangle \end{csarray} \]

Note the important but elementary fact that the image function \(\imageModifier{\function{f}}\) preserves unions for any function \(\function{f}\):

\[ \function{\imageModifier{\function{f}}}(\setSymbol{A}\setUnionSymbol \setSymbol{B}) = \function{\imageModifier{\function{f}}}(\setSymbol{A})\setUnionSymbol \function{\imageModifier{\function{f}}}(\setSymbol{B}) \]

We show one example of this identity in action :

\[ \function{\preimageModifier{\function{f}}}(\set{\rform{\card{r}}}\setUnionSymbol \set{\bform{\card{b}}}) \] \[ \begin{csarray}{rclcccc}{acccccc} \preimageModifier{\function{f}}(\set{\rform{\card{r}}} & \cup & \set{\bform{\card{b}}}) & = & \function{\preimageModifier{\function{f}}}(\set{\rform{\card{r}},\bform{\card{b}}}) & = & \lbrace \rgform{\card{x}} , \gbform{\card{y}} \rbrace \\[0.5em] \function{\preimageModifier{\function{f}}}(\set{\rform{\card{r}}}) & \cup & \function{\preimageModifier{\function{f}}}(\set{\bform{\card{b}}}) & = & \set{\rgform{\card{x}}}\setUnionSymbol \set{\gbform{\card{y}}} & = & \lbrace \rgform{\card{x}} , \gbform{\card{y}} \rbrace \end{csarray} \]

However, the image function does not preserve intersections or relative complements. Here are counterexamples for each case:

\[ \begin{csarray}{rclcccc}{acccccc} \imageModifier{\function{f}}(\set{\rform{\card{r}}} & \cap & \set{\gform{\card{g}}}) & = & \function{\imageModifier{\function{f}}}(\set{}) & = & \lbrace \rbrace \\[0.5em] \function{\imageModifier{\function{f}}}(\set{\rform{\card{r}}}) & \cap & \function{\imageModifier{\function{f}}}(\set{\gform{\card{g}}}) & = & \set{\rgform{\card{x}}}\setIntersectionSymbol \set{\rgform{\card{x}}} & = & \lbrace \rgform{\card{x}} \rbrace \end{csarray} \] \[ \begin{csarray}{rclcccc}{acccccc} \preimageModifier{\function{f}}(\set{\rform{\card{r}}} & \setminus & \set{\gform{\card{g}}}) & = & \function{\preimageModifier{\function{f}}}(\set{\rform{\card{r}}}) & = & \lbrace \rgform{\card{x}} \rbrace \\[0.5em] \function{\preimageModifier{\function{f}}}(\set{\rform{\card{r}}}) & \setminus & \function{\preimageModifier{\function{f}}}(\set{\gform{\card{g}}}) & = & \set{\rgform{\card{x}}}\setRelativeComplementSymbol \set{\rgform{\card{x}}} & = & \lbrace \rbrace \end{csarray} \] \[ \begin{csarray}{rclcccc}{acccccc} \imageModifier{\function{f}}(\set{\rform{\card{r}}} & \cap & \set{\gform{\card{g}}}) & = & \function{\imageModifier{\function{f}}}(\set{}) & = & \lbrace \rbrace \\[0.5em] \function{\imageModifier{\function{f}}}(\set{\rform{\card{r}}}) & \cap & \function{\imageModifier{\function{f}}}(\set{\gform{\card{g}}}) & = & \set{\rgform{\card{x}}}\setIntersectionSymbol \set{\rgform{\card{x}}} & = & \lbrace \rgform{\card{x}} \rbrace \\[1em] \imageModifier{\function{f}}(\set{\rform{\card{r}}} & \setminus & \set{\gform{\card{g}}}) & = & \function{\imageModifier{\function{f}}}(\set{\rform{\card{r}}}) & = & \lbrace \rgform{\card{x}} \rbrace \\[0.5em] \function{\imageModifier{\function{f}}}(\set{\rform{\card{r}}}) & \setminus & \function{\imageModifier{\function{f}}}(\set{\gform{\card{g}}}) & = & \set{\rgform{\card{x}}}\setRelativeComplementSymbol \set{\rgform{\card{x}}} & = & \lbrace \rbrace \end{csarray} \]

In general, however, we do have that have the following inequalities for intersections and complements:

\[ \begin{csarray}{rclcrcr}{acccccc} \imageModifier{\function{f}}(\setSymbol{X} & \cap & \setSymbol{Y}) & \subseteq & \function{\imageModifier{\function{f}}}(\setSymbol{X}) & \cap & \function{\imageModifier{\function{f}}}(\setSymbol{Y})\\[1em] \imageModifier{\function{f}}(\setSymbol{X} & \setminus & \setSymbol{Y}) & \supseteq & \function{\imageModifier{\function{f}}}(\setSymbol{X}) & \setminus & \function{\imageModifier{\function{f}}}(\setSymbol{Y}) \end{csarray} \]

Let's examine the preimage function \(\preimageModifier{\function{f}}\), which again we can write as a literal mapping for our example:

\[ \preimageModifier{\function{f}} = \assocArray{\mto{\set{}}{\set{}},\mto{\set{\rgform{\card{x}}}}{\set{\rform{\card{r}},\gform{\card{g}}}},\mto{\set{\gbform{\card{y}}}}{\set{\bform{\card{b}}}},\mto{\set{\rgform{\card{x}},\gbform{\card{y}}}}{\set{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}}} \]

The preimage function is quite nice, since preserves intersections, unions, and relative complements for any function:

\[ \begin{csarray}{rclcccc}{acccccc} \preimageModifier{\function{f}}(\setSymbol{A} & \cup & \setSymbol{B}) & = & \function{\preimageModifier{\function{f}}}(\setSymbol{A}) & \cup & \function{\preimageModifier{\function{f}}}(\setSymbol{B})\\[0.5em] \preimageModifier{\function{f}}(\setSymbol{A} & \cap & \setSymbol{B}) & = & \function{\preimageModifier{\function{f}}}(\setSymbol{A}) & \cap & \function{\preimageModifier{\function{f}}}(\setSymbol{B})\\[0.5em] \preimageModifier{\function{f}}(\setSymbol{A} & \setminus & \setSymbol{B}) & = & \function{\preimageModifier{\function{f}}}(\setSymbol{A}) & \setminus & \function{\preimageModifier{\function{f}}}(\setSymbol{B}) \end{csarray} \]

Here we show some examples for these identities for our specific function, but leave the general proofs as exercises:

\[ \begin{csarray}{rclcccc}{acccccc} \preimageModifier{\function{f}}(\set{\rgform{\card{x}}} & \cup & \set{\gbform{\card{y}}}) & = & \function{\preimageModifier{\function{f}}}(\set{\rgform{\card{x}},\gbform{\card{y}}}) & = & \lbrace \rform{\card{r}} , \gform{\card{g}} , \bform{\card{b}} \rbrace \\[0.5em] \function{\preimageModifier{\function{f}}}(\set{\rgform{\card{x}}}) & \cup & \function{\preimageModifier{\function{f}}}(\set{\gbform{\card{y}}}) & = & \set{\rform{\card{r}},\gform{\card{g}}}\setUnionSymbol \set{\bform{\card{b}}} & = & \lbrace \rform{\card{r}} , \gform{\card{g}} , \bform{\card{b}} \rbrace \\[1em] \preimageModifier{\function{f}}(\set{\rgform{\card{x}}} & \cap & \set{\rgform{\card{x}},\gbform{\card{y}}}) & = & \function{\preimageModifier{\function{f}}}(\set{\rgform{\card{x}}}) & = & \lbrace \rform{\card{r}} , \gform{\card{g}} \rbrace \\[0.5em] \function{\preimageModifier{\function{f}}}(\set{\rgform{\card{x}}}) & \cap & \function{\preimageModifier{\function{f}}}(\set{\rgform{\card{x}},\gbform{\card{y}}}) & = & \set{\rform{\card{r}},\gform{\card{g}}}\setIntersectionSymbol \set{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}} & = & \lbrace \rform{\card{r}} , \gform{\card{g}} \rbrace \\[1em] \preimageModifier{\function{f}}(\set{\rgform{\card{x}},\gbform{\card{y}}} & \setminus & \set{\gbform{\card{y}}}) & = & \function{\preimageModifier{\function{f}}}(\set{\rgform{\card{x}}}) & = & \lbrace \rform{\card{r}} , \gform{\card{g}} \rbrace \\[0.5em] \function{\preimageModifier{\function{f}}}(\set{\rgform{\card{x}},\gbform{\card{y}}}) & \setminus & \function{\preimageModifier{\function{f}}}(\set{\gbform{\card{y}}}) & = & \set{\rform{\card{r}},\gform{\card{g}}}\setRelativeComplementSymbol \set{\bform{\card{b}}} & = & \lbrace \rform{\card{r}} , \gform{\card{g}} \rbrace \end{csarray} \]

We now extend the image and preimage functions to the setting of multisets.

Images and preimages of multisets

The multi-image function \(\multiImageModifier{\function{f}}\) and multi-preimage function \(\multiPreimageModifier{\function{f}}\)are functions that play the same role as the image function \(\imageModifier{\function{f}}\) and preimage function \(\preimageModifier{\function{f}}\), but operate on multisets on the domain and codomain:

\[ \begin{csarray}{ccccc}{acccc} \function{f} & : & \setSymbol{X} & \rarr & \setSymbol{Y}\\ \multiImageModifier{\function{f}} & : & \multisets{\setSymbol{X}} & \rarr & \multisets{\setSymbol{Y}}\\ \multiPreimageModifier{\function{f}} & : & \multisets{\setSymbol{Y}} & \rarr & \multisets{\setSymbol{X}} \end{csarray} \]

They are defined as follows, where \(\elemOf{\multisetSymbol{A}}{\multisets{\setSymbol{X}}}\textAnd \elemOf{\multisetSymbol{B}}{\multisets{\setSymbol{Y}}}\):

\[ \begin{aligned} \function{\multiImageModifier{\function{f}}}(\setSymbol{A})&\defEqualSymbol \multisetConstructor{\function{f}(\setElementSymbol{x})}{\elemOf{\setElementSymbol{x}}{\setSymbol{A}}}\\ \function{\multiPreimageModifier{\function{f}}}(\setSymbol{B})&\defEqualSymbol \multisetConstructor{\setElementSymbol{x}}{\tuple{\elemOf{\setElementSymbol{x}}{\setSymbol{X}},\elemOf{\function{f}(\setElementSymbol{x})}{\setSymbol{B}}}}\end{aligned} \]

The only difference from the definitions of the image and preimage functions are that we are now using multiset constructor notation, rather than set constructor notation.

Example

Let's compute the multi-image function for an example function \(\function{f}\). We'll use the same function \(\function{f}\) we examined above, which was \(\functionSignature{\function{f}}{\set{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}}{\set{\rgform{\card{x}},\gbform{\card{y}}}}\) defined by \(\function{f} = \assocArray{\mto{\rform{\card{r}}}{\rgform{\card{x}}},\mto{\gform{\card{g}}}{\rgform{\card{x}}},\mto{\bform{\card{b}}}{\gbform{\card{y}}}}\).

Then the explicit value of the multi-image function \(\multiImageModifier{\function{f}}\) is given by:

\[ \multiImageModifier{\function{f}} = \begin{csarray}{rrclrclrclrcll}{abbbcbbcbbcbba} \langle & \multiset{} & \mtoSymbol & \multiset{}, & \multiset{\rform{\card{r}}} & \mtoSymbol & \multiset{\rgform{\card{x}}}, & \multiset{\gform{\card{g}}} & \mtoSymbol & \multiset{\rgform{\card{x}}}, & \multiset{\bform{\card{b}}} & \mtoSymbol & \multiset{\gbform{\card{y}}}, & \\ & \multiset{\rform{\card{r}},\gform{\card{g}}} & \mtoSymbol & \multiset{\rgform{\card{x}},\rgform{\card{x}}}, & \multiset{\rform{\card{r}},\bform{\card{b}}} & \mtoSymbol & \multiset{\rgform{\card{x}},\gbform{\card{y}}}, & \multiset{\gform{\card{g}},\bform{\card{b}}} & \mtoSymbol & \multiset{\rgform{\card{x}},\gbform{\card{y}}}, & \multiset{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}} & \mtoSymbol & \multiset{\rgform{\card{x}},\rgform{\card{x}},\gbform{\card{y}}} & \rangle \end{csarray} \]

Note the only difference here between \(\multiImageModifier{\function{f}}\textAnd \imageModifier{\function{f}}\) is the behavior on \(\multiset{\rform{\card{r}},\gform{\card{g}}}\) / \(\set{\rform{\card{r}},\gform{\card{g}}}\).

The multi pre-image function \(\multiPreimageModifier{\function{f}}\) has explicit value:

\[ \multiPreimageModifier{\function{f}} = \assocArray{\mto{\multiset{}}{\multiset{}},\mto{\multiset{\rgform{\card{x}}}}{\multiset{\rform{\card{r}},\gform{\card{g}}}},\mto{\multiset{\gbform{\card{y}}}}{\multiset{\bform{\card{b}}}},\mto{\multiset{\rgform{\card{x}},\gbform{\card{y}}}}{\multiset{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}}} \]

Note there is no difference between \(\multiPreimageModifier{\function{f}}\textAnd \preimageModifier{\function{f}}\) if we replace multisets with the corresponding sets:

\[ \preimageModifier{\function{f}} = \assocArray{\mto{\set{}}{\set{}},\mto{\set{\rgform{\card{x}}}}{\set{\rform{\card{r}},\gform{\card{g}}}},\mto{\set{\gbform{\card{y}}}}{\set{\bform{\card{b}}}},\mto{\set{\rgform{\card{x}},\gbform{\card{y}}}}{\set{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}}} \]

What is the reason for this? First, observe that pre-images of different singleton sets are always disjoint, because \(\function{f}\) is a single-valued function: any element \(\setElementSymbol{z}\) that was in the intersection \(\function{\preimageModifier{\function{f}}}(\set{\setElementSymbol{x}})\setIntersectionSymbol \function{\preimageModifier{\function{f}}}(\set{\setElementSymbol{y}})\) would imply that both \(\function{f}(\setElementSymbol{z}) = \setElementSymbol{x}\textAnd \function{f}(\setElementSymbol{z}) = \setElementSymbol{y}\). Therefore, the multiplicities of objects in \(\function{\multiPreimageModifier{\function{f}}}(\setSymbol{X})\) cannot exceed 1, and so the multiset \(\function{\multiPreimageModifier{\function{f}}}(\setSymbol{X})\) projects to the set \(\function{\multiPreimageModifier{\function{f}}}(\setSymbol{X})\):

\[ \projection(\function{\multiPreimageModifier{\function{f}}}(\setSymbol{X})) = \function{\preimageModifier{\function{f}}}(\setSymbol{X}) \]

Multiplicity functions of multi-images

Let us examine the behavior of \(\multiImageModifier{\function{f}}\) from the point of view of the multiplicity function of the output multiset \(\function{\multiImageModifier{\function{f}}}(\setSymbol{A})\) for a particular input multiset \(\elemOf{\multisetSymbol{A}}{\multisets{\setSymbol{X}}}\). In other words, we wish to understand the function \(\functionSignature{\function{\boundMultiplicityFunction{\function{\multiImageModifier{\function{f}}}(\multisetSymbol{A})}}}{\multisets{\setSymbol{Y}}}{\mathbb{N}}\):

Simply put, \(\boundMultiplicityFunction{\function{\multiImageModifier{\function{f}}}(\multisetSymbol{A})}\) will count how many times any \(\elemOf{\multisetElementSymbol{y}}{\setSymbol{Y}}\) occurs in the multi-image \(\function{\multiImageModifier{\function{f}}}(\multisetSymbol{A})\). This is easy to define as a cardinality:

\[ \function{\boundMultiplicityFunction{\function{\multiImageModifier{\function{f}}}(\multisetSymbol{A})}}(\multisetElementSymbol{y}) = \function{\multiImageModifier{\function{f}}}(\multisetSymbol{A})\multisetMultiplicitySymbol \setElementSymbol{y} = \cardinalityConstructor{\function{f}(\setElementSymbol{x}) = \setElementSymbol{y}}{\elemOf{\setElementSymbol{x}}{\multisetSymbol{A}}} \]

It is clear that the number of ways that \(\function{f}(\setElementSymbol{x}) = \setElementSymbol{y}\) can be true in the multiset sum \(\multisetSymbol{A}\multisetSumSymbol \primed{\multisetSymbol{A}}\) is the sum of the number of ways it can be true in \(\multisetSymbol{A}\) and the number of ways it can be true in \(\primed{\multisetSymbol{A}}\):

\[ \boundMultiplicityFunction{\function{\multiImageModifier{\function{f}}}(\multisetSymbol{A}\multisetSumSymbol \primed{\multisetSymbol{A}})} = \boundMultiplicityFunction{\function{\multiImageModifier{\function{f}}}(\multisetSymbol{A})} + \boundMultiplicityFunction{\function{\multiImageModifier{\function{f}}}(\primed{\multisetSymbol{A}})} \]

Therefore we have that multi-image functions preserve multiset sums, or – speaking more geometrically – are "linear":

\[ \function{\multiImageModifier{\function{f}}}(\multisetSymbol{A}\multisetSumSymbol \primed{\multisetSymbol{A}}) = \function{\multiImageModifier{\function{f}}}(\multisetSymbol{A}) + \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\primed{A}}) \]

The same is not true for multiset intersection, and relative complement, for the same reason that ordinary image functions do not preserve set intersection and relative complement.

Multiset products

In this section we'll establish how to multiply two multisets together. Doing this will require us to choose a function with appropriate properties to combine elements from each multiset together, to yield a resulting multiset.

Images of multiple arguments

In the previous section we defined how we can "lift" the an function \(\functionSignature{\function{f}}{\setSymbol{X}}{\setSymbol{Y}}\) between sets \(\setSymbol{X},\setSymbol{Y}\), to the multi-image \(\functionSignature{\function{\multiImageModifier{\function{f}}}}{\multisets{\setSymbol{X}}}{\multisets{\setSymbol{Y}}}\) between multisets on \(\setSymbol{X},\setSymbol{Y}\):

\[ \begin{aligned} \function{\multiImageModifier{\function{f}}}(\setSymbol{A})&\defEqualSymbol \multisetConstructor{\function{f}(\setElementSymbol{x})}{\elemOf{\setElementSymbol{x}}{\setSymbol{A}}}\end{aligned} \]

We can easily extend this idea to a function of \(\sym{n}\) arguments \(\functionSignature{\function{g}}{\tuple{\setSymbol{X}_1,\setSymbol{X}_2,\ellipsis ,\setSymbol{X}_{\sym{n}}}}{\setSymbol{Y}}\), lifting it into a function \(\functionSignature{\function{\multiImageModifier{\function{g}}}}{\tuple{\multisets{\setSymbol{X}_1},\multisets{\setSymbol{X}_2},\ellipsis ,\multisets{\setSymbol{X}_{\sym{n}}}}}{\multisets{\setSymbol{Y}}}\):

\[ \begin{aligned} \function{\multiImageModifier{\function{g}}}(\setSymbol{A}_1,\setSymbol{A}_2,\ellipsis ,\setSymbol{A}_{\sym{n}})&\defEqualSymbol \multisetConstructor{\function{f}(\setElementSymbol{x}_1,\setElementSymbol{x}_2,\ellipsis ,\setElementSymbol{x}_{\sym{n}})}{\elemOf{\setElementSymbol{x}_1}{\setSymbol{A}_1},\elemOf{\setElementSymbol{x}_2}{\setSymbol{A}_2},\ellipsis ,\elemOf{\setElementSymbol{x}_{\sym{n}}}{\setSymbol{A}_{\sym{n}}}}\end{aligned} \]

For similar reasons to the single-argument case, \(\multiImageModifier{\function{g}}\) preserves multiset sums in any of its arguments individually – it is "multilinear".

Semigroups

We now focus our attention on binary functions that define the product of semigroups, as these will form useful ingredients in cooking up multiset products.

A semigroup on a set \(\setSymbol{X}\) is a pair \(\tuple{\setSymbol{X},\sgdot }\), where \(\functionSignature{\function{\sgdot }}{\tuple{\setSymbol{X},\setSymbol{X}}}{\setSymbol{X}}\) is an associative binary operation:

\[ \paren{\setElementSymbol{x}\sgdot \setElementSymbol{y}}\sgdot \setElementSymbol{z} = \setElementSymbol{x}\sgdot \paren{\setElementSymbol{y}\sgdot \setElementSymbol{z}} \]

Lifting semigroup products

Let us now consider how to lift the semigroup product \(\sgdot\), defined on \(\setSymbol{X}\), to operate on multisets on \(\setSymbol{X}\). We should technically write this multi-image function as \(\multiImageModifier{\sgdot }\), but we will use the symbol \(\multiImageColorModifier{\srdot }\) instead, as we did for multiset versions of union, etc.

To recall, the multi-image function that lifts \(\sgdot\) is the function \(\functionSignature{\function{\multiImageColorModifier{\srdot }}}{\tuple{\multisets{\setSymbol{X}},\multisets{\setSymbol{X}}}}{\multisets{\setSymbol{X}}}\) defined as:

\[ \appliedRelation{\multisetSymbol{A} \multiImageColorModifier{\srdot } \multisetSymbol{B}}\defEqualSymbol \multisetConstructor{\multisetElementSymbol{a}\sgdot \multisetElementSymbol{b}}{\elemOf{\multisetElementSymbol{a}}{\multisetSymbol{A}},\elemOf{\multisetElementSymbol{b}}{\multisetSymbol{B}}} \]

This function endows \(\multisets{\setSymbol{X}}\) with an interesting structure: that of a semiring. First, let's explain what a semiring is!

Semirings

A semiring is a tuple \(\tuple{\setSymbol{M},\srplus ,\srdot }\), where \(\functionSignature{\function{\srdot }}{\tuple{\setSymbol{X},\setSymbol{X}}}{\setSymbol{X}}\) is an associative binary operation and \(\functionSignature{\function{\srplus }}{\tuple{\setSymbol{X},\setSymbol{X}}}{\setSymbol{X}}\) is a commutative, associative binary operation with identity that distributes over \(\srdot\):

\[ \begin{aligned} \setElementSymbol{x}\srdot \paren{\setElementSymbol{y}\srplus \setElementSymbol{z}}&= \paren{\setElementSymbol{x}\srdot \setElementSymbol{y}}\srplus \paren{\setElementSymbol{x}\srdot \setElementSymbol{z}}\\ \paren{\setElementSymbol{x}\srplus \setElementSymbol{y}}\srdot \setElementSymbol{z}&= \paren{\setElementSymbol{x}\srdot \setElementSymbol{z}}\srplus \paren{\setElementSymbol{y}\srdot \setElementSymbol{z}}\end{aligned} \]

Additionally they must have an additive identity (the zero element), and usually also have one or more multiplicative identities.

Probably the simplest example of a semiring is given by the natural numbers under their ordinary sum and product: \(\tuple{\mathbb{N}, + ,\times }\).

Semirings are an "API" for the most general kinds of number-like objects, requiring only that they can be added and multiplied in a sensible way.

Semigroups to semirings

We now show how an arbitrary semigroup yields a semiring via multi-images:

We define the multiset semiring induced by a semigroup \(\tuple{\setSymbol{X},\sgdot }\), to be the semiring \(\tuple{\multisets{\setSymbol{X}},\multisetSumSymbol ,\srdot = \multiImageModifier{\sgdot }}\), which we can denote \(\multisetSemiring{\setSymbol{X}}{\sgdot }\):

  • the semiring elements are the multisets on \(\setSymbol{X}\)

  • the semiring addition \(\srplus\) is given by multiset sum \(\multisetSumSymbol\)

  • the semiring product \(\srdot\) is given by the multi-image function \(\multiImageModifier{\sgdot }\) that lifts the semigroup product \(\sgdot\)

Let's verify this is actually a semiring.

The additive identity is obvious: it is the empty multiset, since \(\multisetSymbol{A}\multisetSumSymbol \multiset{} = \multisetSymbol{A}\).

Associativity of the semiring product \(\srdot\) follows from associativity of \(\sgdot\) straightforwardly.

Distributivity of \(\srdot\) over \(\srplus\) follows from the fact that any \(n\)-ary multi-image function is multilinear: it preserves multiset sums in each of its arguments. We'll spelling this out for left-distributivity, right-distributivity is proved in a similar way:

\[ \begin{aligned} \multisetSymbol{A}\srdot \paren{\multisetSymbol{B}\srplus \multisetSymbol{C}}&= \function{\multiImageModifier{\sgdot }}(\multisetSymbol{A},\multisetSymbol{B}\multisetSumSymbol \multisetSymbol{C})\\ &= \function{\multiImageModifier{\sgdot }}(\multisetSymbol{A},\multisetSymbol{B})\multisetSumSymbol \function{\multiImageModifier{\sgdot }}(\multisetSymbol{A},\multisetSymbol{C})\\ &= \paren{\multisetSymbol{A}\srdot \multisetSymbol{B}}\srplus \paren{\multisetSymbol{A}\srdot \multisetSymbol{C}}\end{aligned} \]

Example 1: "tally" multisets

Let's flex our muscles a bit to see how these multiset semirings might model familiar parts of mathematics.

Let's consider the multisets on a singleton set \(\bform{\setSymbol{X_0}} = \set{\bform{\sym{x}}}\). We'll name this set \(\rform{\setSymbol{X_1}}\):

\[ \rform{\setSymbol{X_1}} = \multisets{\bform{\setSymbol{X_0}}} = \set{\styledMultiset{\rform}{},\styledMultiset{\rform}{\bform{\sym{x}}},\styledMultiset{\rform}{\bform{\sym{x}},\bform{\sym{x}}},\styledMultiset{\rform}{\bform{\sym{x}},\bform{\sym{x}},\bform{\sym{x}}},\styledMultiset{\rform}{\bform{\sym{x}},\bform{\sym{x}},\bform{\sym{x}},\bform{\sym{x}}},\ellipsis } \]

We saw earlier that the multisets on a singleton are in bijection with the natural numbers, where we are essentially "tallying by finger counting":

\[ \begin{aligned} \rform{\setSymbol{X_1}}& \approx \mathbb{Z}\\ \underRepeated{\styledMultiset{\rform}{\bform{\sym{x}},\bform{\sym{x}},\ellipsis ,\bform{\sym{x}}}}{\sym{n}}& \approx \sym{n}\end{aligned} \]

From now on, we'll express these multisets in a more compact form using integer multiples:

\[ \repeatedMultiset{\sym{n}}{\styledMultiset{\rform}{\bform{\sym{x}}}}\syntaxEqualSymbol \underRepeated{\styledMultiset{\rform}{\bform{\sym{x}},\bform{\sym{x}},\ellipsis ,\bform{\sym{x}}}}{\sym{n}} \]

Using this notation, we have:

\[ \begin{aligned} \repeatedMultiset{0}{\styledMultiset{\rform}{\bform{\sym{x}}}}&\syntaxEqualSymbol \styledMultiset{\rform}{}\\ \repeatedMultiset{1}{\styledMultiset{\rform}{\bform{\sym{x}}}}&\syntaxEqualSymbol \styledMultiset{\rform}{\bform{\sym{x}}}\\ \repeatedMultiset{2}{\styledMultiset{\rform}{\bform{\sym{x}}}}&\syntaxEqualSymbol \styledMultiset{\rform}{\bform{\sym{x}},\bform{\sym{x}}}\\ \repeatedMultiset{3}{\styledMultiset{\rform}{\bform{\sym{x}}}}&\syntaxEqualSymbol \styledMultiset{\rform}{\bform{\sym{x}},\bform{\sym{x}},\bform{\sym{x}}}\end{aligned} \]

To define the semiring structure on \(\rform{\setSymbol{X_1}} = \multisets{\bform{\setSymbol{X_0}}}\), we must choose a semigroup product \(\functionSignature{\function{\sgdot }}{\tuple{\bform{\setSymbol{X_0}},\bform{\setSymbol{X_0}}}}{\bform{\setSymbol{X_0}}}\) on \(\bform{\setSymbol{X_0}} = \set{\bform{\sym{x}}}\). But there is only one possible such structure, given by \(\bform{\identity} = \assocArray{\mto{\tuple{\bform{\sym{x}},\bform{\sym{x}}}}{\bform{\sym{x}}}}\). Therefore our semiring product on \(\rform{\setSymbol{X_1}}\) is \(\rform{\msrdot } = \multiImageModifier{\bform{\identity}}\), yielding the the semiring structure we'll call \(\rform{\multisetSemiringSymbol{M_1}}\):

\[ \rform{\multisetSemiringSymbol{M_1}} = \tuple{\rform{\setSymbol{X_1}},\rform{\msrplus },\rform{\msrdot }} = \tuple{\multisets{\bform{\setSymbol{X_0}}},\rform{\msrplus },\multiImageModifier{\bform{\identity}}} \]

\(\rform{\multisetSemiringSymbol{M_1}}\) has the following properties:

  • the sum of two multisets corresponds to the sum of two natural numbers: \(\repeatedMultiset{\sym{m}}{\styledMultiset{\rform}{\bform{\sym{x}}}}\,\rform{\msrplus }\,\repeatedMultiset{\sym{n}}{\styledMultiset{\rform}{\bform{\sym{x}}}} = \repeatedMultiset{\paren{\sym{m} + \sym{n}}}{\styledMultiset{\rform}{\bform{\sym{x}}}}\)

  • product of two multisets corresponds to the product of two natural numbers: \(\repeatedMultiset{\sym{m}}{\styledMultiset{\rform}{\bform{\sym{x}}}}\,\rform{\msrdot }\,\repeatedMultiset{\sym{n}}{\styledMultiset{\rform}{\bform{\sym{x}}}} = \repeatedMultiset{\paren{\sym{m} \, \sym{n}}}{\styledMultiset{\rform}{\bform{\sym{x}}}}\)

Hence, \(\rform{\multisetSemiringSymbol{M_1}}\) is isomorphic to the semiring of the natural numbers:

\[ \rform{\multisetSemiringSymbol{M_1}}\isomorphicSymbol \semiring{\mathbb{N}} \]

We have some additional properties of \(\rform{\multisetSemiringSymbol{M_1}}\) that exploit the other multiset operations:

\[ \begin{aligned} \repeatedMultiset{\sym{m}}{\styledMultiset{\rform}{\bform{\sym{x}}}}\multisetUnionSymbol \repeatedMultiset{\sym{n}}{\styledMultiset{\rform}{\bform{\sym{x}}}}&= \max(\sym{m},\sym{n})\\ \repeatedMultiset{\sym{m}}{\styledMultiset{\rform}{\bform{\sym{x}}}}\multisetIntersectionSymbol \repeatedMultiset{\sym{n}}{\styledMultiset{\rform}{\bform{\sym{x}}}}&= \min(\sym{m},\sym{n})\\ \repeatedMultiset{\sym{m}}{\styledMultiset{\rform}{\bform{\sym{x}}}}\multisetRelativeComplementSymbol \repeatedMultiset{\sym{n}}{\styledMultiset{\rform}{\bform{\sym{x}}}}&= \sym{m} - \sym{n}\end{aligned} \]

Example 2: univariate polynomials

We'll now form the multisets on \(\rform{\setSymbol{X_1}}\), and call this \(\gform{\setSymbol{X_2}}\):

\[ \gform{\setSymbol{X_2}} = \multisets{\rform{\setSymbol{X_1}}} = \multisets{\multisets{\bform{\setSymbol{X_0}}}} = \multisets{\set{\styledMultiset{\rform}{},\styledMultiset{\rform}{\bform{\sym{x}}},\styledMultiset{\rform}{\bform{\sym{x}},\bform{\sym{x}}},\ellipsis }} \]

Before trying to interpret \(\gform{\setSymbol{X_2}}\), we'll choose to abbreviate the elements of \(\rform{\setSymbol{X_1}}\) in a more suggestive way:

\[ \power{\rform{\sym{x}}}{\sym{n}}\syntaxEqualSymbol \underRepeated{\styledMultiset{\rform}{\bform{\sym{x}},\bform{\sym{x}},\ellipsis ,\bform{\sym{x}}}}{\sym{n}} \]

As a special case, we'll use \(\rform{1}\) to denote the empty multiset \(\elemOf{\styledMultiset{\rform}{}}{\rform{\setSymbol{X_1}}}\).

We can now list some of the infinitely many elements of \(\gform{\setSymbol{X_2}}\):

\[ \gform{\setSymbol{X_2}} = \begin{nsarray}{rlllll} \lbrace & \phantom{,}\styledMultiset{\gform}{}, & & & & \\ \phantom{\lbrace } & \phantom{,}\styledMultiset{\gform}{\rform{1}}, & \phantom{,}\styledMultiset{\gform}{\rform{1},\rform{1}}, & \phantom{,}\styledMultiset{\gform}{\rform{1},\rform{1},\rform{1}}, & \phantom{,}\ellipsis , & \\ \phantom{\lbrace } & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{1}}, & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{1}}, & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{1}}, & \phantom{,}\ellipsis , & \\ \phantom{\lbrace } & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{1},\rform{1}}, & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{1},\rform{1},\rform{1}}, & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{1},\rform{1},\rform{1}}, & \phantom{,}\ellipsis , & \\ \phantom{\lbrace } & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{2}}, & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{2}}, & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{2}}, & \phantom{,}\ellipsis , & \\ \phantom{\lbrace } & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{1}}, & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{1}}, & \phantom{,}\ellipsis , & & \\ \phantom{\lbrace } & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{1}}, & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{1}}, & \phantom{,}\ellipsis , & & \\ \phantom{\lbrace } & \phantom{,}\styledMultiset{\gform}{\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{1},\rform{1}}, & \phantom{,}\ellipsis , & & & \rbrace \end{nsarray} \]

We can further also use integer multiple notation to write these elements of \(\gform{\setSymbol{X_2}}\) in a more compact way:

\[ \styledMultiset{\gform}{\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{1},\rform{1},\rform{1},\rform{1}}\syntaxEqualSymbol \styledMultiset{\gform}{\power{\rform{\sym{x}}}{2}}\,\gform{\msrplus }\,\repeatedMultiset{2}{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{1}}}\,\gform{\msrplus }\,\repeatedMultiset{3}{\styledMultiset{\gform}{\rform{1}}} \]

On the other hand, we can avoid using any notation at all, and write an element of \(\gform{\setSymbol{X_2}}\) directly as a multiset of multisets on \(\bform{\setSymbol{X_0}} = \set{\bform{\sym{x}}}\):

\[ \styledMultiset{\gform}{\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{1},\rform{1},\rform{1},\rform{1}}\syntaxEqualSymbol \begin{nsarray}{l} \gform{\openMultiset }\kern{2pt}\styledMultiset{\rform}{\bform{\sym{x}},\bform{\sym{x}}},\\ \phantom{\openMultiset \kern{2pt}}\styledMultiset{\rform}{\bform{\sym{x}}},\styledMultiset{\rform}{\bform{\sym{x}}},\\ \phantom{\openMultiset \kern{2pt}}\styledMultiset{\rform}{},\styledMultiset{\rform}{},\styledMultiset{\rform}{}\kern{2pt}\gform{\closeMultiset } \end{nsarray} \]

General form

A general element \(\elemOf{\multisetSymbol{M}}{\gform{\setSymbol{X_2}}}\) can be written as a sum of elements of \(\rform{\setSymbol{X_1}}\), with corresponding multiplicities \(\sym{m}_{\sym{i}}\). Recall that only finitely many of these can be non-zero.

\[ \multisetSymbol{M} = \styledIndexSum{\gform}{\repeatedMultiset{\sym{m}_{\sym{i}}}{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{\sym{i}}}}}{\sym{i} \ge 0}{} \]

The summation symbol \(\gform\indexSumSymbol{}\) is colored to indicate that is represents the composition of binary multiset sums \(\gform{\msrplus }\).

Polynomials

It should be transparent now that there is a bijection between \(\gform{\setSymbol{X_2}}\) and the polynomials in variable \(\bform{\sym{x}}\) with non-negative integer coefficients:

\[ \gform{\setSymbol{X_2}}\bijectiveSymbol \polynomialRing{\semiring{\mathbb{N}}}{\bform{\sym{x}}} \]

Semiring product

Next, we seek a product \(\gform{\msrdot }\) so that \(\tuple{\gform{\setSymbol{X_2}},\gform{\msrplus },\gform{\msrdot }}\) forms a semiring.

But we have an obvious candidate: the lift \(\multiImageModifier{\rform{\msrdot }}\) of the product \(\rform{\msrdot }\) of \(\rform{\multisetSemiringSymbol{M_1}}\), since the semiring \(\tuple{\rform{\setSymbol{X_1}},\rform{\msrplus },\rform{\msrdot }}\) defines a semigroup \(\tuple{\rform{\setSymbol{X_1}},\rform{\msrdot }}\).

Setting \(\gform{\msrdot } = \multiImageModifier{\rform{\msrdot }}\), we can define the semiring \(\gform{\multisetSemiringSymbol{M_2}} = \tuple{\gform{\setSymbol{X_2}},\gform{\msrplus },\gform{\msrdot }}\).

As an example, let's see how the product \(\gform{\msrdot }\) acts on two elements of \(\gform{\setSymbol{X_2}}\):

\[ \begin{aligned} \paren{\repeatedMultiset{3}{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{2}}}\,\gform{\msrplus }\,\multiset{\rform{1}}}\,\gform{\msrdot }\,\paren{\repeatedMultiset{2}{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{1}}}}&= \styledMultiset{\gform}{\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{2},\power{\rform{\sym{x}}}{0}}\,\gform{\msrdot }\,\styledMultiset{\gform}{\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{1}}\\ &= \styledMultiset{\gform}{\power{\rform{\sym{x}}}{2}\,\rform{\msrdot }\,\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{2}\,\rform{\msrdot }\,\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{2}\,\rform{\msrdot }\,\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{0}\,\rform{\msrdot }\,\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{2}\,\rform{\msrdot }\,\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{2}\,\rform{\msrdot }\,\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{2}\,\rform{\msrdot }\,\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{0}\,\rform{\msrdot }\,\power{\rform{\sym{x}}}{1}}\\ &= \styledMultiset{\gform}{\power{\rform{\sym{x}}}{3},\power{\rform{\sym{x}}}{3},\power{\rform{\sym{x}}}{3},\power{\rform{\sym{x}}}{1},\power{\rform{\sym{x}}}{3},\power{\rform{\sym{x}}}{3},\power{\rform{\sym{x}}}{3},\power{\rform{\sym{x}}}{1}}\\ &= \repeatedMultiset{6}{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{3}}}\,\gform{\msrplus }\,\repeatedMultiset{2}{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{1}}}\end{aligned} \]

This corresponds to the product of polynomials:

\[ \paren{\poly{3 \, \power{\bform{\sym{x}}}{2} + 1}} \, \paren{\poly{2 \, \bform{\sym{x}}}} = \poly{6 \, \power{\bform{\sym{x}}}{3} + 2 \, \bform{\sym{x}}} \]

Product computation

We can compute the product of two general elements of \(\elemOf{\multisetSymbol{A},\multisetSymbol{B}}{\gform{\multisetSemiringSymbol{M_2}}}\) by first expressing them as finite sums of elements of elements of \(\rform{\multisetSemiringSymbol{M_1}}\):

\[ \multisetSymbol{A} = \styledIndexSum{\gform}{\repeatedMultiset{\sym{a}_{\sym{i}}}{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{\sym{i}}}}}{\sym{i} \ge 0}{}\quad \multisetSymbol{B} = \styledIndexSum{\gform}{\repeatedMultiset{\sym{b}_{\sym{i}}}{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{\sym{i}}}}}{\sym{i} \ge 0}{} \]

Then the product is given by:

\[ \begin{aligned} \multisetSymbol{A}\,\gform{\msrdot }\,\multisetSymbol{B}&= \paren{\styledIndexSum{\gform}{\repeatedMultiset{\sym{a}_{\sym{i}}}{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{\sym{i}}}}}{\sym{i}}{}}\,\gform{\msrdot }\,\paren{\styledIndexSum{\gform}{\repeatedMultiset{\sym{b}_{\sym{j}}}{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{\sym{j}}}}}{\sym{j}}{}}\\ &= \styledIndexSum{\gform}{\paren{\repeatedMultiset{\sym{a}_{\sym{i}}}{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{\sym{i}}}}}\,\gform{\msrdot }\,\paren{\repeatedMultiset{\sym{b}_{\sym{j}}}{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{\sym{j}}}}}}{\substack{\sym{i},\;\sym{j}}}{}\\ &= \styledIndexSum{\gform}{\underRepeated{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{\sym{i}},\ellipsis ,\power{\rform{\sym{x}}}{\sym{i}}}}{\sym{a}_{\sym{i}}}\,\gform{\msrdot }\,\underRepeated{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{\sym{j}},\ellipsis ,\power{\rform{\sym{x}}}{\sym{j}}}}{\sym{b}_{\sym{j}}}}{\substack{\sym{i},\;\sym{j}}}{}\\ &= \styledIndexSum{\gform}{\underRepeated{\styledMultiset{\gform}{\power{\rform{\sym{x}}}{\sym{i}}\,\rform{\msrdot }\,\power{\rform{\sym{x}}}{\sym{j}},\ellipsis ,\power{\rform{\sym{x}}}{\sym{i}}\,\rform{\msrdot }\,\power{\rform{\sym{x}}}{\sym{j}}}}{\sym{a}_{\sym{i}} \, \sym{b}_{\sym{j}}}}{\substack{\sym{i},\;\sym{j}}}{}\\ &= \styledIndexSum{\gform}{\repeatedMultiset{\sym{a}_{\sym{i}} \, \sym{b}_{\sym{j}}}{\power{\rform{\sym{x}}}{\sym{i}}\,\rform{\msrdot }\,\power{\rform{\sym{x}}}{\sym{j}}}}{\substack{\sym{i},\;\sym{j}}}{}\\ &= \styledIndexSum{\gform}{\repeatedMultiset{\sym{a}_{\sym{i}} \, \sym{b}_{\sym{j}}}{\power{\rform{\sym{x}}}{\sym{i} + \sym{j}}}}{\substack{\sym{i},\;\sym{j}}}{}\end{aligned} \]

Solving for the multiplicity in \(\multisetSymbol{A}\,\gform{\msrdot }\,\multisetSymbol{B}\) of a generic element \(\elemOf{\power{\rform{\sym{x}}}{\sym{i}}}{\rform{\setSymbol{X_1}}}\), we can remove one of the indices of the double summation:

\[ \begin{aligned} \paren{\multisetSymbol{A}\,\gform{\msrdot }\,\multisetSymbol{B}}\multisetMultiplicitySymbol \power{\rform{\sym{x}}}{\sym{n}}&= \indexSum{\paren{\multisetSymbol{A}\multisetMultiplicitySymbol \power{\rform{\sym{x}}}{\sym{i}}} \, \paren{\multisetSymbol{B}\multisetMultiplicitySymbol \power{\rform{\sym{x}}}{\sym{j}}}}{\sym{i} + \sym{j} = \sym{n}}{}\\ &= \indexSum{\paren{\multisetSymbol{A}\multisetMultiplicitySymbol \power{\rform{\sym{x}}}{\sym{i}}} \, \paren{\multisetSymbol{B}\multisetMultiplicitySymbol \power{\rform{\sym{x}}}{\sym{n} - \sym{i}}}}{\sym{i} \le \sym{n}}{}\end{aligned} \]

These computations may seem obvious when we have the polynomial interpretation of these multisets in mind, and in a sense it is pedantic to spell them out. But it is perhaps surprising that we were naturally led to this semiring structure as soon as we chose the base set \(\bform{\setSymbol{X_0}} = \set{\bform{\sym{x}}}\).

In summary, we have the semiring isomorphism between the positive-integral univariate polynomials \(\polynomialRing{\semiring{\mathbb{N}}}{\bform{\sym{x}}}\) and the multiset semiring on the multiset semiring on \(\set{\bform{\sym{x}}}\) (phew!):

\[ \gform{\multisetSemiringSymbol{M_2}}\isomorphicSymbol \polynomialRing{\semiring{\mathbb{N}}}{\bform{\sym{x}}} \]

Summary of examples

Our last two examples have covered one semigroup and two multiset semirings involved, let's summarize the situation in a table:

elementssemiringsemigroupproductmodels
\(\bform{\setSymbol{X_0}} = \set{\bform{\sym{x}}}\)\(\notApplicable\)\(\tuple{\bform{\setSymbol{X_0}},\bform{\identity}}\)\(\bform{\identity} = \mto{\tuple{\bform{\sym{x}},\bform{\sym{x}}}}{\bform{\sym{x}}}\)'identity'
\(\rform{\setSymbol{X_1}} = \multisets{\bform{\setSymbol{X_0}}}\)\(\rform{\multisetSemiringSymbol{M_1}} = \tuple{\rform{\setSymbol{X_1}},\rform{\msrplus },\rform{\msrdot }}\)\(\tuple{\rform{\setSymbol{X_1}},\rform{\msrdot }}\)\(\rform{\msrdot } = \multiImageModifier{\bform{\identity}}\)natural numbers
\(\gform{\setSymbol{X_2}} = \multisets{\rform{\setSymbol{X_1}}}\)\(\gform{\multisetSemiringSymbol{M_2}} = \tuple{\gform{\setSymbol{X_2}},\gform{\msrplus },\gform{\msrdot }}\)\(\tuple{\gform{\setSymbol{X_2}},\gform{\msrdot }}\)\(\gform{\msrdot } = \multiImageModifier{\rform{\msrdot }}\)polynomials in \(\bform{\sym{x}}\)

The univariate polynomials modelled by \(\gform{\multisetSemiringSymbol{M_2}}\) are specifically those that have natural-number coefficients. We will shortly see how to obtain the full ring of polynomials with integer-valued coefficients using signed multisets.

Next, we will extend our notion of multisets slightly, which will allow us to beef up these constructions of the semirings \(\semiring{\mathbb{N}}\) and \(\polynomialRing{\semiring{\mathbb{N}}}{\bform{\sym{x}}}\) to constructions of the rings \(\ring{\mathbb{Z}}\) and \(\polynomialRing{\ring{\mathbb{Z}}}{\bform{\sym{x}}}\).

Signed multisets

We can extend the idea of a multiset in a very simple way to yield a signed multiset.

We can think of a normal, unsigned multiset \(\elemOf{\multisetSymbol{A}}{\multisets{\setSymbol{X}}}\) on a base set \(\setSymbol{X}\) as an unordered list of elements from \(\setSymbol{X}\). To form a signed multiset, we allow some of these elements to be present in negated form in the multiset. This is similar to the way we conceptualize of negative integers are the negated forms of positive integers.

To indicate the presence of a negated form of an element \(\elemOf{\setElementSymbol{x}}{\setSymbol{X}}\), we write it with an overbar: \(\negated{\signedMultisetElementSymbol{x}}\). For example, the following signed multiset consists of three non-negated copies of \(\signedMultisetElementSymbol{x}\), and two negated copies of \(\signedMultisetElementSymbol{y}\):

\[ \signedMultiset{\signedMultisetElementSymbol{x},\signedMultisetElementSymbol{x},\signedMultisetElementSymbol{x},\negated{\signedMultisetElementSymbol{y}},\negated{\signedMultisetElementSymbol{y}}} \]

If a single object is present in both negated and non-negated forms, these "cancel" each other in pairs:

\[ \signedMultiset{\signedMultisetElementSymbol{x},\signedMultisetElementSymbol{x},\signedMultisetElementSymbol{x},\negated{\signedMultisetElementSymbol{x}},\negated{\signedMultisetElementSymbol{x}}} = \signedMultiset{\signedMultisetElementSymbol{x},\signedMultisetElementSymbol{x},\negated{\signedMultisetElementSymbol{x}}} = \signedMultiset{\signedMultisetElementSymbol{x}} \]

A signed multiset is in normal form if it is written so that no cancellable pairs are present.

Essentially, the "net" number of ordinary or negated copies of an object gives the multiplicity of that object, which can now be a negative integer if there are negated copies present.

We write the set of signed multisets on a base set \(\setSymbol{X}\) as \(\signedMultisets{\setSymbol{X}}\).

Signed multiplicities

For a multiset \(\elemOf{\multisetSymbol{A}}{\multisets{\setSymbol{X}}}\), the multiplicity function \(\functionSignature{\function{\boundMultiplicityFunction{\multisetSymbol{A}}}}{\setSymbol{X}}{\mathbb{N}}\) associates to each element \(\elemOf{\setElementSymbol{x}}{\setSymbol{X}}\) a natural number \(\multisetSymbol{X}\multisetMultiplicitySymbol \setElementSymbol{x}\).

For a signed multiset \(\elemOf{\multisetSymbol{B}}{\signedMultisets{\setSymbol{X}}}\), the multiplicity function \(\functionSignature{\function{\boundMultiplicityFunction{\multisetSymbol{B}}}}{\setSymbol{X}}{\mathbb{Z}}\) associates to each element of \(\setSymbol{X}\) an integer. Negative integers indicate negative multiplicities.

All other operations on signed multisets are defined in an identical way relative to their multiset relatives, with one exception – the relative complement no longer requires a \(\max(□,0)\) in its definition, since negative multiplicities are permitted:

\[ \begin{aligned} \boundSignedMultiplicityFunction{\paren{\multisetSymbol{M}\multisetSumSymbol \multisetSymbol{N}}}&= \boundMultiplicityFunction{\multisetSymbol{M}} + \boundMultiplicityFunction{\multisetSymbol{N}}\\ \boundSignedMultiplicityFunction{\paren{\multisetSymbol{M}\multisetUnionSymbol \multisetSymbol{N}}}&= \max(\boundMultiplicityFunction{\multisetSymbol{M}},\boundMultiplicityFunction{\multisetSymbol{N}})\\ \boundSignedMultiplicityFunction{\paren{\multisetSymbol{M}\multisetIntersectionSymbol \multisetSymbol{N}}}&= \min(\boundMultiplicityFunction{\multisetSymbol{M}},\boundMultiplicityFunction{\multisetSymbol{N}})\\ \boundSignedMultiplicityFunction{\paren{\multisetSymbol{M}\multisetRelativeComplementSymbol \multisetSymbol{N}}}&= \boundMultiplicityFunction{\multisetSymbol{M}} - \boundMultiplicityFunction{\multisetSymbol{N}}\\ \boundMultiplicityFunction{\paren{\repeatedMultiset{\sym{n}}{\multisetSymbol{M}}}}&= \sym{n} \, \paren{\boundMultiplicityFunction{\multisetSymbol{M}}}\end{aligned} \]

Signed sets

Analogous to the signed multisets \(\signedMultisets{X}\) on a set \(\setSymbol{X}\) are the signed sets \(\signedSubsets{X}\) on \(\setSymbol{X}\).

Just as for multisets, any element \(\elemOf{\setElementSymbol{x}}{\setSymbol{X}}\) can be present in a signed set \(\elemOf{\signedSetSymbol{A}}{\signedSubsets{X}}\) in a signed set in unnegated or negated form. When present in negated form it is written \(\negated{\signedSetElementSymbol{x}}\). A given element \(\setElementSymbol{x}\) can not be present in both unnegated and negated forms simultaneously. To illustrate the possibilities, we show the set of signed sets on a variety of base sets:

\[ \begin{aligned} \signedSubsets{\set{}}&= \signedSet{}\\[0.5em] \signedSubsets{\set{\rform{\setElementSymbol{a}}}}&= \set{\signedSet{},\signedSet{\rform{\signedSetElementSymbol{a}}},\signedSet{\rform{\negated{\signedSetElementSymbol{a}}}}}\\[0.5em] \signedSubsets{\set{\rform{\setElementSymbol{a}},\bform{\setElementSymbol{b}}}}&= \set{\signedSet{},\signedSet{\rform{\signedSetElementSymbol{a}}},\signedSet{\rform{\negated{\signedSetElementSymbol{a}}}},\signedSet{\bform{\signedSetElementSymbol{b}}},\signedSet{\bform{\negated{\signedSetElementSymbol{b}}}},\signedSet{\rform{\signedSetElementSymbol{a}},\bform{\signedSetElementSymbol{b}}},\signedSet{\rform{\signedSetElementSymbol{a}},\bform{\negated{\signedSetElementSymbol{b}}}},\signedSet{\rform{\negated{\signedSetElementSymbol{a}}},\bform{\signedSetElementSymbol{b}}},\signedSet{\rform{\negated{\signedSetElementSymbol{a}}},\bform{\negated{\signedSetElementSymbol{b}}}}}\end{aligned} \]

In general, for a base set \(\setSymbol{X}\) of cardinality \(\setCardinality{\setSymbol{X}} = \sym{n}\) the cardinality of the set of signed sets on \(\setSymbol{X}\) is:

\[ \setCardinality{\signedSubsets{\setSymbol{X}}} = \power{3}{\sym{n}} \]

This is because in a given signed set \(\elemOf{\signedSetSymbol{A}}{\signedSubsets{\setSymbol{X}}}\) element of \(\setSymbol{X}\) can either 1) not occur in \(\signedSetSymbol{A}\), 2) occur unnegated or 3) occur negated.

Multiplicity functions

To help us think about signed sets, we can regard them in terms of their multiplicity functions, which can now take on values in the set \(\set{-1,0,1}\) to indicate the presence, absence, or presence in negated form of any given element.

For example, here are some multiplicity functions for signed sets on base set \(\set{\rform{\setElementSymbol{a}},\bform{\signedSetElementSymbol{b}},\gform{\setElementSymbol{c}}}\):

\[ \begin{csarray}{rcrrrrrrrrrrrrr}{accbbbbbbbbbbbb} \boundMultiplicityFunction{\signedSet{\rform{\signedSetElementSymbol{a}}}} & = & \langle & \rform{\signedSetElementSymbol{a}} & \mtoSymbol & 1 & , & \bform{\signedSetElementSymbol{b}} & \mtoSymbol & 0 & , & \gform{\signedSetElementSymbol{c}} & \mtoSymbol & 0 & \rangle \\[0.5em] \boundMultiplicityFunction{\signedSet{\rform{\negated{\signedSetElementSymbol{a}}}}} & = & \langle & \rform{\signedSetElementSymbol{a}} & \mtoSymbol & -1 & , & \bform{\signedSetElementSymbol{b}} & \mtoSymbol & 0 & , & \gform{\signedSetElementSymbol{c}} & \mtoSymbol & 0 & \rangle \\[0.5em] \boundMultiplicityFunction{\signedSet{\rform{\signedSetElementSymbol{a}},\bform{\signedSetElementSymbol{b}}}} & = & \langle & \rform{\signedSetElementSymbol{a}} & \mtoSymbol & 1 & , & \bform{\signedSetElementSymbol{b}} & \mtoSymbol & 1 & , & \gform{\signedSetElementSymbol{c}} & \mtoSymbol & 0 & \rangle \\[0.5em] \boundMultiplicityFunction{\signedSet{\rform{\signedSetElementSymbol{a}},\bform{\negated{\signedSetElementSymbol{b}}}}} & = & \langle & \rform{\signedSetElementSymbol{a}} & \mtoSymbol & 1 & , & \bform{\signedSetElementSymbol{b}} & \mtoSymbol & -1 & , & \gform{\signedSetElementSymbol{c}} & \mtoSymbol & 0 & \rangle \\[0.5em] \boundMultiplicityFunction{\signedSet{\rform{\negated{\signedSetElementSymbol{a}}},\bform{\negated{\signedSetElementSymbol{b}}},\gform{\negated{\signedSetElementSymbol{c}}}}} & = & \langle & \rform{\signedSetElementSymbol{a}} & \mtoSymbol & -1 & , & \bform{\signedSetElementSymbol{b}} & \mtoSymbol & -1 & , & \gform{\signedSetElementSymbol{c}} & \mtoSymbol & -1 & \rangle \end{csarray} \]

Operations

We can define union and intersection operations on signed sets by applying the definition of these operations in terms of multiplicity functions that we obtained in the case of ordinary sets, which we recall below:

\[ \begin{aligned} \boundMultiplicityFunction{\paren{\setSymbol{M}\setUnionSymbol \setSymbol{N}}}&\defEqualSymbol \max(\boundMultiplicityFunction{\setSymbol{M}},\boundMultiplicityFunction{\setSymbol{N}})\\ \boundMultiplicityFunction{\paren{\setSymbol{M}\setIntersectionSymbol \setSymbol{N}}}&\defEqualSymbol \min(\boundMultiplicityFunction{\setSymbol{M}},\boundMultiplicityFunction{\setSymbol{N}})\\ \boundMultiplicityFunction{\paren{\setSymbol{M}\setRelativeComplementSymbol \setSymbol{N}}}&\defEqualSymbol \max(\boundMultiplicityFunction{\setSymbol{M}} - \boundMultiplicityFunction{\setSymbol{N}},0)\end{aligned} \]

To handle signed multiplicities for signed sets \(\signedSetSymbol{A}\) and \(\signedSetSymbol{B}\), we need only modify the relative complement, which should now "clip" the resulting multiplicity to be no greater than 1 and no less than -1:

\[ \begin{aligned} \boundMultiplicityFunction{\paren{\signedSetSymbol{A}\setUnionSymbol \signedSetSymbol{B}}}&\defEqualSymbol \max(\boundMultiplicityFunction{\signedSetSymbol{A}},\boundMultiplicityFunction{\signedSetSymbol{B}})\\ \boundMultiplicityFunction{\paren{\signedSetSymbol{A}\setIntersectionSymbol \signedSetSymbol{B}}}&\defEqualSymbol \min(\boundMultiplicityFunction{\signedSetSymbol{A}},\boundMultiplicityFunction{\signedSetSymbol{B}})\\ \boundMultiplicityFunction{\paren{\signedSetSymbol{A}\setRelativeComplementSymbol \signedSetSymbol{B}}}&\defEqualSymbol \clip(\boundMultiplicityFunction{\signedSetSymbol{A}} - \boundMultiplicityFunction{\signedSetSymbol{B}},-1,1)\end{aligned} \]

With these definitions in hand, we can look at some examples of unions on the signed sets on base set \(\set{\rform{\setElementSymbol{a}},\bform{\signedSetElementSymbol{b}},\gform{\setElementSymbol{c}}}\):

\[ \begin{csarray}{rclcl}{acccc} \signedSet{\rform{\setElementSymbol{a}}} & \cup & \signedSet{} & = & \signedSet{\rform{\setElementSymbol{a}}}\\[0.5em] \signedSet{\rform{\setElementSymbol{a}}} & \cup & \signedSet{\rform{\setElementSymbol{a}}} & = & \signedSet{\rform{\setElementSymbol{a}}}\\[0.5em] \signedSet{\rform{\setElementSymbol{a}}} & \cup & \signedSet{\rform{\negated{\setElementSymbol{a}}}} & = & \signedSet{\rform{\setElementSymbol{a}}}\\[0.5em] \signedSet{\rform{\setElementSymbol{a}},\bform{\negated{\setElementSymbol{b}}}} & \cup & \signedSet{\gform{\setElementSymbol{c}}} & = & \signedSet{\rform{\setElementSymbol{a}},\bform{\negated{\setElementSymbol{b}}},\gform{\setElementSymbol{c}}}\\[0.5em] \signedSet{\rform{\setElementSymbol{a}},\bform{\negated{\setElementSymbol{b}}}} & \cup & \signedSet{\bform{\setElementSymbol{b}},\gform{\negated{\setElementSymbol{c}}}} & = & \signedSet{\rform{\setElementSymbol{a}},\bform{\setElementSymbol{b}},\gform{\negated{\setElementSymbol{c}}}} \end{csarray} \]

Some intersections:

\[ \begin{csarray}{rclcl}{acccc} \signedSet{\rform{\signedSetElementSymbol{a}}} & \cap & \signedSet{} & = & \signedSet{}\\[0.5em] \signedSet{\rform{\signedSetElementSymbol{a}}} & \cap & \signedSet{\rform{\signedSetElementSymbol{a}}} & = & \signedSet{\rform{\signedSetElementSymbol{a}}}\\[0.5em] \signedSet{\rform{\signedSetElementSymbol{a}}} & \cap & \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}} & = & \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}}\\[0.5em] \signedSet{\rform{\signedSetElementSymbol{a}},\bform{\negated{\signedSetElementSymbol{b}}}} & \cap & \signedSet{\gform{\signedSetElementSymbol{c}}} & = & \signedSet{\bform{\negated{\signedSetElementSymbol{b}}}}\\[0.5em] \signedSet{\rform{\signedSetElementSymbol{a}},\bform{\negated{\signedSetElementSymbol{b}}}} & \cap & \signedSet{\bform{\signedSetElementSymbol{b}},\gform{\negated{\signedSetElementSymbol{c}}}} & = & \signedSet{\bform{\negated{\signedSetElementSymbol{b}}},\gform{\negated{\signedSetElementSymbol{c}}}} \end{csarray} \]

Some relative complements:

\[ \begin{csarray}{rclclrclclrclclrc}{acccciccccciccccc} \signedSet{\rform{\signedSetElementSymbol{a}}} & \setminus & \signedSet{} & = & \signedSet{\rform{\signedSetElementSymbol{a}}} & & \signedSet{} & \setminus & \signedSet{} & = & \signedSet{} & & \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}} & \setminus & \signedSet{} & = & \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}}\\[0.5em] \signedSet{\rform{\signedSetElementSymbol{a}}} & \setminus & \signedSet{\rform{\signedSetElementSymbol{a}}} & = & \signedSet{} & & \signedSet{} & \setminus & \signedSet{\rform{\signedSetElementSymbol{a}}} & = & \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}} & & \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}} & \setminus & \signedSet{\rform{\signedSetElementSymbol{a}}} & = & \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}}\\[0.5em] \signedSet{\rform{\signedSetElementSymbol{a}}} & \setminus & \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}} & = & \signedSet{\rform{\signedSetElementSymbol{a}}} & & \signedSet{} & \setminus & \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}} & = & \signedSet{\rform{\signedSetElementSymbol{a}}} & & \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}} & \setminus & \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}} & = & \signedSet{} \end{csarray} \]

Sum

When we introduced the sum of multisets, as distinct from the union of multisets, the reader might wonder why there was no such distinction for ordinary sets. The reason is that sets take multiplicities in \(\set{0,1}\), and for these values there is no distinction between the \(\max(□,□)\) (the multiplicity implementation of union) and \(\min(□ + □,1)\) (the multiplicity implementation of sum). For signed multisets these implementations are distinct, as there is no longer a \(\min\) at play. For signed sets, these are again distinct, although here the multiplicity implementation of sum is now \(\clip(□ + □,-1,1)\):

\[ \paren{\signedSetSymbol{A}\multisetSumSymbol \signedSetSymbol{B}}\signedMultisetMultiplicitySymbol \signedSetElementSymbol{c}\defEqualSymbol \clip(\paren{\signedSetSymbol{A}\signedMultisetMultiplicitySymbol \signedSetElementSymbol{c}} + \paren{\signedSetSymbol{B}\signedMultisetMultiplicitySymbol \signedSetElementSymbol{c}},-1,1) \]

Here we show some examples of the sums of signed sets:

\[ \begin{csarray}{rcl}{acc} \signedSet{\rform{\signedSetElementSymbol{a}}}\multisetSumSymbol \signedSet{} & = & \signedSet{}\\[0.5em] \signedSet{\rform{\signedSetElementSymbol{a}}}\multisetSumSymbol \signedSet{\rform{\signedSetElementSymbol{a}}} & = & \signedSet{\rform{\signedSetElementSymbol{a}}}\\[0.5em] \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}}\multisetSumSymbol \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}} & = & \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}}\\[0.5em] \signedSet{\rform{\signedSetElementSymbol{a}}}\multisetSumSymbol \signedSet{\rform{\negated{\signedSetElementSymbol{a}}}} & = & \signedSet{}\\[0.5em] \signedSet{\rform{\signedSetElementSymbol{a}},\bform{\negated{\signedSetElementSymbol{b}}}}\multisetSumSymbol \signedSet{\gform{\signedSetElementSymbol{c}}} & = & \signedSet{\rform{\signedSetElementSymbol{a}},\bform{\negated{\signedSetElementSymbol{b}}},\gform{\signedSetElementSymbol{c}}}\\[0.5em] \signedSet{\rform{\signedSetElementSymbol{a}},\bform{\negated{\signedSetElementSymbol{b}}}}\multisetSumSymbol \signedSet{\bform{\signedSetElementSymbol{b}},\gform{\negated{\signedSetElementSymbol{c}}}} & = & \signedSet{\rform{\signedSetElementSymbol{a}},\gform{\negated{\signedSetElementSymbol{c}}}} \end{csarray} \]

An interesting aspect of signed set summation is that it is not associative, unlike for multiset summation. For multisets \(\multisetSymbol{X},\multisetSymbol{Y},\multisetSymbol{Z}\), we have that \(\multisetSymbol{X}\multisetSumSymbol \paren{\multisetSymbol{Y}\multisetSumSymbol \multisetSymbol{Z}}\identicallyEqualSymbol \paren{\multisetSymbol{X}\multisetSumSymbol \multisetSymbol{Y}}\multisetSumSymbol \multisetSymbol{Z}\), which justifies writing sums of three or more sets without any parentheses \(\multisetSymbol{X}\multisetSumSymbol \multisetSymbol{Y}\multisetSumSymbol \multisetSymbol{Z}\) since the order of binary operations does not matter. This is not true for signed sets because of the presence of \(\clip\):

\[ \begin{nsarray}{c} \paren{\signedSet{\rform{\setElementSymbol{a}}}\multisetSumSymbol \signedSet{\rform{\setElementSymbol{a}}}}\multisetSumSymbol \signedSet{\rform{\negated{\setElementSymbol{a}}}} = \signedSet{\rform{\setElementSymbol{a}}}\multisetSumSymbol \signedSet{\rform{\negated{\setElementSymbol{a}}}} = \signedSet{}\\[1em] \signedSet{\rform{\setElementSymbol{a}}}\multisetSumSymbol \paren{\signedSet{\rform{\setElementSymbol{a}}}\multisetSumSymbol \signedSet{\rform{\negated{\setElementSymbol{a}}}}} = \signedSet{\rform{\setElementSymbol{a}}}\multisetSumSymbol \signedSet{} = \signedSet{\rform{\setElementSymbol{a}}} \end{nsarray} \]

Signed projection and lift

Just like for sets and multisets, we can lift and project between signed sets and signed multisets.

\[ \begin{csarray}{ccccc}{acccc} \signed{\lift} & : & \signedSubsets{X} & \rarr & \signedMultisets{\setSymbol{X}}\\ \signed{\projection} & : & \signedMultisets{\setSymbol{X}} & \rarr & \signedSubsets{X} \end{csarray} \]

Signed lifting takes a signed set and gives the signed multiset that contains each element either negated or unnegated exactly once:

\[ \begin{aligned} \function{\signed{\lift}}(\setSymbol{A})&\defEqualSymbol \signed{\multisetConstructor{\multisetElementSymbol{x}}{\elemOf{\multisetElementSymbol{x}}{\setSymbol{A}}}}\\[1em] \paren{\function{\signed{\lift}}(\setSymbol{A})}\signedMultisetMultiplicitySymbol \signedMultisetElementSymbol{c}&\defEqualSymbol \setSymbol{A}\signedMultisetMultiplicitySymbol \signedSetElementSymbol{c}\end{aligned} \]

Signed projection takes a signed multiset and gives the signed set that contains an element unnegated if it occurs a positive number of times, and negated if it occurs a negative number of times:

\[ \begin{aligned} \function{\signed{\projection}}(\signedMultisetSymbol{A})&\defEqualSymbol \setConstructor{\signedMultisetElementSymbol{a}}{\elemOf{\signedMultisetElementSymbol{a}}{\positiveSignedPart{\signedMultisetSymbol{A}}}}\multisetSumSymbol \setConstructor{\negated{\signedMultisetElementSymbol{a}}}{\elemOf{\signedMultisetElementSymbol{a}}{\negativeSignedPart{\signedMultisetSymbol{A}}}}\\[1em] \paren{\function{\signed{\projection}}(\signedMultisetSymbol{A})}\signedMultisetMultiplicitySymbol \signedSetElementSymbol{c}&\defEqualSymbol \clip(\signedMultisetSymbol{A}\signedMultisetMultiplicitySymbol \signedSetElementSymbol{c},-1,1)\end{aligned} \]

Here we use \(\positiveSignedPart{\signedMultisetSymbol{A}}\) to denote the ordinary multiset consisting of all the unnegated elements of the signed multiset \(\signedMultisetSymbol{A}\), and \(\negativeSignedPart{\signedMultisetSymbol{A}}\) to be the same but for negated elements (where the negated elements occur unnegated in the result, of course):

\[ \begin{aligned} \positiveSignedPart{\signedMultisetSymbol{A}}\multisetMultiplicitySymbol \multisetElementSymbol{c}&\defEqualSymbol \max(\signedMultisetSymbol{A}\multisetMultiplicitySymbol \multisetElementSymbol{c},0)\\ \negativeSignedPart{\signedMultisetSymbol{A}}\multisetMultiplicitySymbol \multisetElementSymbol{c}&\defEqualSymbol \max(\minus{\signedMultisetSymbol{A}\multisetMultiplicitySymbol \multisetElementSymbol{c}},0)\end{aligned} \]

As before, lifting and projecting a signed set yields the same set:

\[ \function{\signed{\projection}}(\function{\signed{\lift}}(\setSymbol{A}))\identicallyEqualSymbol \setSymbol{A} \]

Signed multiset rings

Recap

In the previous section we saw how the multisets on a set with an associated semigroup operation give rise to a semiring. Specifically if we have a semigroup operation \(\functionSignature{\function{\sgdot }}{\tuple{\setSymbol{X},\setSymbol{X}}}{\setSymbol{X}}\) on a set \(\setSymbol{X}\), we can equip the set of multisets \(\multisets{X}\) with a multiplication \(\msrdot \defEqualSymbol \multiImageModifier{\sgdot }\) to yield a semiring that we will denote \(\multisetSemiring{\setSymbol{X}}{\sgdot }\).

Compactly, then, we have \(\multisetSemiring{\setSymbol{X}}{\sgdot }\defEqualSymbol \tuple{\multisets{X},\multisetSumSymbol ,\msrdot }\). To recap, the semiring operations are:

  • adding two elements \(\multisetSymbol{A},\multisetSymbol{B}\) of the semiring corresponds to adding the corresponding multisets (\(\isomorphicSymbol\) adding their multiplicity functions):

\[ \begin{aligned} \multisetSymbol{A}\msrplus \multisetSymbol{B}&= \multiset{\multisetElementSymbol{a_1},\multisetElementSymbol{a_2},\ellipsis }\multisetSumSymbol \multiset{\multisetElementSymbol{b_1},\multisetElementSymbol{b_2},\ellipsis }\\ &= \multiset{\multisetElementSymbol{a_1},\multisetElementSymbol{a_2},\ellipsis ,\multisetElementSymbol{b_1},\multisetElementSymbol{b_2},\ellipsis }\end{aligned} \]
  • multiplying two elements of the semiring corresponds to \(\sgdot\)-multiplying all pairs that can be formed from the two multisets:

\[ \begin{aligned} \multisetSymbol{A}\msrdot \multisetSymbol{B}&= \function{\multiImageModifier{\sgdot }}(\multiset{\multisetElementSymbol{a_1},\multisetElementSymbol{a_2},\ellipsis },\multiset{\multisetElementSymbol{b_1},\multisetElementSymbol{b_2},\ellipsis })\\ &= \multiset{\multisetElementSymbol{a_1}\sgdot \multisetElementSymbol{b_1},\multisetElementSymbol{a_1}\sgdot \multisetElementSymbol{b_2},\ellipsis ,\multisetElementSymbol{a_2}\sgdot \multisetElementSymbol{b_1},\multisetElementSymbol{a_2}\sgdot \multisetElementSymbol{b_2},\ellipsis }\end{aligned} \]

Multiplicity functions

We can also state the semiring sum and product in terms of multiplicity functions. The multiplicity of some element \(\multisetElementSymbol{c}\) in the sum and product is computed as:

\[ \begin{aligned} \paren{\multisetSymbol{A}\msrplus \multisetSymbol{B}}\multisetMultiplicitySymbol \multisetElementSymbol{c}&= \multisetSymbol{A}\multisetMultiplicitySymbol \multisetElementSymbol{c} + \multisetSymbol{B}\multisetMultiplicitySymbol \multisetElementSymbol{c}\\ \paren{\multisetSymbol{A}\msrdot \multisetSymbol{B}}\multisetMultiplicitySymbol \multisetElementSymbol{c}&= \indexSum{\paren{\multisetSymbol{A}\multisetMultiplicitySymbol \multisetElementSymbol{a}} \, \paren{\multisetSymbol{B}\multisetMultiplicitySymbol \multisetElementSymbol{b}}}{\multisetElementSymbol{a}\sgdot \multisetElementSymbol{b} = \multisetElementSymbol{c}}{}\end{aligned} \]

We can now extend this situation to signed multisets by simply allowing the corresponding multiplicities to be negative.

Signed multiset ring

If \(\functionSignature{\function{\sgdot }}{\tuple{\setSymbol{X},\setSymbol{X}}}{\setSymbol{X}}\) is a semigroup operation on a set \(\setSymbol{X}\), we can now define the signed multiset ring, written \(\signedMultisetRing{\setSymbol{X}}{\sgdot }\) to be the following tuple:

\[ \signedMultisetRing{\setSymbol{X}}{\sgdot }\defEqualSymbol \tuple{\signedMultisets{\setSymbol{X}},\multisetSumSymbol ,\msrdot } \]

Here, \(\msrdot\) is again the multi-image lift \(\multiImageModifier{\sgdot }\) of the semigroup operation \(\sgdot\), this time to operate on signed multisets. How does this work?

The most natural way to understand this is to first extend \(\sgdot\) to be a binary operation on signed sets on \(\setSymbol{X}\).

Advanced topics

Lattice structure

Convexity

Galois connection