\( \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{#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\rform#1{ {\textcolor{e1432d}{#1}}} \gdef\gform#1{ {\textcolor{4ea82a}{#1}}} \gdef\bform#1{ {\textcolor{3e81c3}{#1}}} \gdef\rgform#1{ {\textcolor{dc841a}{#1}}} \gdef\gbform#1{ {\textcolor{47a5a7}{#1}}} \gdef\rbform#1{ {\textcolor{c74883}{#1}}} \gdef\waform#1{ {\textcolor{6b6b6b}{#1}}} \gdef\wbform#1{ {\textcolor{929292}{#1}}} \gdef\wcform#1{ {\textcolor{c5c5c5}{#1}}} \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\forwardFactor{\uparrow} \gdef\backwardFactor{\downarrow} \gdef\neutralFactor{\mid} \gdef\arrowhead{⏵} \gdef\deSymbol{ { { {\raisebox{1.1pt}{\tinybullet}\mkern{-1pt}{→}}}\,}} \gdef\ueSymbol{ {\raisebox{1pt}{\tinybullet\raisebox{-0.03em}{\mkern{-0.3pt}{\tiny──}\mkern{-0.3pt}}\tinybullet}\,}} \gdef\ldeSymbol{ { { {\raisebox{1.1pt}{\tinybullet}\mkern{-1pt}{\longrightarrow}}}\,}} \gdef\lueSymbol{ {\raisebox{1pt}{\tinybullet\raisebox{-0.03em}{\mkern{-0.3pt}{\tiny────}\mkern{-0.3pt}}\tinybullet}\,}} \gdef\de#1#2{ { {#1} \deSymbol {#2}}} \gdef\ue#1#2{ { {#1} \ueSymbol {#2}}} \gdef\tde#1#2#3{ { {#1} \overset{#3}{\deSymbol} {#2}}} \gdef\tue#1#2#3{ { {#1} \overset{#3}{\ueSymbol} {#2}}} \gdef\ltde#1#2#3{ { {#1} \overset{#3}{\ldeSymbol} {#2}}} \gdef\ltue#1#2#3{ { {#1} \overset{#3}{\lueSymbol} {#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{\cong} \gdef\homotopicSymbol{\simeq} \gdef\approxEqualSymbol{\approx} \gdef\bijectiveSymbol{\cong} \gdef\defeq{\;≝\;} \gdef\defEqualSymbol{\;≝\;} \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\!\degree} \gdef\toroidalModifier#1{\supercirc{#1}} \gdef\modulo#1{\supercirc{#1}} \gdef\dividesSymbol{\,|\,} \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{ {\,∷\,}} \gdef\pathCompose#1#2{ {#1}\pathComposeSymbol{#2}} \gdef\translateSymbol{\uparrow} \gdef\backwardTranslateSymbol{\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\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\multiImageModifier#1{ {#1}^{\Rightarrow}} \gdef\multiPreimageModifier#1{ {#1}^{\Leftarrow}} \gdef\functionComposition#1{#1} \gdef\functionCompositionSymbol{∘} \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\nullPath{\bot} \gdef\nullElement{\bot} \gdef\path#1{#1} \gdef\vert#1{#1} \gdef\underdot#1{\underset{\raisebox{0.3em}{.}}{#1}} \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\realVectorSpace#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\indeterminate#1{#1} \gdef\semiring#1{#1} \gdef\sym#1{#1} \gdef\matrix#1{#1} \gdef\polynomial#1{#1} \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\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}|{#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\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\covering#1#2#3{ {#2} \sqsupseteq_{#1} {#3}} \gdef\powerSet#1{\powerSetSymbol({#1})} \gdef\powerSetSymbol{\mathscr{P}} \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\latticeElement#1{#1} \gdef\latticeMeetSymbol{\wedge} \gdef\latticeJoinSymbol{\vee} \gdef\latticeTop{\top} \gdef\latticeBottom{\bot} \gdef\latticeGreaterSymbol{>} \gdef\latticeGreaterEqualSymbol{\ge} \gdef\latticeLessSymbol{<} \gdef\latticeLessEqualSymbol{\le} \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\groupoidElement#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\multisets#1{\mathscr{M}({#1})} \gdef\signedMultisets#1{\mathscr{M^*}({#1})} \gdef\setSymbol#1{#1} \gdef\multisetSymbol#1{#1} \gdef\setElementSymbol#1{#1} \gdef\multisetElementSymbol#1{#1} \gdef\multisetMultiplicitySymbol{\raisebox{.1em}{\small\#}\mkern{.1em}} \gdef\boundMultiplicityFunction#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\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\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{\mathsf{#1}} \gdef\genericRewritingSystem{\namedSystem{System}} \gdef\stringRewritingSystem{\namedSystem{Str}} \gdef\turingMachineRewritingSystem{\namedSystem{TM}} \gdef\cellularAutomatonRewritingSystem{\namedSystem{CA}} \gdef\graphRewritingSystem{\namedSystem{Gr}} \gdef\hypergraphRewritingSystem{\namedSystem{HGr}} \gdef\petriNetRewritingSystem{\namedSystem{Petri}} \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\set#1{\{ {#1} \}} \gdef\list#1{\{ {#1} \}} \gdef\multiset#1{\lBrace {#1} \rBrace} \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{\,\largeDot\,}\vsp} \gdef\ellipsis{\dots} \gdef\verticalEllipsis{\vdots} \gdef\appliedRelation#1{#1} \gdef\setUnionSymbol{\cup} \gdef\setIntersectionSymbol{\cap} \gdef\setRelativeComplementSymbol{\backslash} \gdef\multisetUnionSymbol{\cup} \gdef\multisetIntersectionSymbol{\cap} \gdef\multisetRelativeComplementSymbol{\backslash} \gdef\multisetSumSymbol{+} \gdef\cartesianProductSymbol{\times} \gdef\functionSignature#1#2#3{ { {#1} : {#2} \to {#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\dependentQuiverProductSymbol{\,\times\,} \gdef\independentQuiverProductSymbol{\,⨝\,} \gdef\graphUnionSymbol{\sqcup} \gdef\graphProductSymbol{\times} \gdef\inlineProdSymbol{\mid} \gdef\serialCardSymbol{ {:}} \gdef\parallelCardSymbol{ {\mid}} \gdef\cardinalSequenceSymbol{ {:}} \gdef\cardinalProductSymbol{\inlineProdSymbol} \gdef\vertexProductSymbol{\!\inlineProdSymbol\!} \gdef\edgeProductSymbol{\inlineProdSymbol} \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\oneTo#1{1..{#1}} \gdef\zeroTo#1{0..{#1}} \gdef\qstring#1{\mathtt{"}{#1}\mathtt{"}} \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\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 datastructures, 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 interpretational 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 frontload 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 an unrestricted 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:

\[ \multisets{\multisetSymbol{B}}\bijectiveSymbol \functionSpace{\multisetSymbol{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.

Sets as 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 \(\multisets{\multisetSymbol{B}}\), multisets on \(\multisetSymbol{B}\) with maximum multiplicity 1:

\[ \powerSet{\multisetSymbol{B}}\bijectiveSymbol \setConstructor{\multisetSymbol{M}}{\elemOf{\multisetSymbol{M}}{\multisets{\multisetSymbol{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}}{\multisetSymbol{X}}\\ 0 &\text{otherwise} \end{cases} } \]

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

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

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} \multisetSymbol{X}\setUnionSymbol \multisetSymbol{Y}&\defEqualSymbol \setConstructor{\setElementSymbol{x}}{\paren{\elemOf{\setElementSymbol{x}}{\multisetSymbol{X}}}\orSymbol \paren{\elemOf{\setElementSymbol{x}}{\multisetSymbol{Y}}}}\\ \multisetSymbol{X}\setIntersectionSymbol \multisetSymbol{Y}&\defEqualSymbol \setConstructor{\setElementSymbol{x}}{\paren{\elemOf{\setElementSymbol{x}}{\multisetSymbol{X}}}\andSymbol \paren{\elemOf{\setElementSymbol{x}}{\multisetSymbol{Y}}}}\\ \multisetSymbol{X}\setRelativeComplementSymbol \multisetSymbol{Y}&\defEqualSymbol \setConstructor{\setElementSymbol{x}}{\paren{\elemOf{\setElementSymbol{x}}{\multisetSymbol{X}}}\andSymbol \paren{\notElemOf{\setElementSymbol{x}}{\multisetSymbol{Y}}}}\end{aligned} \]

For multisets \(\multisetSymbol{M}\textAnd \multisetSymbol{N}\), we now define the equivalent operations 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{nsarray}{l} \langle \kern{2pt}\mto{\rform{\card{r}}}{2},\\ \phantom{ \langle \kern{2pt}}\mto{\gform{\card{g}}}{1},\\ \phantom{ \langle \kern{2pt}}\mto{\bform{\card{b}}}{2}\kern{2pt} \rangle \end{nsarray} & \multisetUnionSymbol & \begin{nsarray}{l} \langle \kern{2pt}\mto{\rform{\card{r}}}{1},\\ \phantom{ \langle \kern{2pt}}\mto{\gform{\card{g}}}{0},\\ \phantom{ \langle \kern{2pt}}\mto{\bform{\card{b}}}{2}\kern{2pt} \rangle \end{nsarray} & = & \begin{nsarray}{l} \langle \kern{2pt}\mto{\rform{\card{r}}}{2},\\ \phantom{ \langle \kern{2pt}}\mto{\gform{\card{g}}}{1},\\ \phantom{ \langle \kern{2pt}}\mto{\bform{\card{b}}}{2}\kern{2pt} \rangle \end{nsarray} & \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{nsarray}{l} \langle \kern{2pt}\mto{\rform{\card{r}}}{2},\\ \phantom{ \langle \kern{2pt}}\mto{\gform{\card{g}}}{1},\\ \phantom{ \langle \kern{2pt}}\mto{\bform{\card{b}}}{0}\kern{2pt} \rangle \end{nsarray} & \multisetIntersectionSymbol & \begin{nsarray}{l} \langle \kern{2pt}\mto{\rform{\card{r}}}{1},\\ \phantom{ \langle \kern{2pt}}\mto{\gform{\card{g}}}{0},\\ \phantom{ \langle \kern{2pt}}\mto{\bform{\card{b}}}{2}\kern{2pt} \rangle \end{nsarray} & = & \begin{nsarray}{l} \langle \kern{2pt}\mto{\rform{\card{r}}}{1},\\ \phantom{ \langle \kern{2pt}}\mto{\gform{\card{g}}}{0},\\ \phantom{ \langle \kern{2pt}}\mto{\bform{\card{b}}}{2}\kern{2pt} \rangle \end{nsarray} & \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{nsarray}{l} \langle \kern{2pt}\mto{\rform{\card{r}}}{2},\\ \phantom{ \langle \kern{2pt}}\mto{\gform{\card{g}}}{1},\\ \phantom{ \langle \kern{2pt}}\mto{\bform{\card{b}}}{0}\kern{2pt} \rangle \end{nsarray} & \multisetRelativeComplementSymbol & \begin{nsarray}{l} \langle \kern{2pt}\mto{\rform{\card{r}}}{1},\\ \phantom{ \langle \kern{2pt}}\mto{\gform{\card{g}}}{0},\\ \phantom{ \langle \kern{2pt}}\mto{\bform{\card{b}}}{2}\kern{2pt} \rangle \end{nsarray} & = & \begin{nsarray}{l} \langle \kern{2pt}\mto{\rform{\card{r}}}{1},\\ \phantom{ \langle \kern{2pt}}\mto{\gform{\card{g}}}{1},\\ \phantom{ \langle \kern{2pt}}\mto{\bform{\card{b}}}{0}\kern{2pt} \rangle \end{nsarray} & \end{array} \]

Note that in the special case of multisets that represent sets, the \(\max\textAnd \min\) functions operate on multiplicites in \(\set{0,1}\), and in this limited range max and min behave like logical \(\orSymbol\) and \(\andSymbol\), recovering the original definitions we had for sets. 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{nsarray}{l} \langle \kern{2pt}\mto{\rform{\card{r}}}{2},\\ \phantom{ \langle \kern{2pt}}\mto{\gform{\card{g}}}{1},\\ \phantom{ \langle \kern{2pt}}\mto{\bform{\card{b}}}{0}\kern{2pt} \rangle \end{nsarray} & \multisetSumSymbol & \begin{nsarray}{l} \langle \kern{2pt}\mto{\rform{\card{r}}}{1},\\ \phantom{ \langle \kern{2pt}}\mto{\gform{\card{g}}}{0},\\ \phantom{ \langle \kern{2pt}}\mto{\bform{\card{b}}}{2}\kern{2pt} \rangle \end{nsarray} & = & \begin{nsarray}{l} \langle \kern{2pt}\mto{\rform{\card{r}}}{3},\\ \phantom{ \langle \kern{2pt}}\mto{\gform{\card{g}}}{1},\\ \phantom{ \langle \kern{2pt}}\mto{\bform{\card{b}}}{2}\kern{2pt} \rangle \end{nsarray} & \end{array} \]

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 store 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 constuctor 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! 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.

Definition

Consider a function \(\functionSignature{\function{f}}{\setSymbol{X}}{\setSymbol{Y}}\). We wish to apply it "setwise", 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}{accccc} \function{f} & : & \setSymbol{X} & \rarr & \setSymbol{Y}\\ \imageModifier{\function{f}} & : & \powerSet{\setSymbol{X}} & \rarr & \powerSet{\setSymbol{Y}}\\ \preimageModifier{\function{f}} & : & \powerSet{\setSymbol{Y}} & \rarr & \powerSet{\setSymbol{X}} \end{csarray} \]

We define them to 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{\imageModifier{\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}{accicciccicci} & & & \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 define \(\imageModifier{\function{f}}\) as an explicit mapping:

\[ \imageModifier{\function{f}} = \begin{csarray}{rrclrclrclrcll}{abbbcbbcbbcbbaa} \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 :

\[ \begin{csarray}{rclccccc}{accccccc} \imageModifier{\function{f}}(\set{\rform{\card{r}}} & \cup & \set{\bform{\card{b}}}) & = & \function{\imageModifier{\function{f}}}(\set{\rform{\card{r}},\bform{\card{b}}}) & = & \set{\rgform{\card{x}},\gbform{\card{y}}}\\[0.5em] \function{\imageModifier{\function{f}}}(\set{\rform{\card{r}}}) & \cup & \function{\imageModifier{\function{f}}}(\set{\bform{\card{b}}}) & = & \set{\rgform{\card{x}}}\setUnionSymbol \set{\gbform{\card{y}}} & = & \set{\rgform{\card{x}},\gbform{\card{y}}} \end{csarray} \]

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

\[ \begin{csarray}{rclccccc}{accccccc} \imageModifier{\function{f}}(\set{\rform{\card{r}}} & \cap & \set{\gform{\card{g}}}) & = & \function{\imageModifier{\function{f}}}(\set{}) & = & \set{}\\[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}}} & = & \set{\rgform{\card{x}}}\\[1em] \imageModifier{\function{f}}(\set{\rform{\card{r}}} & \setminus & \set{\gform{\card{g}}}) & = & \function{\imageModifier{\function{f}}}(\set{\rform{\card{r}}}) & = & \set{\rgform{\card{x}}}\\[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}}} & = & \set{} \end{csarray} \]

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

\[ \begin{csarray}{rclcrcr}{accccccc} \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}{rclccccc}{accccccc} \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}{rclccccc}{accccccc} \preimageModifier{\function{f}}(\set{\rgform{\card{x}}} & \cup & \set{\gbform{\card{y}}}) & = & \function{\preimageModifier{\function{f}}}(\set{\rgform{\card{x}},\gbform{\card{y}}}) & = & \set{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}\\[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}}} & = & \set{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}\\[1em] \preimageModifier{\function{f}}(\set{\rgform{\card{x}}} & \cap & \set{\rgform{\card{x}},\gbform{\card{y}}}) & = & \function{\preimageModifier{\function{f}}}(\set{\rgform{\card{x}}}) & = & \set{\rform{\card{r}},\gform{\card{g}}}\\[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}}} & = & \set{\rform{\card{r}},\gform{\card{g}}}\\[1em] \preimageModifier{\function{f}}(\set{\rgform{\card{x}},\gbform{\card{y}}} & \setminus & \set{\gbform{\card{y}}}) & = & \function{\preimageModifier{\function{f}}}(\set{\rgform{\card{x}}}) & = & \set{\rform{\card{r}},\gform{\card{g}}}\\[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}}} & = & \set{\rform{\card{r}},\gform{\card{g}}} \end{csarray} \]

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

Images and preimages of multisets

The muli-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}}{\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.

Monoids

Advanced topics

Lattice structure

Convexity

Galois connection

Signed multisets